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.
12 /* This is, of course, shamelessly stolen from fs/minix */
14 static const int nibblemap
[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
17 affs_count_free_bits(u32 blocksize
, const void *data
)
25 for (blocksize
/= 4; blocksize
> 0; blocksize
--) {
28 free
+= nibblemap
[tmp
& 0xf];
37 affs_count_free_blocks(struct super_block
*sb
)
39 struct affs_bm_info
*bm
;
43 pr_debug("AFFS: count_free_blocks()\n");
45 if (sb
->s_flags
& MS_RDONLY
)
48 mutex_lock(&AFFS_SB(sb
)->s_bmlock
);
50 bm
= AFFS_SB(sb
)->s_bitmap
;
52 for (i
= AFFS_SB(sb
)->s_bmap_count
; i
> 0; bm
++, i
--)
55 mutex_unlock(&AFFS_SB(sb
)->s_bmlock
);
61 affs_free_block(struct super_block
*sb
, u32 block
)
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
;
69 pr_debug("AFFS: free_block(%u)\n", block
);
71 if (block
> sbi
->s_partition_size
)
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
];
79 mutex_lock(&sbi
->s_bmlock
);
82 if (sbi
->s_last_bmap
!= bmap
) {
84 bh
= affs_bread(sb
, bm
->bm_key
);
88 sbi
->s_last_bmap
= bmap
;
91 mask
= 1 << (bit
& 31);
92 data
= (__be32
*)bh
->b_data
+ bit
/ 32 + 1;
95 tmp
= be32_to_cpu(*data
);
98 *data
= cpu_to_be32(tmp
| mask
);
101 tmp
= be32_to_cpu(*(__be32
*)bh
->b_data
);
102 *(__be32
*)bh
->b_data
= cpu_to_be32(tmp
- mask
);
104 mark_buffer_dirty(bh
);
108 mutex_unlock(&sbi
->s_bmlock
);
112 affs_warning(sb
,"affs_free_block","Trying to free block %u which is already free", block
);
113 mutex_unlock(&sbi
->s_bmlock
);
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 mutex_unlock(&sbi
->s_bmlock
);
124 affs_error(sb
, "affs_free_block","Block %u outside partition", block
);
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.
138 affs_alloc_block(struct inode
*inode
, u32 goal
)
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
;
151 pr_debug("AFFS: balloc(inode=%lu,goal=%u): ", inode
->i_ino
, goal
);
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
;
159 if (!goal
|| goal
> sbi
->s_partition_size
) {
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
;
167 blk
= goal
- sbi
->s_reserved
;
168 bmap
= blk
/ sbi
->s_bmap_bits
;
169 bm
= &sbi
->s_bitmap
[bmap
];
171 mutex_lock(&sbi
->s_bmlock
);
177 /* search for the next bmap buffer with free bits */
178 i
= sbi
->s_bmap_count
;
184 if (bmap
< sbi
->s_bmap_count
)
186 /* restart search at zero */
189 } while (!bm
->bm_free
);
190 blk
= bmap
* sbi
->s_bmap_bits
;
195 if (sbi
->s_last_bmap
!= bmap
) {
197 bh
= affs_bread(sb
, bm
->bm_key
);
201 sbi
->s_last_bmap
= bmap
;
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);
211 tmp
= be32_to_cpu(*data
);
215 /* scan the rest of the buffer */
218 if (++data
>= enddata
)
219 /* didn't find something, can only happen
220 * if scan didn't start at 0, try next bmap
224 tmp
= be32_to_cpu(*data
);
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
;
234 /* prealloc as much as possible within this word */
235 while ((mask2
<<= 1)) {
238 AFFS_I(inode
)->i_pa_cnt
++;
241 bm
->bm_free
-= AFFS_I(inode
)->i_pa_cnt
+ 1;
243 *data
= cpu_to_be32(tmp
& ~mask
);
246 tmp
= be32_to_cpu(*(__be32
*)bh
->b_data
);
247 *(__be32
*)bh
->b_data
= cpu_to_be32(tmp
+ mask
);
249 mark_buffer_dirty(bh
);
252 mutex_unlock(&sbi
->s_bmlock
);
254 pr_debug("%d\n", blk
);
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;
262 mutex_unlock(&sbi
->s_bmlock
);
263 pr_debug("failed\n");
267 int affs_init_bitmap(struct super_block
*sb
, int *flags
)
269 struct affs_bm_info
*bm
;
270 struct buffer_head
*bmap_bh
= NULL
, *bh
= NULL
;
272 u32 size
, blk
, end
, offset
, mask
;
274 struct affs_sb_info
*sbi
= AFFS_SB(sb
);
276 if (*flags
& MS_RDONLY
)
279 if (!AFFS_ROOT_TAIL(sb
, sbi
->s_root_bh
)->bm_flag
) {
280 printk(KERN_NOTICE
"AFFS: Bitmap invalid - mounting %s read only\n",
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");
298 bmap_blk
= (__be32
*)sbi
->s_root_bh
->b_data
;
299 blk
= sb
->s_blocksize
/ 4 - 49;
302 for (i
= sbi
->s_bmap_count
; i
> 0; bm
++, i
--) {
305 bm
->bm_key
= be32_to_cpu(bmap_blk
[blk
]);
306 bh
= affs_bread(sb
, bm
->bm_key
);
308 printk(KERN_ERR
"AFFS: Cannot read bitmap\n");
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
);
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);
321 /* Don't try read the extension if this is the last block,
322 * but we also need the right bm pointer below
324 if (++blk
< end
|| i
== 1)
327 affs_brelse(bmap_bh
);
328 bmap_bh
= affs_bread(sb
, be32_to_cpu(bmap_blk
[blk
]));
330 printk(KERN_ERR
"AFFS: Cannot read bitmap extension\n");
334 bmap_blk
= (__be32
*)bmap_bh
->b_data
;
336 end
= sb
->s_blocksize
/ 4 - 1;
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;
347 /* Mark unused bits in the last word as allocated */
348 old
= be32_to_cpu(((__be32
*)bh
->b_data
)[offset
]);
351 ((__be32
*)bh
->b_data
)[offset
] = cpu_to_be32(new);
354 //old = be32_to_cpu(*(__be32 *)bh->b_data);
355 //*(__be32 *)bh->b_data = cpu_to_be32(old - new);
356 //mark_buffer_dirty(bh);
358 /* correct offset for the bitmap count below */
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
);
367 /* recalculate bitmap count for last block */
369 bm
->bm_free
= affs_count_free_bits(sb
->s_blocksize
- 4, bh
->b_data
+ 4);
373 affs_brelse(bmap_bh
);
377 void affs_free_bitmap(struct super_block
*sb
)
379 struct affs_sb_info
*sbi
= AFFS_SB(sb
);
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
;
This page took 0.03829 seconds and 6 git commands to generate.