1 /* 2 * linux/fs/affs/bitmap.c 3 * 4 * (c) 1996 Hans-Joachim Widmaier 5 * 6 * bitmap.c contains the code that handles all bitmap related stuff - 7 * block allocation, deallocation, calculation of free space. 8 */ 9 10 #include <linux/slab.h> 11 #include "affs.h" 12 13 u32 14 affs_count_free_blocks(struct super_block *sb) 15 { 16 struct affs_bm_info *bm; 17 u32 free; 18 int i; 19 20 pr_debug("%s()\n", __func__); 21 22 if (sb_rdonly(sb)) 23 return 0; 24 25 mutex_lock(&AFFS_SB(sb)->s_bmlock); 26 27 bm = AFFS_SB(sb)->s_bitmap; 28 free = 0; 29 for (i = AFFS_SB(sb)->s_bmap_count; i > 0; bm++, i--) 30 free += bm->bm_free; 31 32 mutex_unlock(&AFFS_SB(sb)->s_bmlock); 33 34 return free; 35 } 36 37 void 38 affs_free_block(struct super_block *sb, u32 block) 39 { 40 struct affs_sb_info *sbi = AFFS_SB(sb); 41 struct affs_bm_info *bm; 42 struct buffer_head *bh; 43 u32 blk, bmap, bit, mask, tmp; 44 __be32 *data; 45 46 pr_debug("%s(%u)\n", __func__, block); 47 48 if (block > sbi->s_partition_size) 49 goto err_range; 50 51 blk = block - sbi->s_reserved; 52 bmap = blk / sbi->s_bmap_bits; 53 bit = blk % sbi->s_bmap_bits; 54 bm = &sbi->s_bitmap[bmap]; 55 56 mutex_lock(&sbi->s_bmlock); 57 58 bh = sbi->s_bmap_bh; 59 if (sbi->s_last_bmap != bmap) { 60 affs_brelse(bh); 61 bh = affs_bread(sb, bm->bm_key); 62 if (!bh) 63 goto err_bh_read; 64 sbi->s_bmap_bh = bh; 65 sbi->s_last_bmap = bmap; 66 } 67 68 mask = 1 << (bit & 31); 69 data = (__be32 *)bh->b_data + bit / 32 + 1; 70 71 /* mark block free */ 72 tmp = be32_to_cpu(*data); 73 if (tmp & mask) 74 goto err_free; 75 *data = cpu_to_be32(tmp | mask); 76 77 /* fix checksum */ 78 tmp = be32_to_cpu(*(__be32 *)bh->b_data); 79 *(__be32 *)bh->b_data = cpu_to_be32(tmp - mask); 80 81 mark_buffer_dirty(bh); 82 affs_mark_sb_dirty(sb); 83 bm->bm_free++; 84 85 mutex_unlock(&sbi->s_bmlock); 86 return; 87 88 err_free: 89 affs_warning(sb,"affs_free_block","Trying to free block %u which is already free", block); 90 mutex_unlock(&sbi->s_bmlock); 91 return; 92 93 err_bh_read: 94 affs_error(sb,"affs_free_block","Cannot read bitmap block %u", bm->bm_key); 95 sbi->s_bmap_bh = NULL; 96 sbi->s_last_bmap = ~0; 97 mutex_unlock(&sbi->s_bmlock); 98 return; 99 100 err_range: 101 affs_error(sb, "affs_free_block","Block %u outside partition", block); 102 } 103 104 /* 105 * Allocate a block in the given allocation zone. 106 * Since we have to byte-swap the bitmap on little-endian 107 * machines, this is rather expensive. Therefore we will 108 * preallocate up to 16 blocks from the same word, if 109 * possible. We are not doing preallocations in the 110 * header zone, though. 111 */ 112 113 u32 114 affs_alloc_block(struct inode *inode, u32 goal) 115 { 116 struct super_block *sb; 117 struct affs_sb_info *sbi; 118 struct affs_bm_info *bm; 119 struct buffer_head *bh; 120 __be32 *data, *enddata; 121 u32 blk, bmap, bit, mask, mask2, tmp; 122 int i; 123 124 sb = inode->i_sb; 125 sbi = AFFS_SB(sb); 126 127 pr_debug("balloc(inode=%lu,goal=%u): ", inode->i_ino, goal); 128 129 if (AFFS_I(inode)->i_pa_cnt) { 130 pr_debug("%d\n", AFFS_I(inode)->i_lastalloc+1); 131 AFFS_I(inode)->i_pa_cnt--; 132 return ++AFFS_I(inode)->i_lastalloc; 133 } 134 135 if (!goal || goal > sbi->s_partition_size) { 136 if (goal) 137 affs_warning(sb, "affs_balloc", "invalid goal %d", goal); 138 //if (!AFFS_I(inode)->i_last_block) 139 // affs_warning(sb, "affs_balloc", "no last alloc block"); 140 goal = sbi->s_reserved; 141 } 142 143 blk = goal - sbi->s_reserved; 144 bmap = blk / sbi->s_bmap_bits; 145 bm = &sbi->s_bitmap[bmap]; 146 147 mutex_lock(&sbi->s_bmlock); 148 149 if (bm->bm_free) 150 goto find_bmap_bit; 151 152 find_bmap: 153 /* search for the next bmap buffer with free bits */ 154 i = sbi->s_bmap_count; 155 do { 156 if (--i < 0) 157 goto err_full; 158 bmap++; 159 bm++; 160 if (bmap < sbi->s_bmap_count) 161 continue; 162 /* restart search at zero */ 163 bmap = 0; 164 bm = sbi->s_bitmap; 165 } while (!bm->bm_free); 166 blk = bmap * sbi->s_bmap_bits; 167 168 find_bmap_bit: 169 170 bh = sbi->s_bmap_bh; 171 if (sbi->s_last_bmap != bmap) { 172 affs_brelse(bh); 173 bh = affs_bread(sb, bm->bm_key); 174 if (!bh) 175 goto err_bh_read; 176 sbi->s_bmap_bh = bh; 177 sbi->s_last_bmap = bmap; 178 } 179 180 /* find an unused block in this bitmap block */ 181 bit = blk % sbi->s_bmap_bits; 182 data = (__be32 *)bh->b_data + bit / 32 + 1; 183 enddata = (__be32 *)((u8 *)bh->b_data + sb->s_blocksize); 184 mask = ~0UL << (bit & 31); 185 blk &= ~31UL; 186 187 tmp = be32_to_cpu(*data); 188 if (tmp & mask) 189 goto find_bit; 190 191 /* scan the rest of the buffer */ 192 do { 193 blk += 32; 194 if (++data >= enddata) 195 /* didn't find something, can only happen 196 * if scan didn't start at 0, try next bmap 197 */ 198 goto find_bmap; 199 } while (!*data); 200 tmp = be32_to_cpu(*data); 201 mask = ~0; 202 203 find_bit: 204 /* finally look for a free bit in the word */ 205 bit = ffs(tmp & mask) - 1; 206 blk += bit + sbi->s_reserved; 207 mask2 = mask = 1 << (bit & 31); 208 AFFS_I(inode)->i_lastalloc = blk; 209 210 /* prealloc as much as possible within this word */ 211 while ((mask2 <<= 1)) { 212 if (!(tmp & mask2)) 213 break; 214 AFFS_I(inode)->i_pa_cnt++; 215 mask |= mask2; 216 } 217 bm->bm_free -= AFFS_I(inode)->i_pa_cnt + 1; 218 219 *data = cpu_to_be32(tmp & ~mask); 220 221 /* fix checksum */ 222 tmp = be32_to_cpu(*(__be32 *)bh->b_data); 223 *(__be32 *)bh->b_data = cpu_to_be32(tmp + mask); 224 225 mark_buffer_dirty(bh); 226 affs_mark_sb_dirty(sb); 227 228 mutex_unlock(&sbi->s_bmlock); 229 230 pr_debug("%d\n", blk); 231 return blk; 232 233 err_bh_read: 234 affs_error(sb,"affs_read_block","Cannot read bitmap block %u", bm->bm_key); 235 sbi->s_bmap_bh = NULL; 236 sbi->s_last_bmap = ~0; 237 err_full: 238 mutex_unlock(&sbi->s_bmlock); 239 pr_debug("failed\n"); 240 return 0; 241 } 242 243 int affs_init_bitmap(struct super_block *sb, int *flags) 244 { 245 struct affs_bm_info *bm; 246 struct buffer_head *bmap_bh = NULL, *bh = NULL; 247 __be32 *bmap_blk; 248 u32 size, blk, end, offset, mask; 249 int i, res = 0; 250 struct affs_sb_info *sbi = AFFS_SB(sb); 251 252 if (*flags & MS_RDONLY) 253 return 0; 254 255 if (!AFFS_ROOT_TAIL(sb, sbi->s_root_bh)->bm_flag) { 256 pr_notice("Bitmap invalid - mounting %s read only\n", sb->s_id); 257 *flags |= MS_RDONLY; 258 return 0; 259 } 260 261 sbi->s_last_bmap = ~0; 262 sbi->s_bmap_bh = NULL; 263 sbi->s_bmap_bits = sb->s_blocksize * 8 - 32; 264 sbi->s_bmap_count = (sbi->s_partition_size - sbi->s_reserved + 265 sbi->s_bmap_bits - 1) / sbi->s_bmap_bits; 266 size = sbi->s_bmap_count * sizeof(*bm); 267 bm = sbi->s_bitmap = kzalloc(size, GFP_KERNEL); 268 if (!sbi->s_bitmap) { 269 pr_err("Bitmap allocation failed\n"); 270 return -ENOMEM; 271 } 272 273 bmap_blk = (__be32 *)sbi->s_root_bh->b_data; 274 blk = sb->s_blocksize / 4 - 49; 275 end = blk + 25; 276 277 for (i = sbi->s_bmap_count; i > 0; bm++, i--) { 278 affs_brelse(bh); 279 280 bm->bm_key = be32_to_cpu(bmap_blk[blk]); 281 bh = affs_bread(sb, bm->bm_key); 282 if (!bh) { 283 pr_err("Cannot read bitmap\n"); 284 res = -EIO; 285 goto out; 286 } 287 if (affs_checksum_block(sb, bh)) { 288 pr_warn("Bitmap %u invalid - mounting %s read only.\n", 289 bm->bm_key, sb->s_id); 290 *flags |= MS_RDONLY; 291 goto out; 292 } 293 pr_debug("read bitmap block %d: %d\n", blk, bm->bm_key); 294 bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4); 295 296 /* Don't try read the extension if this is the last block, 297 * but we also need the right bm pointer below 298 */ 299 if (++blk < end || i == 1) 300 continue; 301 if (bmap_bh) 302 affs_brelse(bmap_bh); 303 bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk])); 304 if (!bmap_bh) { 305 pr_err("Cannot read bitmap extension\n"); 306 res = -EIO; 307 goto out; 308 } 309 bmap_blk = (__be32 *)bmap_bh->b_data; 310 blk = 0; 311 end = sb->s_blocksize / 4 - 1; 312 } 313 314 offset = (sbi->s_partition_size - sbi->s_reserved) % sbi->s_bmap_bits; 315 mask = ~(0xFFFFFFFFU << (offset & 31)); 316 pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask); 317 offset = offset / 32 + 1; 318 319 if (mask) { 320 u32 old, new; 321 322 /* Mark unused bits in the last word as allocated */ 323 old = be32_to_cpu(((__be32 *)bh->b_data)[offset]); 324 new = old & mask; 325 //if (old != new) { 326 ((__be32 *)bh->b_data)[offset] = cpu_to_be32(new); 327 /* fix checksum */ 328 //new -= old; 329 //old = be32_to_cpu(*(__be32 *)bh->b_data); 330 //*(__be32 *)bh->b_data = cpu_to_be32(old - new); 331 //mark_buffer_dirty(bh); 332 //} 333 /* correct offset for the bitmap count below */ 334 //offset++; 335 } 336 while (++offset < sb->s_blocksize / 4) 337 ((__be32 *)bh->b_data)[offset] = 0; 338 ((__be32 *)bh->b_data)[0] = 0; 339 ((__be32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh)); 340 mark_buffer_dirty(bh); 341 342 /* recalculate bitmap count for last block */ 343 bm--; 344 bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4); 345 346 out: 347 affs_brelse(bh); 348 affs_brelse(bmap_bh); 349 return res; 350 } 351 352 void affs_free_bitmap(struct super_block *sb) 353 { 354 struct affs_sb_info *sbi = AFFS_SB(sb); 355 356 if (!sbi->s_bitmap) 357 return; 358 359 affs_brelse(sbi->s_bmap_bh); 360 sbi->s_bmap_bh = NULL; 361 sbi->s_last_bmap = ~0; 362 kfree(sbi->s_bitmap); 363 sbi->s_bitmap = NULL; 364 } 365