fs/hfs/bitmap.c

0001 /*
0002  *  linux/fs/hfs/bitmap.c
0003  *
0004  * Copyright (C) 1996-1997  Paul H. Hargrove
0005  * (C) 2003 Ardis Technologies <roman@ardistech.com>
0006  * This file may be distributed under the terms of the GNU General Public License.
0007  *
0008  * Based on GPLed code Copyright (C) 1995  Michael Dreher
0009  *
0010  * This file contains the code to modify the volume bitmap:
0011  * search/set/clear bits.
0012  */
0013
0014 #include "hfs_fs.h"
0015
0016 /*
0017  * hfs_find_zero_bit()
0018  *
0019  * Description:
0020  *  Given a block of memory, its length in bits, and a starting bit number,
0021  *  determine the number of the first zero bits (in left-to-right ordering)
0022  *  in that range.
0023  *
0024  *  Returns >= 'size' if no zero bits are found in the range.
0025  *
0026  *  Accesses memory in 32-bit aligned chunks of 32-bits and thus
0027  *  may read beyond the 'size'th bit.
0028  */
0029 static u32 hfs_find_set_zero_bits(__be32 *bitmap, u32 size, u32 offset, u32 *max)
0030 {
0031     __be32 *curr, *end;
0032     u32 mask, start, len, n;
0033     __be32 val;
0034     int i;
0035
0036     len = *max;
0037     if (!len)
0038         return size;
0039
0040     curr = bitmap + (offset / 32);
0041     end = bitmap + ((size + 31) / 32);
0042
0043     /* scan the first partial u32 for zero bits */
0044     val = *curr;
0045     if (~val) {
0046         n = be32_to_cpu(val);
0047         i = offset % 32;
0048         mask = (1U << 31) >> i;
0049         for (; i < 32; mask >>= 1, i++) {
0050             if (!(n & mask))
0051                 goto found;
0052         }
0053     }
0054
0055     /* scan complete u32s for the first zero bit */
0056     while (++curr < end) {
0057         val = *curr;
0058         if (~val) {
0059             n = be32_to_cpu(val);
0060             mask = 1 << 31;
0061             for (i = 0; i < 32; mask >>= 1, i++) {
0062                 if (!(n & mask))
0063                     goto found;
0064             }
0065         }
0066     }
0067     return size;
0068
0069 found:
0070     start = (curr - bitmap) * 32 + i;
0071     if (start >= size)
0072         return start;
0073     /* do any partial u32 at the start */
0074     len = min(size - start, len);
0075     while (1) {
0076         n |= mask;
0077         if (++i >= 32)
0078             break;
0079         mask >>= 1;
0080         if (!--len || n & mask)
0081             goto done;
0082     }
0083     if (!--len)
0084         goto done;
0085     *curr++ = cpu_to_be32(n);
0086     /* do full u32s */
0087     while (1) {
0088         n = be32_to_cpu(*curr);
0089         if (len < 32)
0090             break;
0091         if (n) {
0092             len = 32;
0093             break;
0094         }
0095         *curr++ = cpu_to_be32(0xffffffff);
0096         len -= 32;
0097     }
0098     /* do any partial u32 at end */
0099     mask = 1U << 31;
0100     for (i = 0; i < len; i++) {
0101         if (n & mask)
0102             break;
0103         n |= mask;
0104         mask >>= 1;
0105     }
0106 done:
0107     *curr = cpu_to_be32(n);
0108     *max = (curr - bitmap) * 32 + i - start;
0109     return start;
0110 }
0111
0112 /*
0113  * hfs_vbm_search_free()
0114  *
0115  * Description:
0116  *   Search for 'num_bits' consecutive cleared bits in the bitmap blocks of
0117  *   the hfs MDB. 'mdb' had better be locked or the returned range
0118  *   may be no longer free, when this functions returns!
0119  *   XXX Currently the search starts from bit 0, but it should start with
0120  *   the bit number stored in 's_alloc_ptr' of the MDB.
0121  * Input Variable(s):
0122  *   struct hfs_mdb *mdb: Pointer to the hfs MDB
0123  *   u16 *num_bits: Pointer to the number of cleared bits
0124  *     to search for
0125  * Output Variable(s):
0126  *   u16 *num_bits: The number of consecutive clear bits of the
0127  *     returned range. If the bitmap is fragmented, this will be less than
0128  *     requested and it will be zero, when the disk is full.
0129  * Returns:
0130  *   The number of the first bit of the range of cleared bits which has been
0131  *   found. When 'num_bits' is zero, this is invalid!
0132  * Preconditions:
0133  *   'mdb' points to a "valid" (struct hfs_mdb).
0134  *   'num_bits' points to a variable of type (u16), which contains
0135  *  the number of cleared bits to find.
0136  * Postconditions:
0137  *   'num_bits' is set to the length of the found sequence.
0138  */
0139 u32 hfs_vbm_search_free(struct super_block *sb, u32 goal, u32 *num_bits)
0140 {
0141     void *bitmap;
0142     u32 pos;
0143
0144     /* make sure we have actual work to perform */
0145     if (!*num_bits)
0146         return 0;
0147
0148     mutex_lock(&HFS_SB(sb)->bitmap_lock);
0149     bitmap = HFS_SB(sb)->bitmap;
0150
0151     pos = hfs_find_set_zero_bits(bitmap, HFS_SB(sb)->fs_ablocks, goal, num_bits);
0152     if (pos >= HFS_SB(sb)->fs_ablocks) {
0153         if (goal)
0154             pos = hfs_find_set_zero_bits(bitmap, goal, 0, num_bits);
0155         if (pos >= HFS_SB(sb)->fs_ablocks) {
0156             *num_bits = pos = 0;
0157             goto out;
0158         }
0159     }
0160
0161     hfs_dbg(BITMAP, "alloc_bits: %u,%u\n", pos, *num_bits);
0162     HFS_SB(sb)->free_ablocks -= *num_bits;
0163     hfs_bitmap_dirty(sb);
0164 out:
0165     mutex_unlock(&HFS_SB(sb)->bitmap_lock);
0166     return pos;
0167 }
0168
0169
0170 /*
0171  * hfs_clear_vbm_bits()
0172  *
0173  * Description:
0174  *   Clear the requested bits in the volume bitmap of the hfs filesystem
0175  * Input Variable(s):
0176  *   struct hfs_mdb *mdb: Pointer to the hfs MDB
0177  *   u16 start: The offset of the first bit
0178  *   u16 count: The number of bits
0179  * Output Variable(s):
0180  *   None
0181  * Returns:
0182  *    0: no error
0183  *   -1: One of the bits was already clear.  This is a strange
0184  *   error and when it happens, the filesystem must be repaired!
0185  *   -2: One or more of the bits are out of range of the bitmap.
0186  * Preconditions:
0187  *   'mdb' points to a "valid" (struct hfs_mdb).
0188  * Postconditions:
0189  *   Starting with bit number 'start', 'count' bits in the volume bitmap
0190  *   are cleared. The affected bitmap blocks are marked "dirty", the free
0191  *   block count of the MDB is updated and the MDB is marked dirty.
0192  */
0193 int hfs_clear_vbm_bits(struct super_block *sb, u16 start, u16 count)
0194 {
0195     __be32 *curr;
0196     u32 mask;
0197     int i, len;
0198
0199     /* is there any actual work to be done? */
0200     if (!count)
0201         return 0;
0202
0203     hfs_dbg(BITMAP, "clear_bits: %u,%u\n", start, count);
0204     /* are all of the bits in range? */
0205     if ((start + count) > HFS_SB(sb)->fs_ablocks)
0206         return -2;
0207
0208     mutex_lock(&HFS_SB(sb)->bitmap_lock);
0209     /* bitmap is always on a 32-bit boundary */
0210     curr = HFS_SB(sb)->bitmap + (start / 32);
0211     len = count;
0212
0213     /* do any partial u32 at the start */
0214     i = start % 32;
0215     if (i) {
0216         int j = 32 - i;
0217         mask = 0xffffffffU << j;
0218         if (j > count) {
0219             mask |= 0xffffffffU >> (i + count);
0220             *curr &= cpu_to_be32(mask);
0221             goto out;
0222         }
0223         *curr++ &= cpu_to_be32(mask);
0224         count -= j;
0225     }
0226
0227     /* do full u32s */
0228     while (count >= 32) {
0229         *curr++ = 0;
0230         count -= 32;
0231     }
0232     /* do any partial u32 at end */
0233     if (count) {
0234         mask = 0xffffffffU >> count;
0235         *curr &= cpu_to_be32(mask);
0236     }
0237 out:
0238     HFS_SB(sb)->free_ablocks += len;
0239     mutex_unlock(&HFS_SB(sb)->bitmap_lock);
0240     hfs_bitmap_dirty(sb);
0241
0242     return 0;
0243 }