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 112u32 hfs_vbm_search_free(struct super_block *sb, u32 goal, u32 *num_bits) 113{ 114 void *bitmap; 115 u32 pos; 116 117 /* make sure we have actual work to perform */ 118 if (!*num_bits) 119 return 0; 120 121 down(&HFS_SB(sb)->bitmap_lock); 122 bitmap = HFS_SB(sb)->bitmap; 123 124 pos = hfs_find_set_zero_bits(bitmap, HFS_SB(sb)->fs_ablocks, goal, num_bits); 125 if (pos >= HFS_SB(sb)->fs_ablocks) { 126 if (goal) 127 pos = hfs_find_set_zero_bits(bitmap, goal, 0, num_bits); 128 if (pos >= HFS_SB(sb)->fs_ablocks) { 129 *num_bits = pos = 0; 130 goto out; 131 } 132 } 133 134 dprint(DBG_BITMAP, "alloc_bits: %u,%u\n", pos, *num_bits); 135 HFS_SB(sb)->free_ablocks -= *num_bits; 136 hfs_bitmap_dirty(sb); 137out: 138 up(&HFS_SB(sb)->bitmap_lock); 139 return pos; 140} 141 142 143/* 144 * hfs_clear_vbm_bits() 145 * 146 * Description: 147 * Clear the requested bits in the volume bitmap of the hfs filesystem 148 * Input Variable(s): 149 * struct hfs_mdb *mdb: Pointer to the hfs MDB 150 * u16 start: The offset of the first bit 151 * u16 count: The number of bits 152 * Output Variable(s): 153 * None 154 * Returns: 155 * 0: no error 156 * -1: One of the bits was already clear. This is a strange 157 * error and when it happens, the filesystem must be repaired! 158 * -2: One or more of the bits are out of range of the bitmap. 159 * Preconditions: 160 * 'mdb' points to a "valid" (struct hfs_mdb). 161 * Postconditions: 162 * Starting with bit number 'start', 'count' bits in the volume bitmap 163 * are cleared. The affected bitmap blocks are marked "dirty", the free 164 * block count of the MDB is updated and the MDB is marked dirty. 165 */ 166int hfs_clear_vbm_bits(struct super_block *sb, u16 start, u16 count) 167{ 168 __be32 *curr; 169 u32 mask; 170 int i, len; 171 172 /* is there any actual work to be done? */ 173 if (!count) 174 return 0; 175 176 dprint(DBG_BITMAP, "clear_bits: %u,%u\n", start, count); 177 /* are all of the bits in range? */ 178 if ((start + count) > HFS_SB(sb)->fs_ablocks) 179 return -2; 180 181 down(&HFS_SB(sb)->bitmap_lock); 182 /* bitmap is always on a 32-bit boundary */ 183 curr = HFS_SB(sb)->bitmap + (start / 32); 184 len = count; 185 186 /* do any partial u32 at the start */ 187 i = start % 32; 188 if (i) { 189 int j = 32 - i; 190 mask = 0xffffffffU << j; 191 if (j > count) { 192 mask |= 0xffffffffU >> (i + count); 193 *curr &= cpu_to_be32(mask); 194 goto out; 195 } 196 *curr++ &= cpu_to_be32(mask); 197 count -= j; 198 } 199 200 /* do full u32s */ 201 while (count >= 32) { 202 *curr++ = 0; 203 count -= 32; 204 } 205 /* do any partial u32 at end */ 206 if (count) { 207 mask = 0xffffffffU >> count; 208 *curr &= cpu_to_be32(mask); 209 } 210out: 211 HFS_SB(sb)->free_ablocks += len; 212 up(&HFS_SB(sb)->bitmap_lock); 213 hfs_bitmap_dirty(sb); 214 215 return 0; 216} 217