11da177e4SLinus Torvalds /*
21da177e4SLinus Torvalds * linux/fs/hfs/bitmap.c
31da177e4SLinus Torvalds *
41da177e4SLinus Torvalds * Copyright (C) 1996-1997 Paul H. Hargrove
51da177e4SLinus Torvalds * (C) 2003 Ardis Technologies <roman@ardistech.com>
61da177e4SLinus Torvalds * This file may be distributed under the terms of the GNU General Public License.
71da177e4SLinus Torvalds *
81da177e4SLinus Torvalds * Based on GPLed code Copyright (C) 1995 Michael Dreher
91da177e4SLinus Torvalds *
101da177e4SLinus Torvalds * This file contains the code to modify the volume bitmap:
111da177e4SLinus Torvalds * search/set/clear bits.
121da177e4SLinus Torvalds */
131da177e4SLinus Torvalds
141da177e4SLinus Torvalds #include "hfs_fs.h"
151da177e4SLinus Torvalds
161da177e4SLinus Torvalds /*
171da177e4SLinus Torvalds * hfs_find_zero_bit()
181da177e4SLinus Torvalds *
191da177e4SLinus Torvalds * Description:
201da177e4SLinus Torvalds * Given a block of memory, its length in bits, and a starting bit number,
211da177e4SLinus Torvalds * determine the number of the first zero bits (in left-to-right ordering)
221da177e4SLinus Torvalds * in that range.
231da177e4SLinus Torvalds *
241da177e4SLinus Torvalds * Returns >= 'size' if no zero bits are found in the range.
251da177e4SLinus Torvalds *
261da177e4SLinus Torvalds * Accesses memory in 32-bit aligned chunks of 32-bits and thus
271da177e4SLinus Torvalds * may read beyond the 'size'th bit.
281da177e4SLinus Torvalds */
hfs_find_set_zero_bits(__be32 * bitmap,u32 size,u32 offset,u32 * max)291da177e4SLinus Torvalds static u32 hfs_find_set_zero_bits(__be32 *bitmap, u32 size, u32 offset, u32 *max)
301da177e4SLinus Torvalds {
311da177e4SLinus Torvalds __be32 *curr, *end;
321da177e4SLinus Torvalds u32 mask, start, len, n;
331da177e4SLinus Torvalds __be32 val;
341da177e4SLinus Torvalds int i;
351da177e4SLinus Torvalds
361da177e4SLinus Torvalds len = *max;
371da177e4SLinus Torvalds if (!len)
381da177e4SLinus Torvalds return size;
391da177e4SLinus Torvalds
401da177e4SLinus Torvalds curr = bitmap + (offset / 32);
411da177e4SLinus Torvalds end = bitmap + ((size + 31) / 32);
421da177e4SLinus Torvalds
431da177e4SLinus Torvalds /* scan the first partial u32 for zero bits */
441da177e4SLinus Torvalds val = *curr;
451da177e4SLinus Torvalds if (~val) {
461da177e4SLinus Torvalds n = be32_to_cpu(val);
471da177e4SLinus Torvalds i = offset % 32;
481da177e4SLinus Torvalds mask = (1U << 31) >> i;
491da177e4SLinus Torvalds for (; i < 32; mask >>= 1, i++) {
501da177e4SLinus Torvalds if (!(n & mask))
511da177e4SLinus Torvalds goto found;
521da177e4SLinus Torvalds }
531da177e4SLinus Torvalds }
541da177e4SLinus Torvalds
551da177e4SLinus Torvalds /* scan complete u32s for the first zero bit */
561da177e4SLinus Torvalds while (++curr < end) {
571da177e4SLinus Torvalds val = *curr;
581da177e4SLinus Torvalds if (~val) {
591da177e4SLinus Torvalds n = be32_to_cpu(val);
601da177e4SLinus Torvalds mask = 1 << 31;
611da177e4SLinus Torvalds for (i = 0; i < 32; mask >>= 1, i++) {
621da177e4SLinus Torvalds if (!(n & mask))
631da177e4SLinus Torvalds goto found;
641da177e4SLinus Torvalds }
651da177e4SLinus Torvalds }
661da177e4SLinus Torvalds }
671da177e4SLinus Torvalds return size;
681da177e4SLinus Torvalds
691da177e4SLinus Torvalds found:
701da177e4SLinus Torvalds start = (curr - bitmap) * 32 + i;
711da177e4SLinus Torvalds if (start >= size)
721da177e4SLinus Torvalds return start;
731da177e4SLinus Torvalds /* do any partial u32 at the start */
741da177e4SLinus Torvalds len = min(size - start, len);
751da177e4SLinus Torvalds while (1) {
761da177e4SLinus Torvalds n |= mask;
771da177e4SLinus Torvalds if (++i >= 32)
781da177e4SLinus Torvalds break;
791da177e4SLinus Torvalds mask >>= 1;
801da177e4SLinus Torvalds if (!--len || n & mask)
811da177e4SLinus Torvalds goto done;
821da177e4SLinus Torvalds }
831da177e4SLinus Torvalds if (!--len)
841da177e4SLinus Torvalds goto done;
851da177e4SLinus Torvalds *curr++ = cpu_to_be32(n);
861da177e4SLinus Torvalds /* do full u32s */
871da177e4SLinus Torvalds while (1) {
881da177e4SLinus Torvalds n = be32_to_cpu(*curr);
891da177e4SLinus Torvalds if (len < 32)
901da177e4SLinus Torvalds break;
911da177e4SLinus Torvalds if (n) {
921da177e4SLinus Torvalds len = 32;
931da177e4SLinus Torvalds break;
941da177e4SLinus Torvalds }
951da177e4SLinus Torvalds *curr++ = cpu_to_be32(0xffffffff);
961da177e4SLinus Torvalds len -= 32;
971da177e4SLinus Torvalds }
981da177e4SLinus Torvalds /* do any partial u32 at end */
991da177e4SLinus Torvalds mask = 1U << 31;
1001da177e4SLinus Torvalds for (i = 0; i < len; i++) {
1011da177e4SLinus Torvalds if (n & mask)
1021da177e4SLinus Torvalds break;
1031da177e4SLinus Torvalds n |= mask;
1041da177e4SLinus Torvalds mask >>= 1;
1051da177e4SLinus Torvalds }
1061da177e4SLinus Torvalds done:
1071da177e4SLinus Torvalds *curr = cpu_to_be32(n);
1081da177e4SLinus Torvalds *max = (curr - bitmap) * 32 + i - start;
1091da177e4SLinus Torvalds return start;
1101da177e4SLinus Torvalds }
1111da177e4SLinus Torvalds
1121da177e4SLinus Torvalds /*
1131da177e4SLinus Torvalds * hfs_vbm_search_free()
1141da177e4SLinus Torvalds *
1151da177e4SLinus Torvalds * Description:
1161da177e4SLinus Torvalds * Search for 'num_bits' consecutive cleared bits in the bitmap blocks of
1171da177e4SLinus Torvalds * the hfs MDB. 'mdb' had better be locked or the returned range
1181da177e4SLinus Torvalds * may be no longer free, when this functions returns!
1191da177e4SLinus Torvalds * XXX Currently the search starts from bit 0, but it should start with
1201da177e4SLinus Torvalds * the bit number stored in 's_alloc_ptr' of the MDB.
1211da177e4SLinus Torvalds * Input Variable(s):
1221da177e4SLinus Torvalds * struct hfs_mdb *mdb: Pointer to the hfs MDB
1231da177e4SLinus Torvalds * u16 *num_bits: Pointer to the number of cleared bits
1241da177e4SLinus Torvalds * to search for
1251da177e4SLinus Torvalds * Output Variable(s):
1261da177e4SLinus Torvalds * u16 *num_bits: The number of consecutive clear bits of the
1271da177e4SLinus Torvalds * returned range. If the bitmap is fragmented, this will be less than
1281da177e4SLinus Torvalds * requested and it will be zero, when the disk is full.
1291da177e4SLinus Torvalds * Returns:
1301da177e4SLinus Torvalds * The number of the first bit of the range of cleared bits which has been
1311da177e4SLinus Torvalds * found. When 'num_bits' is zero, this is invalid!
1321da177e4SLinus Torvalds * Preconditions:
1331da177e4SLinus Torvalds * 'mdb' points to a "valid" (struct hfs_mdb).
1341da177e4SLinus Torvalds * 'num_bits' points to a variable of type (u16), which contains
1351da177e4SLinus Torvalds * the number of cleared bits to find.
1361da177e4SLinus Torvalds * Postconditions:
1371da177e4SLinus Torvalds * 'num_bits' is set to the length of the found sequence.
1381da177e4SLinus Torvalds */
hfs_vbm_search_free(struct super_block * sb,u32 goal,u32 * num_bits)1391da177e4SLinus Torvalds u32 hfs_vbm_search_free(struct super_block *sb, u32 goal, u32 *num_bits)
1401da177e4SLinus Torvalds {
1411da177e4SLinus Torvalds void *bitmap;
1421da177e4SLinus Torvalds u32 pos;
1431da177e4SLinus Torvalds
1441da177e4SLinus Torvalds /* make sure we have actual work to perform */
1451da177e4SLinus Torvalds if (!*num_bits)
1461da177e4SLinus Torvalds return 0;
1471da177e4SLinus Torvalds
1483084b72dSMatthias Kaehlcke mutex_lock(&HFS_SB(sb)->bitmap_lock);
1491da177e4SLinus Torvalds bitmap = HFS_SB(sb)->bitmap;
1501da177e4SLinus Torvalds
1511da177e4SLinus Torvalds pos = hfs_find_set_zero_bits(bitmap, HFS_SB(sb)->fs_ablocks, goal, num_bits);
1521da177e4SLinus Torvalds if (pos >= HFS_SB(sb)->fs_ablocks) {
1531da177e4SLinus Torvalds if (goal)
1541da177e4SLinus Torvalds pos = hfs_find_set_zero_bits(bitmap, goal, 0, num_bits);
1551da177e4SLinus Torvalds if (pos >= HFS_SB(sb)->fs_ablocks) {
1561da177e4SLinus Torvalds *num_bits = pos = 0;
1571da177e4SLinus Torvalds goto out;
1581da177e4SLinus Torvalds }
1591da177e4SLinus Torvalds }
1601da177e4SLinus Torvalds
161c2b3e1f7SJoe Perches hfs_dbg(BITMAP, "alloc_bits: %u,%u\n", pos, *num_bits);
1621da177e4SLinus Torvalds HFS_SB(sb)->free_ablocks -= *num_bits;
1631da177e4SLinus Torvalds hfs_bitmap_dirty(sb);
1641da177e4SLinus Torvalds out:
1653084b72dSMatthias Kaehlcke mutex_unlock(&HFS_SB(sb)->bitmap_lock);
1661da177e4SLinus Torvalds return pos;
1671da177e4SLinus Torvalds }
1681da177e4SLinus Torvalds
1691da177e4SLinus Torvalds
1701da177e4SLinus Torvalds /*
1711da177e4SLinus Torvalds * hfs_clear_vbm_bits()
1721da177e4SLinus Torvalds *
1731da177e4SLinus Torvalds * Description:
1741da177e4SLinus Torvalds * Clear the requested bits in the volume bitmap of the hfs filesystem
1751da177e4SLinus Torvalds * Input Variable(s):
1761da177e4SLinus Torvalds * struct hfs_mdb *mdb: Pointer to the hfs MDB
1771da177e4SLinus Torvalds * u16 start: The offset of the first bit
1781da177e4SLinus Torvalds * u16 count: The number of bits
1791da177e4SLinus Torvalds * Output Variable(s):
1801da177e4SLinus Torvalds * None
1811da177e4SLinus Torvalds * Returns:
1821da177e4SLinus Torvalds * 0: no error
1831da177e4SLinus Torvalds * -1: One of the bits was already clear. This is a strange
1841da177e4SLinus Torvalds * error and when it happens, the filesystem must be repaired!
1851da177e4SLinus Torvalds * -2: One or more of the bits are out of range of the bitmap.
1861da177e4SLinus Torvalds * Preconditions:
1871da177e4SLinus Torvalds * 'mdb' points to a "valid" (struct hfs_mdb).
1881da177e4SLinus Torvalds * Postconditions:
1891da177e4SLinus Torvalds * Starting with bit number 'start', 'count' bits in the volume bitmap
1901da177e4SLinus Torvalds * are cleared. The affected bitmap blocks are marked "dirty", the free
1911da177e4SLinus Torvalds * block count of the MDB is updated and the MDB is marked dirty.
1921da177e4SLinus Torvalds */
hfs_clear_vbm_bits(struct super_block * sb,u16 start,u16 count)1931da177e4SLinus Torvalds int hfs_clear_vbm_bits(struct super_block *sb, u16 start, u16 count)
1941da177e4SLinus Torvalds {
1951da177e4SLinus Torvalds __be32 *curr;
1961da177e4SLinus Torvalds u32 mask;
1971da177e4SLinus Torvalds int i, len;
1981da177e4SLinus Torvalds
1991da177e4SLinus Torvalds /* is there any actual work to be done? */
2001da177e4SLinus Torvalds if (!count)
2011da177e4SLinus Torvalds return 0;
2021da177e4SLinus Torvalds
203c2b3e1f7SJoe Perches hfs_dbg(BITMAP, "clear_bits: %u,%u\n", start, count);
2041da177e4SLinus Torvalds /* are all of the bits in range? */
2051da177e4SLinus Torvalds if ((start + count) > HFS_SB(sb)->fs_ablocks)
2061da177e4SLinus Torvalds return -2;
2071da177e4SLinus Torvalds
2083084b72dSMatthias Kaehlcke mutex_lock(&HFS_SB(sb)->bitmap_lock);
2091da177e4SLinus Torvalds /* bitmap is always on a 32-bit boundary */
2101da177e4SLinus Torvalds curr = HFS_SB(sb)->bitmap + (start / 32);
2111da177e4SLinus Torvalds len = count;
2121da177e4SLinus Torvalds
2131da177e4SLinus Torvalds /* do any partial u32 at the start */
2141da177e4SLinus Torvalds i = start % 32;
2151da177e4SLinus Torvalds if (i) {
2161da177e4SLinus Torvalds int j = 32 - i;
2171da177e4SLinus Torvalds mask = 0xffffffffU << j;
2181da177e4SLinus Torvalds if (j > count) {
2191da177e4SLinus Torvalds mask |= 0xffffffffU >> (i + count);
2201da177e4SLinus Torvalds *curr &= cpu_to_be32(mask);
2211da177e4SLinus Torvalds goto out;
2221da177e4SLinus Torvalds }
2231da177e4SLinus Torvalds *curr++ &= cpu_to_be32(mask);
2241da177e4SLinus Torvalds count -= j;
2251da177e4SLinus Torvalds }
2261da177e4SLinus Torvalds
2271da177e4SLinus Torvalds /* do full u32s */
2281da177e4SLinus Torvalds while (count >= 32) {
2291da177e4SLinus Torvalds *curr++ = 0;
2301da177e4SLinus Torvalds count -= 32;
2311da177e4SLinus Torvalds }
2321da177e4SLinus Torvalds /* do any partial u32 at end */
2331da177e4SLinus Torvalds if (count) {
2341da177e4SLinus Torvalds mask = 0xffffffffU >> count;
2351da177e4SLinus Torvalds *curr &= cpu_to_be32(mask);
2361da177e4SLinus Torvalds }
2371da177e4SLinus Torvalds out:
2381da177e4SLinus Torvalds HFS_SB(sb)->free_ablocks += len;
2393084b72dSMatthias Kaehlcke mutex_unlock(&HFS_SB(sb)->bitmap_lock);
2401da177e4SLinus Torvalds hfs_bitmap_dirty(sb);
2411da177e4SLinus Torvalds
2421da177e4SLinus Torvalds return 0;
2431da177e4SLinus Torvalds }
244