2 * linux/fs/affs/bitmap.c
4 * (c) 1996 Hans-Joachim Widmaier
6 * bitmap.c contains the code that handles all bitmap related stuff -
7 * block allocation, deallocation, calculation of free space.
10 #include <linux/time.h>
11 #include <linux/affs_fs.h>
12 #include <linux/stat.h>
13 #include <linux/kernel.h>
14 #include <linux/slab.h>
15 #include <linux/string.h>
16 #include <linux/bitops.h>
17 #include <linux/amigaffs.h>
18 #include <linux/buffer_head.h>
20 /* This is, of course, shamelessly stolen from fs/minix */
22 static int nibblemap[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
25 affs_count_free_bits(u32 blocksize, const void *data)
33 for (blocksize /= 4; blocksize > 0; blocksize--) {
36 free += nibblemap[tmp & 0xf];
45 affs_count_free_blocks(struct super_block *sb)
47 struct affs_bm_info *bm;
51 pr_debug("AFFS: count_free_blocks()\n");
53 if (sb->s_flags & MS_RDONLY)
56 down(&AFFS_SB(sb)->s_bmlock);
58 bm = AFFS_SB(sb)->s_bitmap;
60 for (i = AFFS_SB(sb)->s_bmap_count; i > 0; bm++, i--)
63 up(&AFFS_SB(sb)->s_bmlock);
69 affs_free_block(struct super_block *sb, u32 block)
71 struct affs_sb_info *sbi = AFFS_SB(sb);
72 struct affs_bm_info *bm;
73 struct buffer_head *bh;
74 u32 blk, bmap, bit, mask, tmp;
77 pr_debug("AFFS: free_block(%u)\n", block);
79 if (block > sbi->s_partition_size)
82 blk = block - sbi->s_reserved;
83 bmap = blk / sbi->s_bmap_bits;
84 bit = blk % sbi->s_bmap_bits;
85 bm = &sbi->s_bitmap[bmap];
90 if (sbi->s_last_bmap != bmap) {
92 bh = affs_bread(sb, bm->bm_key);
96 sbi->s_last_bmap = bmap;
99 mask = 1 << (bit & 31);
100 data = (u32 *)bh->b_data + bit / 32 + 1;
102 /* mark block free */
103 tmp = be32_to_cpu(*data);
106 *data = cpu_to_be32(tmp | mask);
109 tmp = be32_to_cpu(*(u32 *)bh->b_data);
110 *(u32 *)bh->b_data = cpu_to_be32(tmp - mask);
112 mark_buffer_dirty(bh);
120 affs_warning(sb,"affs_free_block","Trying to free block %u which is already free", block);
125 affs_error(sb,"affs_free_block","Cannot read bitmap block %u", bm->bm_key);
126 sbi->s_bmap_bh = NULL;
127 sbi->s_last_bmap = ~0;
132 affs_error(sb, "affs_free_block","Block %u outside partition", block);
137 * Allocate a block in the given allocation zone.
138 * Since we have to byte-swap the bitmap on little-endian
139 * machines, this is rather expensive. Therefor we will
140 * preallocate up to 16 blocks from the same word, if
141 * possible. We are not doing preallocations in the
142 * header zone, though.
146 affs_alloc_block(struct inode *inode, u32 goal)
148 struct super_block *sb;
149 struct affs_sb_info *sbi;
150 struct affs_bm_info *bm;
151 struct buffer_head *bh;
153 u32 blk, bmap, bit, mask, mask2, tmp;
159 pr_debug("AFFS: balloc(inode=%lu,goal=%u): ", inode->i_ino, goal);
161 if (AFFS_I(inode)->i_pa_cnt) {
162 pr_debug("%d\n", AFFS_I(inode)->i_lastalloc+1);
163 AFFS_I(inode)->i_pa_cnt--;
164 return ++AFFS_I(inode)->i_lastalloc;
167 if (!goal || goal > sbi->s_partition_size) {
169 affs_warning(sb, "affs_balloc", "invalid goal %d", goal);
170 //if (!AFFS_I(inode)->i_last_block)
171 // affs_warning(sb, "affs_balloc", "no last alloc block");
172 goal = sbi->s_reserved;
175 blk = goal - sbi->s_reserved;
176 bmap = blk / sbi->s_bmap_bits;
177 bm = &sbi->s_bitmap[bmap];
179 down(&sbi->s_bmlock);
185 /* search for the next bmap buffer with free bits */
186 i = sbi->s_bmap_count;
192 if (bmap < sbi->s_bmap_count)
194 /* restart search at zero */
197 } while (!bm->bm_free);
198 blk = bmap * sbi->s_bmap_bits;
203 if (sbi->s_last_bmap != bmap) {
205 bh = affs_bread(sb, bm->bm_key);
209 sbi->s_last_bmap = bmap;
212 /* find an unused block in this bitmap block */
213 bit = blk % sbi->s_bmap_bits;
214 data = (u32 *)bh->b_data + bit / 32 + 1;
215 enddata = (u32 *)((u8 *)bh->b_data + sb->s_blocksize);
216 mask = ~0UL << (bit & 31);
219 tmp = be32_to_cpu(*data);
223 /* scan the rest of the buffer */
226 if (++data >= enddata)
227 /* didn't find something, can only happen
228 * if scan didn't start at 0, try next bmap
231 } while (!(tmp = *data));
232 tmp = be32_to_cpu(tmp);
236 /* finally look for a free bit in the word */
237 bit = ffs(tmp & mask) - 1;
238 blk += bit + sbi->s_reserved;
239 mask2 = mask = 1 << (bit & 31);
240 AFFS_I(inode)->i_lastalloc = blk;
242 /* prealloc as much as possible within this word */
243 while ((mask2 <<= 1)) {
246 AFFS_I(inode)->i_pa_cnt++;
249 bm->bm_free -= AFFS_I(inode)->i_pa_cnt + 1;
251 *data = cpu_to_be32(tmp & ~mask);
254 tmp = be32_to_cpu(*(u32 *)bh->b_data);
255 *(u32 *)bh->b_data = cpu_to_be32(tmp + mask);
257 mark_buffer_dirty(bh);
262 pr_debug("%d\n", blk);
266 affs_error(sb,"affs_read_block","Cannot read bitmap block %u", bm->bm_key);
267 sbi->s_bmap_bh = NULL;
268 sbi->s_last_bmap = ~0;
271 pr_debug("failed\n");
276 affs_init_bitmap(struct super_block *sb)
278 struct affs_bm_info *bm;
279 struct buffer_head *bmap_bh = NULL, *bh = NULL;
281 u32 size, blk, end, offset, mask;
283 struct affs_sb_info *sbi = AFFS_SB(sb);
285 if (sb->s_flags & MS_RDONLY)
288 if (!AFFS_ROOT_TAIL(sb, sbi->s_root_bh)->bm_flag) {
289 printk(KERN_NOTICE "AFFS: Bitmap invalid - mounting %s read only\n",
291 sb->s_flags |= MS_RDONLY;
295 sbi->s_last_bmap = ~0;
296 sbi->s_bmap_bh = NULL;
297 sbi->s_bmap_bits = sb->s_blocksize * 8 - 32;
298 sbi->s_bmap_count = (sbi->s_partition_size - sbi->s_reserved +
299 sbi->s_bmap_bits - 1) / sbi->s_bmap_bits;
300 size = sbi->s_bmap_count * sizeof(*bm);
301 bm = sbi->s_bitmap = kmalloc(size, GFP_KERNEL);
302 if (!sbi->s_bitmap) {
303 printk(KERN_ERR "AFFS: Bitmap allocation failed\n");
306 memset(sbi->s_bitmap, 0, size);
308 bmap_blk = (u32 *)sbi->s_root_bh->b_data;
309 blk = sb->s_blocksize / 4 - 49;
312 for (i = sbi->s_bmap_count; i > 0; bm++, i--) {
315 bm->bm_key = be32_to_cpu(bmap_blk[blk]);
316 bh = affs_bread(sb, bm->bm_key);
318 printk(KERN_ERR "AFFS: Cannot read bitmap\n");
322 if (affs_checksum_block(sb, bh)) {
323 printk(KERN_WARNING "AFFS: Bitmap %u invalid - mounting %s read only.\n",
324 bm->bm_key, sb->s_id);
325 sb->s_flags |= MS_RDONLY;
328 pr_debug("AFFS: read bitmap block %d: %d\n", blk, bm->bm_key);
329 bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4);
331 /* Don't try read the extension if this is the last block,
332 * but we also need the right bm pointer below
334 if (++blk < end || i == 1)
337 affs_brelse(bmap_bh);
338 bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk]));
340 printk(KERN_ERR "AFFS: Cannot read bitmap extension\n");
344 bmap_blk = (u32 *)bmap_bh->b_data;
346 end = sb->s_blocksize / 4 - 1;
349 offset = (sbi->s_partition_size - sbi->s_reserved) % sbi->s_bmap_bits;
350 mask = ~(0xFFFFFFFFU << (offset & 31));
351 pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask);
352 offset = offset / 32 + 1;
357 /* Mark unused bits in the last word as allocated */
358 old = be32_to_cpu(((u32 *)bh->b_data)[offset]);
361 ((u32 *)bh->b_data)[offset] = cpu_to_be32(new);
364 //old = be32_to_cpu(*(u32 *)bh->b_data);
365 //*(u32 *)bh->b_data = cpu_to_be32(old - new);
366 //mark_buffer_dirty(bh);
368 /* correct offset for the bitmap count below */
371 while (++offset < sb->s_blocksize / 4)
372 ((u32 *)bh->b_data)[offset] = 0;
373 ((u32 *)bh->b_data)[0] = 0;
374 ((u32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh));
375 mark_buffer_dirty(bh);
377 /* recalculate bitmap count for last block */
379 bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4);
383 affs_brelse(bmap_bh);