File: /usr/src/linux/fs/affs/bitmap.c
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
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
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
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
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
271 int
272 affs_init_bitmap(struct super_block *sb)
273 {
274 struct affs_bm_info *bm;
275 struct buffer_head *bmap_bh = NULL, *bh = NULL;
276 u32 *bmap_blk;
277 u32 size, blk, end, offset, mask;
278 int i, res = 0;
279
280 if (sb->s_flags & MS_RDONLY)
281 return 0;
282
283 if (!AFFS_ROOT_TAIL(sb, AFFS_SB->s_root_bh)->bm_flag) {
284 printk(KERN_NOTICE "AFFS: Bitmap invalid - mounting %s read only\n",
285 kdevname(sb->s_dev));
286 sb->s_flags |= MS_RDONLY;
287 return 0;
288 }
289
290 AFFS_SB->s_last_bmap = ~0;
291 AFFS_SB->s_bmap_bh = NULL;
292 AFFS_SB->s_bmap_bits = sb->s_blocksize * 8 - 32;
293 AFFS_SB->s_bmap_count = (AFFS_SB->s_partition_size - AFFS_SB->s_reserved +
294 AFFS_SB->s_bmap_bits - 1) / AFFS_SB->s_bmap_bits;
295 size = AFFS_SB->s_bmap_count * sizeof(struct affs_bm_info);
296 bm = AFFS_SB->s_bitmap = kmalloc(size, GFP_KERNEL);
297 if (!AFFS_SB->s_bitmap) {
298 printk(KERN_ERR "AFFS: Bitmap allocation failed\n");
299 return 1;
300 }
301 memset(AFFS_SB->s_bitmap, 0, size);
302
303 bmap_blk = (u32 *)AFFS_SB->s_root_bh->b_data;
304 blk = sb->s_blocksize / 4 - 49;
305 end = blk + 25;
306
307 for (i = AFFS_SB->s_bmap_count; i > 0; bm++, i--) {
308 affs_brelse(bh);
309
310 bm->bm_key = be32_to_cpu(bmap_blk[blk]);
311 bh = affs_bread(sb, bm->bm_key);
312 if (!bh) {
313 printk(KERN_ERR "AFFS: Cannot read bitmap\n");
314 res = 1;
315 goto out;
316 }
317 if (affs_checksum_block(sb, bh)) {
318 printk(KERN_WARNING "AFFS: Bitmap %u invalid - mounting %s read only.\n",
319 bm->bm_key, kdevname(sb->s_dev));
320 sb->s_flags |= MS_RDONLY;
321 goto out;
322 }
323 pr_debug("AFFS: read bitmap block %d: %d\n", blk, bm->bm_key);
324 bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4);
325
326 /* Don't try read the extension if this is the last block,
327 * but we also need the right bm pointer below
328 */
329 if (++blk < end || i == 1)
330 continue;
331 if (bmap_bh)
332 affs_brelse(bmap_bh);
333 bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk]));
334 if (!bmap_bh) {
335 printk(KERN_ERR "AFFS: Cannot read bitmap extension\n");
336 res = 1;
337 goto out;
338 }
339 bmap_blk = (u32 *)bmap_bh->b_data;
340 blk = 0;
341 end = sb->s_blocksize / 4 - 1;
342 }
343
344 offset = (AFFS_SB->s_partition_size - AFFS_SB->s_reserved) % AFFS_SB->s_bmap_bits;
345 mask = ~(0xFFFFFFFFU << (offset & 31));
346 pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask);
347 offset = offset / 32 + 1;
348
349 if (mask) {
350 u32 old, new;
351
352 /* Mark unused bits in the last word as allocated */
353 old = be32_to_cpu(((u32 *)bh->b_data)[offset]);
354 new = old & mask;
355 //if (old != new) {
356 ((u32 *)bh->b_data)[offset] = cpu_to_be32(new);
357 /* fix checksum */
358 //new -= old;
359 //old = be32_to_cpu(*(u32 *)bh->b_data);
360 //*(u32 *)bh->b_data = cpu_to_be32(old - new);
361 //mark_buffer_dirty(bh);
362 //}
363 /* correct offset for the bitmap count below */
364 //offset++;
365 }
366 while (++offset < sb->s_blocksize / 4)
367 ((u32 *)bh->b_data)[offset] = 0;
368 ((u32 *)bh->b_data)[0] = 0;
369 ((u32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh));
370 mark_buffer_dirty(bh);
371
372 /* recalculate bitmap count for last block */
373 bm--;
374 bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4);
375
376 out:
377 affs_brelse(bh);
378 affs_brelse(bmap_bh);
379 return res;
380 }
381