Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
Matthias Kaehlcke | 3084b72 | 2008-07-25 01:46:34 -0700 | [diff] [blame] | 148 | mutex_lock(&HFS_SB(sb)->bitmap_lock); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
Joe Perches | c2b3e1f | 2013-04-30 15:27:54 -0700 | [diff] [blame^] | 161 | hfs_dbg(BITMAP, "alloc_bits: %u,%u\n", pos, *num_bits); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 162 | HFS_SB(sb)->free_ablocks -= *num_bits; |
| 163 | hfs_bitmap_dirty(sb); |
| 164 | out: |
Matthias Kaehlcke | 3084b72 | 2008-07-25 01:46:34 -0700 | [diff] [blame] | 165 | mutex_unlock(&HFS_SB(sb)->bitmap_lock); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
Joe Perches | c2b3e1f | 2013-04-30 15:27:54 -0700 | [diff] [blame^] | 203 | hfs_dbg(BITMAP, "clear_bits: %u,%u\n", start, count); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 204 | /* are all of the bits in range? */ |
| 205 | if ((start + count) > HFS_SB(sb)->fs_ablocks) |
| 206 | return -2; |
| 207 | |
Matthias Kaehlcke | 3084b72 | 2008-07-25 01:46:34 -0700 | [diff] [blame] | 208 | mutex_lock(&HFS_SB(sb)->bitmap_lock); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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; |
Matthias Kaehlcke | 3084b72 | 2008-07-25 01:46:34 -0700 | [diff] [blame] | 239 | mutex_unlock(&HFS_SB(sb)->bitmap_lock); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 240 | hfs_bitmap_dirty(sb); |
| 241 | |
| 242 | return 0; |
| 243 | } |