[linux.git] / fs / hfsplus / bitmap.c

// SPDX-License-Identifier: GPL-2.0
/*
 *  linux/fs/hfsplus/bitmap.c
 *
 * Copyright (C) 2001
 * Brad Boyer ([email protected])
 * (C) 2003 Ardis Technologies <[email protected]>
 *
 * Handling of allocation file
 */

#include <linux/pagemap.h>

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

#define PAGE_CACHE_BITS	(PAGE_SIZE * 8)

int hfsplus_block_allocate(struct super_block *sb, u32 size,
		u32 offset, u32 *max)
{
	struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
	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;

	hfs_dbg(BITMAP, "block_allocate: %u,%u,%u\n", size, offset, len);
	mutex_lock(&sbi->alloc_mutex);
	mapping = sbi->alloc_file->i_mapping;
	page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS, NULL);
	if (IS_ERR(page)) {
		start = size;
		goto out;
	}
	pptr = kmap_local_page(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_local(pptr);
		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_local_page(page);
		if ((size ^ offset) / PAGE_CACHE_BITS)
			end = pptr + PAGE_CACHE_BITS / 32;
		else
			end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
	}
	hfs_dbg(BITMAP, "bitmap full\n");
	start = size;
	goto out;

found:
	start = offset + (curr - pptr) * 32 + i;
	if (start >= size) {
		hfs_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_local(pptr);
		offset += PAGE_CACHE_BITS;
		page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
					 NULL);
		if (IS_ERR(page)) {
			start = size;
			goto out;
		}
		pptr = kmap_local_page(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_local(pptr);
	*max = offset + (curr - pptr) * 32 + i - start;
	sbi->free_blocks -= *max;
	hfsplus_mark_mdb_dirty(sb);
	hfs_dbg(BITMAP, "-> %u,%u\n", start, *max);
out:
	mutex_unlock(&sbi->alloc_mutex);
	return start;
}

int hfsplus_block_free(struct super_block *sb, u32 offset, u32 count)
{
	struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
	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;

	hfs_dbg(BITMAP, "block_free: %u,%u\n", offset, count);
	/* are all of the bits in range? */
	if ((offset + count) > sbi->total_blocks)
		return -ENOENT;

	mutex_lock(&sbi->alloc_mutex);
	mapping = sbi->alloc_file->i_mapping;
	pnr = offset / PAGE_CACHE_BITS;
	page = read_mapping_page(mapping, pnr, NULL);
	if (IS_ERR(page))
		goto kaboom;
	pptr = kmap_local_page(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_local(pptr);
		page = read_mapping_page(mapping, ++pnr, NULL);
		if (IS_ERR(page))
			goto kaboom;
		pptr = kmap_local_page(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_local(pptr);
	sbi->free_blocks += len;
	hfsplus_mark_mdb_dirty(sb);
	mutex_unlock(&sbi->alloc_mutex);

	return 0;

kaboom:
	pr_crit("unable to mark blocks free: error %ld\n", PTR_ERR(page));
	mutex_unlock(&sbi->alloc_mutex);

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