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/slab.h>
13 /* This is, of course, shamelessly stolen from fs/minix */
15 static const int nibblemap
[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
18 affs_count_free_bits(u32 blocksize
, const void *data
)
26 for (blocksize
/= 4; blocksize
> 0; blocksize
--) {
29 free
+= nibblemap
[tmp
& 0xf];
38 affs_count_free_blocks(struct super_block
*sb
)
40 struct affs_bm_info
*bm
;
44 pr_debug("AFFS: count_free_blocks()\n");
46 if (sb
->s_flags
& MS_RDONLY
)
49 mutex_lock(&AFFS_SB(sb
)->s_bmlock
);
51 bm
= AFFS_SB(sb
)->s_bitmap
;
53 for (i
= AFFS_SB(sb
)->s_bmap_count
; i
> 0; bm
++, i
--)
56 mutex_unlock(&AFFS_SB(sb
)->s_bmlock
);
62 affs_free_block(struct super_block
*sb
, u32 block
)
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
;
70 pr_debug("AFFS: free_block(%u)\n", block
);
72 if (block
> sbi
->s_partition_size
)
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
];
80 mutex_lock(&sbi
->s_bmlock
);
83 if (sbi
->s_last_bmap
!= bmap
) {
85 bh
= affs_bread(sb
, bm
->bm_key
);
89 sbi
->s_last_bmap
= bmap
;
92 mask
= 1 << (bit
& 31);
93 data
= (__be32
*)bh
->b_data
+ bit
/ 32 + 1;
96 tmp
= be32_to_cpu(*data
);
99 *data
= cpu_to_be32(tmp
| mask
);
102 tmp
= be32_to_cpu(*(__be32
*)bh
->b_data
);
103 *(__be32
*)bh
->b_data
= cpu_to_be32(tmp
- mask
);
105 mark_buffer_dirty(bh
);
109 mutex_unlock(&sbi
->s_bmlock
);
113 affs_warning(sb
,"affs_free_block","Trying to free block %u which is already free", block
);
114 mutex_unlock(&sbi
->s_bmlock
);
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
);
125 affs_error(sb
, "affs_free_block","Block %u outside partition", block
);
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.
139 affs_alloc_block(struct inode
*inode
, u32 goal
)
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
;
152 pr_debug("AFFS: balloc(inode=%lu,goal=%u): ", inode
->i_ino
, goal
);
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
;
160 if (!goal
|| goal
> sbi
->s_partition_size
) {
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
;
168 blk
= goal
- sbi
->s_reserved
;
169 bmap
= blk
/ sbi
->s_bmap_bits
;
170 bm
= &sbi
->s_bitmap
[bmap
];
172 mutex_lock(&sbi
->s_bmlock
);
178 /* search for the next bmap buffer with free bits */
179 i
= sbi
->s_bmap_count
;
185 if (bmap
< sbi
->s_bmap_count
)
187 /* restart search at zero */
190 } while (!bm
->bm_free
);
191 blk
= bmap
* sbi
->s_bmap_bits
;
196 if (sbi
->s_last_bmap
!= bmap
) {
198 bh
= affs_bread(sb
, bm
->bm_key
);
202 sbi
->s_last_bmap
= bmap
;
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);
212 tmp
= be32_to_cpu(*data
);
216 /* scan the rest of the buffer */
219 if (++data
>= enddata
)
220 /* didn't find something, can only happen
221 * if scan didn't start at 0, try next bmap
225 tmp
= be32_to_cpu(*data
);
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
;
235 /* prealloc as much as possible within this word */
236 while ((mask2
<<= 1)) {
239 AFFS_I(inode
)->i_pa_cnt
++;
242 bm
->bm_free
-= AFFS_I(inode
)->i_pa_cnt
+ 1;
244 *data
= cpu_to_be32(tmp
& ~mask
);
247 tmp
= be32_to_cpu(*(__be32
*)bh
->b_data
);
248 *(__be32
*)bh
->b_data
= cpu_to_be32(tmp
+ mask
);
250 mark_buffer_dirty(bh
);
253 mutex_unlock(&sbi
->s_bmlock
);
255 pr_debug("%d\n", blk
);
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;
263 mutex_unlock(&sbi
->s_bmlock
);
264 pr_debug("failed\n");
268 int affs_init_bitmap(struct super_block
*sb
, int *flags
)
270 struct affs_bm_info
*bm
;
271 struct buffer_head
*bmap_bh
= NULL
, *bh
= NULL
;
273 u32 size
, blk
, end
, offset
, mask
;
275 struct affs_sb_info
*sbi
= AFFS_SB(sb
);
277 if (*flags
& MS_RDONLY
)
280 if (!AFFS_ROOT_TAIL(sb
, sbi
->s_root_bh
)->bm_flag
) {
281 printk(KERN_NOTICE
"AFFS: Bitmap invalid - mounting %s read only\n",
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");
299 bmap_blk
= (__be32
*)sbi
->s_root_bh
->b_data
;
300 blk
= sb
->s_blocksize
/ 4 - 49;
303 for (i
= sbi
->s_bmap_count
; i
> 0; bm
++, i
--) {
306 bm
->bm_key
= be32_to_cpu(bmap_blk
[blk
]);
307 bh
= affs_bread(sb
, bm
->bm_key
);
309 printk(KERN_ERR
"AFFS: Cannot read bitmap\n");
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
);
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);
322 /* Don't try read the extension if this is the last block,
323 * but we also need the right bm pointer below
325 if (++blk
< end
|| i
== 1)
328 affs_brelse(bmap_bh
);
329 bmap_bh
= affs_bread(sb
, be32_to_cpu(bmap_blk
[blk
]));
331 printk(KERN_ERR
"AFFS: Cannot read bitmap extension\n");
335 bmap_blk
= (__be32
*)bmap_bh
->b_data
;
337 end
= sb
->s_blocksize
/ 4 - 1;
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;
348 /* Mark unused bits in the last word as allocated */
349 old
= be32_to_cpu(((__be32
*)bh
->b_data
)[offset
]);
352 ((__be32
*)bh
->b_data
)[offset
] = cpu_to_be32(new);
355 //old = be32_to_cpu(*(__be32 *)bh->b_data);
356 //*(__be32 *)bh->b_data = cpu_to_be32(old - new);
357 //mark_buffer_dirty(bh);
359 /* correct offset for the bitmap count below */
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
);
368 /* recalculate bitmap count for last block */
370 bm
->bm_free
= affs_count_free_bits(sb
->s_blocksize
- 4, bh
->b_data
+ 4);
374 affs_brelse(bmap_bh
);
378 void affs_free_bitmap(struct super_block
*sb
)
380 struct affs_sb_info
*sbi
= AFFS_SB(sb
);
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
;
This page took 0.037518 seconds and 5 git commands to generate.