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