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