linux/fs/hfs/bitmap.c
<<
>>
Prefs
   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 */
  29static 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
  69found:
  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        }
 106done:
 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 */
 139u32 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        dprint(DBG_BITMAP, "alloc_bits: %u,%u\n", pos, *num_bits);
 162        HFS_SB(sb)->free_ablocks -= *num_bits;
 163        hfs_bitmap_dirty(sb);
 164out:
 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 */
 193int 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        dprint(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        }
 237out:
 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}
 244
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.