/* *  linux/fs/hfs/bitmap.c * * Copyright (C) 1996-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. * * Based on GPLed code Copyright (C) 1995  Michael Dreher * * This file contains the code to modify the volume bitmap: * search/set/clear bits. */ #include "hfs_fs.h" /* * hfs_find_zero_bit() * * Description: *  Given a block of memory, its length in bits, and a starting bit number, *  determine the number of the first zero bits (in left-to-right ordering) *  in that range. * *  Returns >= 'size' if no zero bits are found in the range. * *  Accesses memory in 32-bit aligned chunks of 32-bits and thus *  may read beyond the 'size'th bit. */static u32 hfs_find_set_zero_bits(__be32 *bitmap, u32 size, u32 offset, u32 *max){	__be32 *curr, *end;	u32 mask, start, len, n;	__be32 val;	int i; 	len = *max;	if (!len)		return size; 	curr = bitmap + (offset / 32);	end = bitmap + ((size + 31) / 32); 	/* scan the first partial u32 for zero bits */	val = *curr;	if (~val) {		n = be32_to_cpu(val);		i = offset % 32;		mask = (1U << 31) >> i;		for (; i < 32; mask >>= 1, i++) {			if (!(n & mask))				goto found;		}	} 	/* scan complete u32s for the first zero bit */	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;			}		}	}	return size; found:	start = (curr - bitmap) * 32 + i;	if (start >= size)		return start;	/* 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) {		n = be32_to_cpu(*curr);		if (len < 32)			break;		if (n) {			len = 32;			break;		}		*curr++ = cpu_to_be32(0xffffffff);		len -= 32;	}	/* 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);	*max = (curr - bitmap) * 32 + i - start;	return start;} /* * hfs_vbm_search_free() * * Description: *   Search for 'num_bits' consecutive cleared bits in the bitmap blocks of *   the hfs MDB. 'mdb' had better be locked or the returned range *   may be no longer free, when this functions returns! *   XXX Currently the search starts from bit 0, but it should start with *   the bit number stored in 's_alloc_ptr' of the MDB. * Input Variable(s): *   struct hfs_mdb *mdb: Pointer to the hfs MDB *   u16 *num_bits: Pointer to the number of cleared bits *     to search for * Output Variable(s): *   u16 *num_bits: The number of consecutive clear bits of the *     returned range. If the bitmap is fragmented, this will be less than *     requested and it will be zero, when the disk is full. * Returns: *   The number of the first bit of the range of cleared bits which has been *   found. When 'num_bits' is zero, this is invalid! * Preconditions: *   'mdb' points to a "valid" (struct hfs_mdb). *   'num_bits' points to a variable of type (u16), which contains *	the number of cleared bits to find. * Postconditions: *   'num_bits' is set to the length of the found sequence. */u32 hfs_vbm_search_free(struct super_block *sb, u32 goal, u32 *num_bits){	void *bitmap;	u32 pos; 	/* make sure we have actual work to perform */	if (!*num_bits)		return 0; 	mutex_lock(&HFS_SB(sb)->bitmap_lock);	bitmap = HFS_SB(sb)->bitmap; 	pos = hfs_find_set_zero_bits(bitmap, HFS_SB(sb)->fs_ablocks, goal, num_bits);	if (pos >= HFS_SB(sb)->fs_ablocks) {		if (goal)			pos = hfs_find_set_zero_bits(bitmap, goal, 0, num_bits);		if (pos >= HFS_SB(sb)->fs_ablocks) {			*num_bits = pos = 0;			goto out;		}	} 	hfs_dbg("pos %u, num_bits %u\n", pos, *num_bits);	HFS_SB(sb)->free_ablocks -= *num_bits;	hfs_bitmap_dirty(sb);out:	mutex_unlock(&HFS_SB(sb)->bitmap_lock);	return pos;}  /* * hfs_clear_vbm_bits() * * Description: *   Clear the requested bits in the volume bitmap of the hfs filesystem * Input Variable(s): *   struct hfs_mdb *mdb: Pointer to the hfs MDB *   u16 start: The offset of the first bit *   u16 count: The number of bits * Output Variable(s): *   None * Returns: *    0: no error *   -1: One of the bits was already clear.  This is a strange *	 error and when it happens, the filesystem must be repaired! *   -2: One or more of the bits are out of range of the bitmap. * Preconditions: *   'mdb' points to a "valid" (struct hfs_mdb). * Postconditions: *   Starting with bit number 'start', 'count' bits in the volume bitmap *   are cleared. The affected bitmap blocks are marked "dirty", the free *   block count of the MDB is updated and the MDB is marked dirty. */int hfs_clear_vbm_bits(struct super_block *sb, u16 start, u16 count){	__be32 *curr;	u32 mask;	int i, len; 	/* is there any actual work to be done? */	if (!count)		return 0; 	hfs_dbg("start %u, count %u\n", start, count);	/* are all of the bits in range? */	if ((start + count) > HFS_SB(sb)->fs_ablocks)		return -2; 	mutex_lock(&HFS_SB(sb)->bitmap_lock);	/* bitmap is always on a 32-bit boundary */	curr = HFS_SB(sb)->bitmap + (start / 32);	len = count; 	/* do any partial u32 at the start */	i = start % 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 (count >= 32) {		*curr++ = 0;		count -= 32;	}	/* do any partial u32 at end */	if (count) {		mask = 0xffffffffU >> count;		*curr &= cpu_to_be32(mask);	}out:	HFS_SB(sb)->free_ablocks += len;	mutex_unlock(&HFS_SB(sb)->bitmap_lock);	hfs_bitmap_dirty(sb); 	return 0;}