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/sched.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/locks.h>
17 #include <linux/bitops.h>
18 #include <linux/amigaffs.h>
19
20 /* This is, of course, shamelessly stolen from fs/minix */
21
22 static int nibblemap[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
23
24 u32
affs_count_free_bits(u32 blocksize,const void * data)25 affs_count_free_bits(u32 blocksize, const void *data)
26 {
27 const u32 *map;
28 u32 free;
29 u32 tmp;
30
31 map = data;
32 free = 0;
33 for (blocksize /= 4; blocksize > 0; blocksize--) {
34 tmp = *map++;
35 while (tmp) {
36 free += nibblemap[tmp & 0xf];
37 tmp >>= 4;
38 }
39 }
40
41 return free;
42 }
43
44 u32
affs_count_free_blocks(struct super_block * sb)45 affs_count_free_blocks(struct super_block *sb)
46 {
47 struct affs_bm_info *bm;
48 u32 free;
49 int i;
50
51 pr_debug("AFFS: count_free_blocks()\n");
52
53 if (sb->s_flags & MS_RDONLY)
54 return 0;
55
56 down(&AFFS_SB->s_bmlock);
57
58 bm = AFFS_SB->s_bitmap;
59 free = 0;
60 for (i = AFFS_SB->s_bmap_count; i > 0; bm++, i--)
61 free += bm->bm_free;
62
63 up(&AFFS_SB->s_bmlock);
64
65 return free;
66 }
67
68 void
affs_free_block(struct super_block * sb,u32 block)69 affs_free_block(struct super_block *sb, u32 block)
70 {
71 struct affs_bm_info *bm;
72 struct buffer_head *bh;
73 u32 blk, bmap, bit, mask, tmp;
74 u32 *data;
75
76 pr_debug("AFFS: free_block(%u)\n", block);
77
78 if (block > AFFS_SB->s_partition_size)
79 goto err_range;
80
81 blk = block - AFFS_SB->s_reserved;
82 bmap = blk / AFFS_SB->s_bmap_bits;
83 bit = blk % AFFS_SB->s_bmap_bits;
84 bm = &AFFS_SB->s_bitmap[bmap];
85
86 down(&AFFS_SB->s_bmlock);
87
88 bh = AFFS_SB->s_bmap_bh;
89 if (AFFS_SB->s_last_bmap != bmap) {
90 affs_brelse(bh);
91 bh = affs_bread(sb, bm->bm_key);
92 if (!bh)
93 goto err_bh_read;
94 AFFS_SB->s_bmap_bh = bh;
95 AFFS_SB->s_last_bmap = bmap;
96 }
97
98 mask = 1 << (bit & 31);
99 data = (u32 *)bh->b_data + bit / 32 + 1;
100
101 /* mark block free */
102 tmp = be32_to_cpu(*data);
103 if (tmp & mask)
104 goto err_free;
105 *data = cpu_to_be32(tmp | mask);
106
107 /* fix checksum */
108 tmp = be32_to_cpu(*(u32 *)bh->b_data);
109 *(u32 *)bh->b_data = cpu_to_be32(tmp - mask);
110
111 mark_buffer_dirty(bh);
112 sb->s_dirt = 1;
113 bm->bm_free++;
114
115 up(&AFFS_SB->s_bmlock);
116 return;
117
118 err_free:
119 affs_warning(sb,"affs_free_block","Trying to free block %u which is already free", block);
120 up(&AFFS_SB->s_bmlock);
121 return;
122
123 err_bh_read:
124 affs_error(sb,"affs_free_block","Cannot read bitmap block %u", bm->bm_key);
125 AFFS_SB->s_bmap_bh = NULL;
126 AFFS_SB->s_last_bmap = ~0;
127 up(&AFFS_SB->s_bmlock);
128 return;
129
130 err_range:
131 affs_error(sb, "affs_free_block","Block %u outside partition", block);
132 return;
133 }
134
135 /*
136 * Allocate a block in the given allocation zone.
137 * Since we have to byte-swap the bitmap on little-endian
138 * machines, this is rather expensive. Therefor we will
139 * preallocate up to 16 blocks from the same word, if
140 * possible. We are not doing preallocations in the
141 * header zone, though.
142 */
143
144 u32
affs_alloc_block(struct inode * inode,u32 goal)145 affs_alloc_block(struct inode *inode, u32 goal)
146 {
147 struct super_block *sb;
148 struct affs_bm_info *bm;
149 struct buffer_head *bh;
150 u32 *data, *enddata;
151 u32 blk, bmap, bit, mask, mask2, tmp;
152 int i;
153
154 sb = inode->i_sb;
155
156 pr_debug("AFFS: balloc(inode=%lu,goal=%u): ", inode->i_ino, goal);
157
158 if (inode->u.affs_i.i_pa_cnt) {
159 pr_debug("%d\n", inode->u.affs_i.i_lastalloc+1);
160 inode->u.affs_i.i_pa_cnt--;
161 return ++inode->u.affs_i.i_lastalloc;
162 }
163
164 if (!goal || goal > AFFS_SB->s_partition_size) {
165 if (goal)
166 affs_warning(sb, "affs_balloc", "invalid goal %d", goal);
167 //if (!inode->u.affs_i.i_last_block)
168 // affs_warning(sb, "affs_balloc", "no last alloc block");
169 goal = AFFS_SB->s_reserved;
170 }
171
172 blk = goal - AFFS_SB->s_reserved;
173 bmap = blk / AFFS_SB->s_bmap_bits;
174 bm = &AFFS_SB->s_bitmap[bmap];
175
176 down(&AFFS_SB->s_bmlock);
177
178 if (bm->bm_free)
179 goto find_bmap_bit;
180
181 find_bmap:
182 /* search for the next bmap buffer with free bits */
183 i = AFFS_SB->s_bmap_count;
184 do {
185 bmap++;
186 bm++;
187 if (bmap < AFFS_SB->s_bmap_count)
188 continue;
189 /* restart search at zero */
190 bmap = 0;
191 bm = AFFS_SB->s_bitmap;
192 if (--i <= 0)
193 goto err_full;
194 } while (!bm->bm_free);
195 blk = bmap * AFFS_SB->s_bmap_bits;
196
197 find_bmap_bit:
198
199 bh = AFFS_SB->s_bmap_bh;
200 if (AFFS_SB->s_last_bmap != bmap) {
201 affs_brelse(bh);
202 bh = affs_bread(sb, bm->bm_key);
203 if (!bh)
204 goto err_bh_read;
205 AFFS_SB->s_bmap_bh = bh;
206 AFFS_SB->s_last_bmap = bmap;
207 }
208
209 /* find an unused block in this bitmap block */
210 bit = blk % AFFS_SB->s_bmap_bits;
211 data = (u32 *)bh->b_data + bit / 32 + 1;
212 enddata = (u32 *)((u8 *)bh->b_data + sb->s_blocksize);
213 mask = ~0UL << (bit & 31);
214 blk &= ~31UL;
215
216 tmp = be32_to_cpu(*data) & mask;
217 if (tmp)
218 goto find_bit;
219
220 /* scan the rest of the buffer */
221 do {
222 blk += 32;
223 if (++data >= enddata)
224 /* didn't find something, can only happen
225 * if scan didn't start at 0, try next bmap
226 */
227 goto find_bmap;
228 } while (!(tmp = *data));
229 tmp = be32_to_cpu(tmp);
230
231 find_bit:
232 /* finally look for a free bit in the word */
233 bit = ffs(tmp) - 1;
234 blk += bit + AFFS_SB->s_reserved;
235 mask2 = mask = 1 << (bit & 31);
236 inode->u.affs_i.i_lastalloc = blk;
237
238 /* prealloc as much as possible within this word */
239 while ((mask2 <<= 1)) {
240 if (!(tmp & mask2))
241 break;
242 inode->u.affs_i.i_pa_cnt++;
243 mask |= mask2;
244 }
245 bm->bm_free -= inode->u.affs_i.i_pa_cnt + 1;
246
247 *data = cpu_to_be32(tmp & ~mask);
248
249 /* fix checksum */
250 tmp = be32_to_cpu(*(u32 *)bh->b_data);
251 *(u32 *)bh->b_data = cpu_to_be32(tmp + mask);
252
253 mark_buffer_dirty(bh);
254 sb->s_dirt = 1;
255
256 up(&AFFS_SB->s_bmlock);
257
258 pr_debug("%d\n", blk);
259 return blk;
260
261 err_bh_read:
262 affs_error(sb,"affs_read_block","Cannot read bitmap block %u", bm->bm_key);
263 AFFS_SB->s_bmap_bh = NULL;
264 AFFS_SB->s_last_bmap = ~0;
265 err_full:
266 pr_debug("failed\n");
267 up(&AFFS_SB->s_bmlock);
268 return 0;
269 }
270
affs_init_bitmap(struct super_block * sb,int * flags)271 int affs_init_bitmap(struct super_block *sb, int *flags)
272 {
273 struct affs_bm_info *bm;
274 struct buffer_head *bmap_bh = NULL, *bh = NULL;
275 u32 *bmap_blk;
276 u32 size, blk, end, offset, mask;
277 int i, res = 0;
278
279 if (*flags & MS_RDONLY)
280 return 0;
281
282 if (!AFFS_ROOT_TAIL(sb, AFFS_SB->s_root_bh)->bm_flag) {
283 printk(KERN_NOTICE "AFFS: Bitmap invalid - mounting %s read only\n",
284 kdevname(sb->s_dev));
285 *flags |= MS_RDONLY;
286 return 0;
287 }
288
289 AFFS_SB->s_last_bmap = ~0;
290 AFFS_SB->s_bmap_bh = NULL;
291 AFFS_SB->s_bmap_bits = sb->s_blocksize * 8 - 32;
292 AFFS_SB->s_bmap_count = (AFFS_SB->s_partition_size - AFFS_SB->s_reserved +
293 AFFS_SB->s_bmap_bits - 1) / AFFS_SB->s_bmap_bits;
294 size = AFFS_SB->s_bmap_count * sizeof(*bm);
295 bm = AFFS_SB->s_bitmap = kmalloc(size, GFP_KERNEL);
296 if (!AFFS_SB->s_bitmap) {
297 printk(KERN_ERR "AFFS: Bitmap allocation failed\n");
298 return -ENOMEM;
299 }
300 memset(AFFS_SB->s_bitmap, 0, size);
301
302 bmap_blk = (u32 *)AFFS_SB->s_root_bh->b_data;
303 blk = sb->s_blocksize / 4 - 49;
304 end = blk + 25;
305
306 for (i = AFFS_SB->s_bmap_count; i > 0; bm++, i--) {
307 affs_brelse(bh);
308
309 bm->bm_key = be32_to_cpu(bmap_blk[blk]);
310 bh = affs_bread(sb, bm->bm_key);
311 if (!bh) {
312 printk(KERN_ERR "AFFS: Cannot read bitmap\n");
313 res = -EIO;
314 goto out;
315 }
316 if (affs_checksum_block(sb, bh)) {
317 printk(KERN_WARNING "AFFS: Bitmap %u invalid - mounting %s read only.\n",
318 bm->bm_key, kdevname(sb->s_dev));
319 *flags |= MS_RDONLY;
320 goto out;
321 }
322 pr_debug("AFFS: read bitmap block %d: %d\n", blk, bm->bm_key);
323 bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4);
324
325 /* Don't try read the extension if this is the last block,
326 * but we also need the right bm pointer below
327 */
328 if (++blk < end || i == 1)
329 continue;
330 if (bmap_bh)
331 affs_brelse(bmap_bh);
332 bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk]));
333 if (!bmap_bh) {
334 printk(KERN_ERR "AFFS: Cannot read bitmap extension\n");
335 res = -EIO;
336 goto out;
337 }
338 bmap_blk = (u32 *)bmap_bh->b_data;
339 blk = 0;
340 end = sb->s_blocksize / 4 - 1;
341 }
342
343 offset = (AFFS_SB->s_partition_size - AFFS_SB->s_reserved) % AFFS_SB->s_bmap_bits;
344 mask = ~(0xFFFFFFFFU << (offset & 31));
345 pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask);
346 offset = offset / 32 + 1;
347
348 if (mask) {
349 u32 old, new;
350
351 /* Mark unused bits in the last word as allocated */
352 old = be32_to_cpu(((u32 *)bh->b_data)[offset]);
353 new = old & mask;
354 //if (old != new) {
355 ((u32 *)bh->b_data)[offset] = cpu_to_be32(new);
356 /* fix checksum */
357 //new -= old;
358 //old = be32_to_cpu(*(u32 *)bh->b_data);
359 //*(u32 *)bh->b_data = cpu_to_be32(old - new);
360 //mark_buffer_dirty(bh);
361 //}
362 /* correct offset for the bitmap count below */
363 //offset++;
364 }
365 while (++offset < sb->s_blocksize / 4)
366 ((u32 *)bh->b_data)[offset] = 0;
367 ((u32 *)bh->b_data)[0] = 0;
368 ((u32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh));
369 mark_buffer_dirty(bh);
370
371 /* recalculate bitmap count for last block */
372 bm--;
373 bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4);
374
375 out:
376 affs_brelse(bh);
377 affs_brelse(bmap_bh);
378 return res;
379 }
380
affs_free_bitmap(struct super_block * sb)381 void affs_free_bitmap(struct super_block *sb)
382 {
383 if (!AFFS_SB->s_bitmap)
384 return;
385
386 affs_brelse(AFFS_SB->s_bmap_bh);
387 AFFS_SB->s_bmap_bh = NULL;
388 AFFS_SB->s_last_bmap = ~0;
389 kfree(AFFS_SB->s_bitmap);
390 AFFS_SB->s_bitmap = NULL;
391 }
392