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