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 14static int nibblemap[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 }; 15 16static u32 17affs_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 36u32 37affs_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 60void 61affs_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 111err_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 116err_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 123err_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 137u32 138affs_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 176find_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 192find_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 227find_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 257err_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; 261err_full: 262 up(&sbi->s_bmlock); 263 pr_debug("failed\n"); 264 return 0; 265} 266 267int 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 = kzalloc(size, GFP_KERNEL); 293 if (!sbi->s_bitmap) { 294 printk(KERN_ERR "AFFS: Bitmap allocation failed\n"); 295 return -ENOMEM; 296 } 297 298 bmap_blk = (__be32 *)sbi->s_root_bh->b_data; 299 blk = sb->s_blocksize / 4 - 49; 300 end = blk + 25; 301 302 for (i = sbi->s_bmap_count; i > 0; bm++, i--) { 303 affs_brelse(bh); 304 305 bm->bm_key = be32_to_cpu(bmap_blk[blk]); 306 bh = affs_bread(sb, bm->bm_key); 307 if (!bh) { 308 printk(KERN_ERR "AFFS: Cannot read bitmap\n"); 309 res = -EIO; 310 goto out; 311 } 312 if (affs_checksum_block(sb, bh)) { 313 printk(KERN_WARNING "AFFS: Bitmap %u invalid - mounting %s read only.\n", 314 bm->bm_key, sb->s_id); 315 *flags |= MS_RDONLY; 316 goto out; 317 } 318 pr_debug("AFFS: read bitmap block %d: %d\n", blk, bm->bm_key); 319 bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4); 320 321 /* Don't try read the extension if this is the last block, 322 * but we also need the right bm pointer below 323 */ 324 if (++blk < end || i == 1) 325 continue; 326 if (bmap_bh) 327 affs_brelse(bmap_bh); 328 bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk])); 329 if (!bmap_bh) { 330 printk(KERN_ERR "AFFS: Cannot read bitmap extension\n"); 331 res = -EIO; 332 goto out; 333 } 334 bmap_blk = (__be32 *)bmap_bh->b_data; 335 blk = 0; 336 end = sb->s_blocksize / 4 - 1; 337 } 338 339 offset = (sbi->s_partition_size - sbi->s_reserved) % sbi->s_bmap_bits; 340 mask = ~(0xFFFFFFFFU << (offset & 31)); 341 pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask); 342 offset = offset / 32 + 1; 343 344 if (mask) { 345 u32 old, new; 346 347 /* Mark unused bits in the last word as allocated */ 348 old = be32_to_cpu(((__be32 *)bh->b_data)[offset]); 349 new = old & mask; 350 //if (old != new) { 351 ((__be32 *)bh->b_data)[offset] = cpu_to_be32(new); 352 /* fix checksum */ 353 //new -= old; 354 //old = be32_to_cpu(*(__be32 *)bh->b_data); 355 //*(__be32 *)bh->b_data = cpu_to_be32(old - new); 356 //mark_buffer_dirty(bh); 357 //} 358 /* correct offset for the bitmap count below */ 359 //offset++; 360 } 361 while (++offset < sb->s_blocksize / 4) 362 ((__be32 *)bh->b_data)[offset] = 0; 363 ((__be32 *)bh->b_data)[0] = 0; 364 ((__be32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh)); 365 mark_buffer_dirty(bh); 366 367 /* recalculate bitmap count for last block */ 368 bm--; 369 bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4); 370 371out: 372 affs_brelse(bh); 373 affs_brelse(bmap_bh); 374 return res; 375} 376 377void affs_free_bitmap(struct super_block *sb) 378{ 379 struct affs_sb_info *sbi = AFFS_SB(sb); 380 381 if (!sbi->s_bitmap) 382 return; 383 384 affs_brelse(sbi->s_bmap_bh); 385 sbi->s_bmap_bh = NULL; 386 sbi->s_last_bmap = ~0; 387 kfree(sbi->s_bitmap); 388 sbi->s_bitmap = NULL; 389} 390