[net-next-2.6.git] / fs / hfsplus / bitmap.c

/*
 *  linux/fs/hfsplus/bitmap.c
 *
 * Copyright (C) 2001
 * Brad Boyer (flar@allandria.com)
 * (C) 2003 Ardis Technologies <roman@ardistech.com>
 *
 * Handling of allocation file
 */

#include <linux/pagemap.h>

#include "hfsplus_fs.h"
#include "hfsplus_raw.h"

#define PAGE_CACHE_BITS	(PAGE_CACHE_SIZE * 8)

int hfsplus_block_allocate(struct super_block *sb, u32 size, u32 offset, u32 *max)
{
	struct page *page;
	struct address_space *mapping;
	__be32 *pptr, *curr, *end;
	u32 mask, start, len, n;
	__be32 val;
	int i;

	len = *max;
	if (!len)
		return size;

	dprint(DBG_BITMAP, "block_allocate: %u,%u,%u\n", size, offset, len);
	mutex_lock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
	mapping = HFSPLUS_SB(sb).alloc_file->i_mapping;
	page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS, NULL);
	if (IS_ERR(page)) {
		start = size;
		goto out;
	}
	pptr = kmap(page);
	curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
	i = offset % 32;
	offset &= ~(PAGE_CACHE_BITS - 1);
	if ((size ^ offset) / PAGE_CACHE_BITS)
		end = pptr + PAGE_CACHE_BITS / 32;
	else
		end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;

	/* scan the first partial u32 for zero bits */
	val = *curr;
	if (~val) {
		n = be32_to_cpu(val);
		mask = (1U << 31) >> i;
		for (; i < 32; mask >>= 1, i++) {
			if (!(n & mask))
				goto found;
		}
	}
	curr++;

	/* scan complete u32s for the first zero bit */
	while (1) {
		while (curr < end) {
			val = *curr;
			if (~val) {
				n = be32_to_cpu(val);
				mask = 1 << 31;
				for (i = 0; i < 32; mask >>= 1, i++) {
					if (!(n & mask))
						goto found;
				}
			}
			curr++;
		}
		kunmap(page);
		offset += PAGE_CACHE_BITS;
		if (offset >= size)
			break;
		page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
					 NULL);
		if (IS_ERR(page)) {
			start = size;
			goto out;
		}
		curr = pptr = kmap(page);
		if ((size ^ offset) / PAGE_CACHE_BITS)
			end = pptr + PAGE_CACHE_BITS / 32;
		else
			end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
	}
	dprint(DBG_BITMAP, "bitmap full\n");
	start = size;
	goto out;

found:
	start = offset + (curr - pptr) * 32 + i;
	if (start >= size) {
		dprint(DBG_BITMAP, "bitmap full\n");
		goto out;
	}
	/* do any partial u32 at the start */
	len = min(size - start, len);
	while (1) {
		n |= mask;
		if (++i >= 32)
			break;
		mask >>= 1;
		if (!--len || n & mask)
			goto done;
	}
	if (!--len)
		goto done;
	*curr++ = cpu_to_be32(n);
	/* do full u32s */
	while (1) {
		while (curr < end) {
			n = be32_to_cpu(*curr);
			if (len < 32)
				goto last;
			if (n) {
				len = 32;
				goto last;
			}
			*curr++ = cpu_to_be32(0xffffffff);
			len -= 32;
		}
		set_page_dirty(page);
		kunmap(page);
		offset += PAGE_CACHE_BITS;
		page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
					 NULL);
		if (IS_ERR(page)) {
			start = size;
			goto out;
		}
		pptr = kmap(page);
		curr = pptr;
		end = pptr + PAGE_CACHE_BITS / 32;
	}
last:
	/* do any partial u32 at end */
	mask = 1U << 31;
	for (i = 0; i < len; i++) {
		if (n & mask)
			break;
		n |= mask;
		mask >>= 1;
	}
done:
	*curr = cpu_to_be32(n);
	set_page_dirty(page);
	kunmap(page);
	*max = offset + (curr - pptr) * 32 + i - start;
	HFSPLUS_SB(sb).free_blocks -= *max;
	sb->s_dirt = 1;
	dprint(DBG_BITMAP, "-> %u,%u\n", start, *max);
out:
	mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
	return start;
}

int hfsplus_block_free(struct super_block *sb, u32 offset, u32 count)
{
	struct page *page;
	struct address_space *mapping;
	__be32 *pptr, *curr, *end;
	u32 mask, len, pnr;
	int i;

	/* is there any actual work to be done? */
	if (!count)
		return 0;

	dprint(DBG_BITMAP, "block_free: %u,%u\n", offset, count);
	/* are all of the bits in range? */
	if ((offset + count) > HFSPLUS_SB(sb).total_blocks)
		return -2;

	mutex_lock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
	mapping = HFSPLUS_SB(sb).alloc_file->i_mapping;
	pnr = offset / PAGE_CACHE_BITS;
	page = read_mapping_page(mapping, pnr, NULL);
	pptr = kmap(page);
	curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
	end = pptr + PAGE_CACHE_BITS / 32;
	len = count;

	/* do any partial u32 at the start */
	i = offset % 32;
	if (i) {
		int j = 32 - i;
		mask = 0xffffffffU << j;
		if (j > count) {
			mask |= 0xffffffffU >> (i + count);
			*curr++ &= cpu_to_be32(mask);
			goto out;
		}
		*curr++ &= cpu_to_be32(mask);
		count -= j;
	}

	/* do full u32s */
	while (1) {
		while (curr < end) {
			if (count < 32)
				goto done;
			*curr++ = 0;
			count -= 32;
		}
		if (!count)
			break;
		set_page_dirty(page);
		kunmap(page);
		page = read_mapping_page(mapping, ++pnr, NULL);
		pptr = kmap(page);
		curr = pptr;
		end = pptr + PAGE_CACHE_BITS / 32;
	}
done:
	/* do any partial u32 at end */
	if (count) {
		mask = 0xffffffffU >> count;
		*curr &= cpu_to_be32(mask);
	}
out:
	set_page_dirty(page);
	kunmap(page);
	HFSPLUS_SB(sb).free_blocks += len;
	sb->s_dirt = 1;
	mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);

	return 0;
}
Commit	Line	Data
1da177e4 LT	1	/*
	2	* linux/fs/hfsplus/bitmap.c
	3	*
	4	* Copyright (C) 2001
	5	* Brad Boyer (flar@allandria.com)
	6	* (C) 2003 Ardis Technologies <roman@ardistech.com>
	7	*
	8	* Handling of allocation file
	9	*/
	10
	11	#include <linux/pagemap.h>
	12
	13	#include "hfsplus_fs.h"
	14	#include "hfsplus_raw.h"
	15
	16	#define PAGE_CACHE_BITS (PAGE_CACHE_SIZE * 8)
	17
	18	int hfsplus_block_allocate(struct super_block sb, u32 size, u32 offset, u32 max)
	19	{
	20	struct page *page;
	21	struct address_space *mapping;
	22	__be32 pptr, curr, *end;
	23	u32 mask, start, len, n;
	24	__be32 val;
	25	int i;
	26
	27	len = *max;
	28	if (!len)
	29	return size;
	30
	31	dprint(DBG_BITMAP, "block_allocate: %u,%u,%u\n", size, offset, len);
1b1dcc1b	32	mutex_lock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
1da177e4	33	mapping = HFSPLUS_SB(sb).alloc_file->i_mapping;
090d2b18	34	page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS, NULL);
649f1ee6 ES	35	if (IS_ERR(page)) {
	36	start = size;
	37	goto out;
	38	}
1da177e4 LT	39	pptr = kmap(page);
	40	curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
	41	i = offset % 32;
	42	offset &= ~(PAGE_CACHE_BITS - 1);
	43	if ((size ^ offset) / PAGE_CACHE_BITS)
	44	end = pptr + PAGE_CACHE_BITS / 32;
	45	else
	46	end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
	47
	48	/* scan the first partial u32 for zero bits */
	49	val = *curr;
	50	if (~val) {
	51	n = be32_to_cpu(val);
	52	mask = (1U << 31) >> i;
	53	for (; i < 32; mask >>= 1, i++) {
	54	if (!(n & mask))
	55	goto found;
	56	}
	57	}
	58	curr++;
	59
	60	/* scan complete u32s for the first zero bit */
	61	while (1) {
	62	while (curr < end) {
	63	val = *curr;
	64	if (~val) {
	65	n = be32_to_cpu(val);
	66	mask = 1 << 31;
	67	for (i = 0; i < 32; mask >>= 1, i++) {
	68	if (!(n & mask))
	69	goto found;
	70	}
	71	}
	72	curr++;
	73	}
	74	kunmap(page);
	75	offset += PAGE_CACHE_BITS;
	76	if (offset >= size)
	77	break;
090d2b18 PE	78	page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
090d2b18 PE	79	NULL);
649f1ee6 ES	80	if (IS_ERR(page)) {
	81	start = size;
	82	goto out;
	83	}
1da177e4 LT	84	curr = pptr = kmap(page);
	85	if ((size ^ offset) / PAGE_CACHE_BITS)
	86	end = pptr + PAGE_CACHE_BITS / 32;
	87	else
	88	end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
	89	}
	90	dprint(DBG_BITMAP, "bitmap full\n");
	91	start = size;
	92	goto out;
	93
	94	found:
	95	start = offset + (curr - pptr) * 32 + i;
	96	if (start >= size) {
	97	dprint(DBG_BITMAP, "bitmap full\n");
	98	goto out;
	99	}
	100	/* do any partial u32 at the start */
	101	len = min(size - start, len);
	102	while (1) {
	103	n \|= mask;
	104	if (++i >= 32)
	105	break;
	106	mask >>= 1;
	107	if (!--len \|\| n & mask)
	108	goto done;
	109	}
	110	if (!--len)
	111	goto done;
	112	*curr++ = cpu_to_be32(n);
	113	/* do full u32s */
	114	while (1) {
	115	while (curr < end) {
	116	n = be32_to_cpu(*curr);
	117	if (len < 32)
	118	goto last;
	119	if (n) {
	120	len = 32;
	121	goto last;
	122	}
	123	*curr++ = cpu_to_be32(0xffffffff);
	124	len -= 32;
	125	}
	126	set_page_dirty(page);
	127	kunmap(page);
	128	offset += PAGE_CACHE_BITS;
090d2b18 PE	129	page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
090d2b18 PE	130	NULL);
649f1ee6 ES	131	if (IS_ERR(page)) {
	132	start = size;
	133	goto out;
	134	}
1da177e4 LT	135	pptr = kmap(page);
	136	curr = pptr;
	137	end = pptr + PAGE_CACHE_BITS / 32;
	138	}
	139	last:
	140	/* do any partial u32 at end */
	141	mask = 1U << 31;
	142	for (i = 0; i < len; i++) {
	143	if (n & mask)
	144	break;
	145	n \|= mask;
	146	mask >>= 1;
	147	}
	148	done:
	149	*curr = cpu_to_be32(n);
	150	set_page_dirty(page);
	151	kunmap(page);
	152	max = offset + (curr - pptr) 32 + i - start;
	153	HFSPLUS_SB(sb).free_blocks -= *max;
	154	sb->s_dirt = 1;
	155	dprint(DBG_BITMAP, "-> %u,%u\n", start, *max);
	156	out:
1b1dcc1b	157	mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
1da177e4 LT	158	return start;
	159	}
	160
	161	int hfsplus_block_free(struct super_block *sb, u32 offset, u32 count)
	162	{
	163	struct page *page;
	164	struct address_space *mapping;
	165	__be32 pptr, curr, *end;
	166	u32 mask, len, pnr;
	167	int i;
	168
	169	/* is there any actual work to be done? */
	170	if (!count)
	171	return 0;
	172
	173	dprint(DBG_BITMAP, "block_free: %u,%u\n", offset, count);
	174	/* are all of the bits in range? */
	175	if ((offset + count) > HFSPLUS_SB(sb).total_blocks)
	176	return -2;
	177
1b1dcc1b	178	mutex_lock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
1da177e4 LT	179	mapping = HFSPLUS_SB(sb).alloc_file->i_mapping;
1da177e4 LT	180	pnr = offset / PAGE_CACHE_BITS;
090d2b18	181	page = read_mapping_page(mapping, pnr, NULL);
1da177e4 LT	182	pptr = kmap(page);
	183	curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
	184	end = pptr + PAGE_CACHE_BITS / 32;
	185	len = count;
	186
	187	/* do any partial u32 at the start */
	188	i = offset % 32;
	189	if (i) {
	190	int j = 32 - i;
	191	mask = 0xffffffffU << j;
	192	if (j > count) {
	193	mask \|= 0xffffffffU >> (i + count);
	194	*curr++ &= cpu_to_be32(mask);
	195	goto out;
	196	}
	197	*curr++ &= cpu_to_be32(mask);
	198	count -= j;
	199	}
	200
	201	/* do full u32s */
	202	while (1) {
	203	while (curr < end) {
	204	if (count < 32)
	205	goto done;
	206	*curr++ = 0;
	207	count -= 32;
	208	}
	209	if (!count)
	210	break;
	211	set_page_dirty(page);
	212	kunmap(page);
090d2b18	213	page = read_mapping_page(mapping, ++pnr, NULL);
1da177e4 LT	214	pptr = kmap(page);
	215	curr = pptr;
	216	end = pptr + PAGE_CACHE_BITS / 32;
	217	}
	218	done:
	219	/* do any partial u32 at end */
	220	if (count) {
	221	mask = 0xffffffffU >> count;
	222	*curr &= cpu_to_be32(mask);
	223	}
	224	out:
	225	set_page_dirty(page);
	226	kunmap(page);
	227	HFSPLUS_SB(sb).free_blocks += len;
	228	sb->s_dirt = 1;
1b1dcc1b	229	mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
1da177e4 LT	230
	231	return 0;
	232	}