fs/hfs/bitmap.c

   1 /*
   2  *  linux/fs/hfs/bitmap.c
   3  *
   4  * Copyright (C) 1996-1997  Paul H. Hargrove
   5  * (C) 2003 Ardis Technologies <roman@ardistech.com>
   6  * This file may be distributed under the terms of the GNU General Public License.
   7  *
   8  * Based on GPLed code Copyright (C) 1995  Michael Dreher
   9  *
  10  * This file contains the code to modify the volume bitmap:
  11  * search/set/clear bits.
  12  */
  13
  14 #include "hfs_fs.h"
  15
  16 /*
  17  * hfs_find_zero_bit()
  18  *
  19  * Description:
  20  *  Given a block of memory, its length in bits, and a starting bit number,
  21  *  determine the number of the first zero bits (in left-to-right ordering)
  22  *  in that range.
  23  *
  24  *  Returns >= 'size' if no zero bits are found in the range.
  25  *
  26  *  Accesses memory in 32-bit aligned chunks of 32-bits and thus
  27  *  may read beyond the 'size'th bit.
  28  */
  29 static u32 hfs_find_set_zero_bits(__be32 *bitmap, u32 size, u32 offset, u32 *max)
  30 {
  31         __be32 *curr, *end;
  32         u32 mask, start, len, n;
  33         __be32 val;
  34         int i;
  35
  36         len = *max;
  37         if (!len)
  38                 return size;
  39
  40         curr = bitmap + (offset / 32);
  41         end = bitmap + ((size + 31) / 32);
  42
  43         /* scan the first partial u32 for zero bits */
  44         val = *curr;
  45         if (~val) {
  46                 n = be32_to_cpu(val);
  47                 i = offset % 32;
  48                 mask = (1U << 31) >> i;
  49                 for (; i < 32; mask >>= 1, i++) {
  50                         if (!(n & mask))
  51                                 goto found;
  52                 }
  53         }
  54
  55         /* scan complete u32s for the first zero bit */
  56         while (++curr < end) {
  57                 val = *curr;
  58                 if (~val) {
  59                         n = be32_to_cpu(val);
  60                         mask = 1 << 31;
  61                         for (i = 0; i < 32; mask >>= 1, i++) {
  62                                 if (!(n & mask))
  63                                         goto found;
  64                         }
  65                 }
  66         }
  67         return size;
  68
  69 found:
  70         start = (curr - bitmap) * 32 + i;
  71         if (start >= size)
  72                 return start;
  73         /* do any partial u32 at the start */
  74         len = min(size - start, len);
  75         while (1) {
  76                 n |= mask;
  77                 if (++i >= 32)
  78                         break;
  79                 mask >>= 1;
  80                 if (!--len || n & mask)
  81                         goto done;
  82         }
  83         if (!--len)
  84                 goto done;
  85         *curr++ = cpu_to_be32(n);
  86         /* do full u32s */
  87         while (1) {
  88                 n = be32_to_cpu(*curr);
  89                 if (len < 32)
  90                         break;
  91                 if (n) {
  92                         len = 32;
  93                         break;
  94                 }
  95                 *curr++ = cpu_to_be32(0xffffffff);
  96                 len -= 32;
  97         }
  98         /* do any partial u32 at end */
  99         mask = 1U << 31;
 100         for (i = 0; i < len; i++) {
 101                 if (n & mask)
 102                         break;
 103                 n |= mask;
 104                 mask >>= 1;
 105         }
 106 done:
 107         *curr = cpu_to_be32(n);
 108         *max = (curr - bitmap) * 32 + i - start;
 109         return start;
 110 }
 111
 112 /*
 113  * hfs_vbm_search_free()
 114  *
 115  * Description:
 116  *   Search for 'num_bits' consecutive cleared bits in the bitmap blocks of
 117  *   the hfs MDB. 'mdb' had better be locked or the returned range
 118  *   may be no longer free, when this functions returns!
 119  *   XXX Currently the search starts from bit 0, but it should start with
 120  *   the bit number stored in 's_alloc_ptr' of the MDB.
 121  * Input Variable(s):
 122  *   struct hfs_mdb *mdb: Pointer to the hfs MDB
 123  *   u16 *num_bits: Pointer to the number of cleared bits
 124  *     to search for
 125  * Output Variable(s):
 126  *   u16 *num_bits: The number of consecutive clear bits of the
 127  *     returned range. If the bitmap is fragmented, this will be less than
 128  *     requested and it will be zero, when the disk is full.
 129  * Returns:
 130  *   The number of the first bit of the range of cleared bits which has been
 131  *   found. When 'num_bits' is zero, this is invalid!
 132  * Preconditions:
 133  *   'mdb' points to a "valid" (struct hfs_mdb).
 134  *   'num_bits' points to a variable of type (u16), which contains
 135  *      the number of cleared bits to find.
 136  * Postconditions:
 137  *   'num_bits' is set to the length of the found sequence.
 138  */
 139 u32 hfs_vbm_search_free(struct super_block *sb, u32 goal, u32 *num_bits)
 140 {
 141         void *bitmap;
 142         u32 pos;
 143
 144         /* make sure we have actual work to perform */
 145         if (!*num_bits)
 146                 return 0;
 147
 148         mutex_lock(&HFS_SB(sb)->bitmap_lock);
 149         bitmap = HFS_SB(sb)->bitmap;
 150
 151         pos = hfs_find_set_zero_bits(bitmap, HFS_SB(sb)->fs_ablocks, goal, num_bits);
 152         if (pos >= HFS_SB(sb)->fs_ablocks) {
 153                 if (goal)
 154                         pos = hfs_find_set_zero_bits(bitmap, goal, 0, num_bits);
 155                 if (pos >= HFS_SB(sb)->fs_ablocks) {
 156                         *num_bits = pos = 0;
 157                         goto out;
 158                 }
 159         }
 160
 161         hfs_dbg(BITMAP, "alloc_bits: %u,%u\n", pos, *num_bits);
 162         HFS_SB(sb)->free_ablocks -= *num_bits;
 163         hfs_bitmap_dirty(sb);
 164 out:
 165         mutex_unlock(&HFS_SB(sb)->bitmap_lock);
 166         return pos;
 167 }
 168
 169
 170 /*
 171  * hfs_clear_vbm_bits()
 172  *
 173  * Description:
 174  *   Clear the requested bits in the volume bitmap of the hfs filesystem
 175  * Input Variable(s):
 176  *   struct hfs_mdb *mdb: Pointer to the hfs MDB
 177  *   u16 start: The offset of the first bit
 178  *   u16 count: The number of bits
 179  * Output Variable(s):
 180  *   None
 181  * Returns:
 182  *    0: no error
 183  *   -1: One of the bits was already clear.  This is a strange
 184  *       error and when it happens, the filesystem must be repaired!
 185  *   -2: One or more of the bits are out of range of the bitmap.
 186  * Preconditions:
 187  *   'mdb' points to a "valid" (struct hfs_mdb).
 188  * Postconditions:
 189  *   Starting with bit number 'start', 'count' bits in the volume bitmap
 190  *   are cleared. The affected bitmap blocks are marked "dirty", the free
 191  *   block count of the MDB is updated and the MDB is marked dirty.
 192  */
 193 int hfs_clear_vbm_bits(struct super_block *sb, u16 start, u16 count)
 194 {
 195         __be32 *curr;
 196         u32 mask;
 197         int i, len;
 198
 199         /* is there any actual work to be done? */
 200         if (!count)
 201                 return 0;
 202
 203         hfs_dbg(BITMAP, "clear_bits: %u,%u\n", start, count);
 204         /* are all of the bits in range? */
 205         if ((start + count) > HFS_SB(sb)->fs_ablocks)
 206                 return -2;
 207
 208         mutex_lock(&HFS_SB(sb)->bitmap_lock);
 209         /* bitmap is always on a 32-bit boundary */
 210         curr = HFS_SB(sb)->bitmap + (start / 32);
 211         len = count;
 212
 213         /* do any partial u32 at the start */
 214         i = start % 32;
 215         if (i) {
 216                 int j = 32 - i;
 217                 mask = 0xffffffffU << j;
 218                 if (j > count) {
 219                         mask |= 0xffffffffU >> (i + count);
 220                         *curr &= cpu_to_be32(mask);
 221                         goto out;
 222                 }
 223                 *curr++ &= cpu_to_be32(mask);
 224                 count -= j;
 225         }
 226
 227         /* do full u32s */
 228         while (count >= 32) {
 229                 *curr++ = 0;
 230                 count -= 32;
 231         }
 232         /* do any partial u32 at end */
 233         if (count) {
 234                 mask = 0xffffffffU >> count;
 235                 *curr &= cpu_to_be32(mask);
 236         }
 237 out:
 238         HFS_SB(sb)->free_ablocks += len;
 239         mutex_unlock(&HFS_SB(sb)->bitmap_lock);
 240         hfs_bitmap_dirty(sb);
 241
 242         return 0;
 243 }