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("AFFS: count_free_blocks()\n"); 21 22 if (sb->s_flags & MS_RDONLY) 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("AFFS: free_block(%u)\n", 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 return; 103 } 104 105 /* 106 * Allocate a block in the given allocation zone. 107 * Since we have to byte-swap the bitmap on little-endian 108 * machines, this is rather expensive. Therefore we will 109 * preallocate up to 16 blocks from the same word, if 110 * possible. We are not doing preallocations in the 111 * header zone, though. 112 */ 113 114 u32 115 affs_alloc_block(struct inode *inode, u32 goal) 116 { 117 struct super_block *sb; 118 struct affs_sb_info *sbi; 119 struct affs_bm_info *bm; 120 struct buffer_head *bh; 121 __be32 *data, *enddata; 122 u32 blk, bmap, bit, mask, mask2, tmp; 123 int i; 124 125 sb = inode->i_sb; 126 sbi = AFFS_SB(sb); 127 128 pr_debug("AFFS: balloc(inode=%lu,goal=%u): ", inode->i_ino, goal); 129 130 if (AFFS_I(inode)->i_pa_cnt) { 131 pr_debug("%d\n", AFFS_I(inode)->i_lastalloc+1); 132 AFFS_I(inode)->i_pa_cnt--; 133 return ++AFFS_I(inode)->i_lastalloc; 134 } 135 136 if (!goal || goal > sbi->s_partition_size) { 137 if (goal) 138 affs_warning(sb, "affs_balloc", "invalid goal %d", goal); 139 //if (!AFFS_I(inode)->i_last_block) 140 // affs_warning(sb, "affs_balloc", "no last alloc block"); 141 goal = sbi->s_reserved; 142 } 143 144 blk = goal - sbi->s_reserved; 145 bmap = blk / sbi->s_bmap_bits; 146 bm = &sbi->s_bitmap[bmap]; 147 148 mutex_lock(&sbi->s_bmlock); 149 150 if (bm->bm_free) 151 goto find_bmap_bit; 152 153 find_bmap: 154 /* search for the next bmap buffer with free bits */ 155 i = sbi->s_bmap_count; 156 do { 157 if (--i < 0) 158 goto err_full; 159 bmap++; 160 bm++; 161 if (bmap < sbi->s_bmap_count) 162 continue; 163 /* restart search at zero */ 164 bmap = 0; 165 bm = sbi->s_bitmap; 166 } while (!bm->bm_free); 167 blk = bmap * sbi->s_bmap_bits; 168 169 find_bmap_bit: 170 171 bh = sbi->s_bmap_bh; 172 if (sbi->s_last_bmap != bmap) { 173 affs_brelse(bh); 174 bh = affs_bread(sb, bm->bm_key); 175 if (!bh) 176 goto err_bh_read; 177 sbi->s_bmap_bh = bh; 178 sbi->s_last_bmap = bmap; 179 } 180 181 /* find an unused block in this bitmap block */ 182 bit = blk % sbi->s_bmap_bits; 183 data = (__be32 *)bh->b_data + bit / 32 + 1; 184 enddata = (__be32 *)((u8 *)bh->b_data + sb->s_blocksize); 185 mask = ~0UL << (bit & 31); 186 blk &= ~31UL; 187 188 tmp = be32_to_cpu(*data); 189 if (tmp & mask) 190 goto find_bit; 191 192 /* scan the rest of the buffer */ 193 do { 194 blk += 32; 195 if (++data >= enddata) 196 /* didn't find something, can only happen 197 * if scan didn't start at 0, try next bmap 198 */ 199 goto find_bmap; 200 } while (!*data); 201 tmp = be32_to_cpu(*data); 202 mask = ~0; 203 204 find_bit: 205 /* finally look for a free bit in the word */ 206 bit = ffs(tmp & mask) - 1; 207 blk += bit + sbi->s_reserved; 208 mask2 = mask = 1 << (bit & 31); 209 AFFS_I(inode)->i_lastalloc = blk; 210 211 /* prealloc as much as possible within this word */ 212 while ((mask2 <<= 1)) { 213 if (!(tmp & mask2)) 214 break; 215 AFFS_I(inode)->i_pa_cnt++; 216 mask |= mask2; 217 } 218 bm->bm_free -= AFFS_I(inode)->i_pa_cnt + 1; 219 220 *data = cpu_to_be32(tmp & ~mask); 221 222 /* fix checksum */ 223 tmp = be32_to_cpu(*(__be32 *)bh->b_data); 224 *(__be32 *)bh->b_data = cpu_to_be32(tmp + mask); 225 226 mark_buffer_dirty(bh); 227 affs_mark_sb_dirty(sb); 228 229 mutex_unlock(&sbi->s_bmlock); 230 231 pr_debug("%d\n", blk); 232 return blk; 233 234 err_bh_read: 235 affs_error(sb,"affs_read_block","Cannot read bitmap block %u", bm->bm_key); 236 sbi->s_bmap_bh = NULL; 237 sbi->s_last_bmap = ~0; 238 err_full: 239 mutex_unlock(&sbi->s_bmlock); 240 pr_debug("failed\n"); 241 return 0; 242 } 243 244 int affs_init_bitmap(struct super_block *sb, int *flags) 245 { 246 struct affs_bm_info *bm; 247 struct buffer_head *bmap_bh = NULL, *bh = NULL; 248 __be32 *bmap_blk; 249 u32 size, blk, end, offset, mask; 250 int i, res = 0; 251 struct affs_sb_info *sbi = AFFS_SB(sb); 252 253 if (*flags & MS_RDONLY) 254 return 0; 255 256 if (!AFFS_ROOT_TAIL(sb, sbi->s_root_bh)->bm_flag) { 257 printk(KERN_NOTICE "AFFS: Bitmap invalid - mounting %s read only\n", 258 sb->s_id); 259 *flags |= MS_RDONLY; 260 return 0; 261 } 262 263 sbi->s_last_bmap = ~0; 264 sbi->s_bmap_bh = NULL; 265 sbi->s_bmap_bits = sb->s_blocksize * 8 - 32; 266 sbi->s_bmap_count = (sbi->s_partition_size - sbi->s_reserved + 267 sbi->s_bmap_bits - 1) / sbi->s_bmap_bits; 268 size = sbi->s_bmap_count * sizeof(*bm); 269 bm = sbi->s_bitmap = kzalloc(size, GFP_KERNEL); 270 if (!sbi->s_bitmap) { 271 printk(KERN_ERR "AFFS: Bitmap allocation failed\n"); 272 return -ENOMEM; 273 } 274 275 bmap_blk = (__be32 *)sbi->s_root_bh->b_data; 276 blk = sb->s_blocksize / 4 - 49; 277 end = blk + 25; 278 279 for (i = sbi->s_bmap_count; i > 0; bm++, i--) { 280 affs_brelse(bh); 281 282 bm->bm_key = be32_to_cpu(bmap_blk[blk]); 283 bh = affs_bread(sb, bm->bm_key); 284 if (!bh) { 285 printk(KERN_ERR "AFFS: Cannot read bitmap\n"); 286 res = -EIO; 287 goto out; 288 } 289 if (affs_checksum_block(sb, bh)) { 290 printk(KERN_WARNING "AFFS: Bitmap %u invalid - mounting %s read only.\n", 291 bm->bm_key, sb->s_id); 292 *flags |= MS_RDONLY; 293 goto out; 294 } 295 pr_debug("AFFS: read bitmap block %d: %d\n", blk, bm->bm_key); 296 bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4); 297 298 /* Don't try read the extension if this is the last block, 299 * but we also need the right bm pointer below 300 */ 301 if (++blk < end || i == 1) 302 continue; 303 if (bmap_bh) 304 affs_brelse(bmap_bh); 305 bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk])); 306 if (!bmap_bh) { 307 printk(KERN_ERR "AFFS: Cannot read bitmap extension\n"); 308 res = -EIO; 309 goto out; 310 } 311 bmap_blk = (__be32 *)bmap_bh->b_data; 312 blk = 0; 313 end = sb->s_blocksize / 4 - 1; 314 } 315 316 offset = (sbi->s_partition_size - sbi->s_reserved) % sbi->s_bmap_bits; 317 mask = ~(0xFFFFFFFFU << (offset & 31)); 318 pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask); 319 offset = offset / 32 + 1; 320 321 if (mask) { 322 u32 old, new; 323 324 /* Mark unused bits in the last word as allocated */ 325 old = be32_to_cpu(((__be32 *)bh->b_data)[offset]); 326 new = old & mask; 327 //if (old != new) { 328 ((__be32 *)bh->b_data)[offset] = cpu_to_be32(new); 329 /* fix checksum */ 330 //new -= old; 331 //old = be32_to_cpu(*(__be32 *)bh->b_data); 332 //*(__be32 *)bh->b_data = cpu_to_be32(old - new); 333 //mark_buffer_dirty(bh); 334 //} 335 /* correct offset for the bitmap count below */ 336 //offset++; 337 } 338 while (++offset < sb->s_blocksize / 4) 339 ((__be32 *)bh->b_data)[offset] = 0; 340 ((__be32 *)bh->b_data)[0] = 0; 341 ((__be32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh)); 342 mark_buffer_dirty(bh); 343 344 /* recalculate bitmap count for last block */ 345 bm--; 346 bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4); 347 348 out: 349 affs_brelse(bh); 350 affs_brelse(bmap_bh); 351 return res; 352 } 353 354 void affs_free_bitmap(struct super_block *sb) 355 { 356 struct affs_sb_info *sbi = AFFS_SB(sb); 357 358 if (!sbi->s_bitmap) 359 return; 360 361 affs_brelse(sbi->s_bmap_bh); 362 sbi->s_bmap_bh = NULL; 363 sbi->s_last_bmap = ~0; 364 kfree(sbi->s_bitmap); 365 sbi->s_bitmap = NULL; 366 } 367