]>
Commit | Line | Data |
---|---|---|
1da177e4 LT |
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 | ||
14 | static int nibblemap[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 }; | |
15 | ||
16 | static u32 | |
17 | affs_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 | ||
36 | u32 | |
37 | affs_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 | ||
60 | void | |
61 | affs_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 | ||
111 | err_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 | ||
116 | err_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 | ||
123 | err_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 | ||
137 | u32 | |
138 | affs_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 | ||
176 | find_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 | ||
192 | find_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 | ||
227 | find_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 | ||
257 | err_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; | |
261 | err_full: | |
262 | up(&sbi->s_bmlock); | |
263 | pr_debug("failed\n"); | |
264 | return 0; | |
265 | } | |
266 | ||
267 | int 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); | |
b593e48d | 292 | bm = sbi->s_bitmap = kzalloc(size, GFP_KERNEL); |
1da177e4 LT |
293 | if (!sbi->s_bitmap) { |
294 | printk(KERN_ERR "AFFS: Bitmap allocation failed\n"); | |
295 | return -ENOMEM; | |
296 | } | |
1da177e4 LT |
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 | ||
371 | out: | |
372 | affs_brelse(bh); | |
373 | affs_brelse(bmap_bh); | |
374 | return res; | |
375 | } | |
376 | ||
377 | void 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 | } |