aboutsummaryrefslogtreecommitdiffstats
path: root/fs/affs/bitmap.c
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 18:20:36 -0400
committerLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 18:20:36 -0400
commit1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 (patch)
tree0bba044c4ce775e45a88a51686b5d9f90697ea9d /fs/affs/bitmap.c
Linux-2.6.12-rc2v2.6.12-rc2
Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip!
Diffstat (limited to 'fs/affs/bitmap.c')
-rw-r--r--fs/affs/bitmap.c390
1 files changed, 390 insertions, 0 deletions
diff --git a/fs/affs/bitmap.c b/fs/affs/bitmap.c
new file mode 100644
index 000000000000..b0b953683c1a
--- /dev/null
+++ b/fs/affs/bitmap.c
@@ -0,0 +1,390 @@
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
14static int nibblemap[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
15
16static u32
17affs_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
36u32
37affs_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
60void
61affs_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
111err_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
116err_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
123err_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
137u32
138affs_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
176find_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
192find_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
227find_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
257err_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;
261err_full:
262 up(&sbi->s_bmlock);
263 pr_debug("failed\n");
264 return 0;
265}
266
267int 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);
292 bm = sbi->s_bitmap = kmalloc(size, GFP_KERNEL);
293 if (!sbi->s_bitmap) {
294 printk(KERN_ERR "AFFS: Bitmap allocation failed\n");
295 return -ENOMEM;
296 }
297 memset(sbi->s_bitmap, 0, size);
298
299 bmap_blk = (__be32 *)sbi->s_root_bh->b_data;
300 blk = sb->s_blocksize / 4 - 49;
301 end = blk + 25;
302
303 for (i = sbi->s_bmap_count; i > 0; bm++, i--) {
304 affs_brelse(bh);
305
306 bm->bm_key = be32_to_cpu(bmap_blk[blk]);
307 bh = affs_bread(sb, bm->bm_key);
308 if (!bh) {
309 printk(KERN_ERR "AFFS: Cannot read bitmap\n");
310 res = -EIO;
311 goto out;
312 }
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);
316 *flags |= MS_RDONLY;
317 goto out;
318 }
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);
321
322 /* Don't try read the extension if this is the last block,
323 * but we also need the right bm pointer below
324 */
325 if (++blk < end || i == 1)
326 continue;
327 if (bmap_bh)
328 affs_brelse(bmap_bh);
329 bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk]));
330 if (!bmap_bh) {
331 printk(KERN_ERR "AFFS: Cannot read bitmap extension\n");
332 res = -EIO;
333 goto out;
334 }
335 bmap_blk = (__be32 *)bmap_bh->b_data;
336 blk = 0;
337 end = sb->s_blocksize / 4 - 1;
338 }
339
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;
344
345 if (mask) {
346 u32 old, new;
347
348 /* Mark unused bits in the last word as allocated */
349 old = be32_to_cpu(((__be32 *)bh->b_data)[offset]);
350 new = old & mask;
351 //if (old != new) {
352 ((__be32 *)bh->b_data)[offset] = cpu_to_be32(new);
353 /* fix checksum */
354 //new -= old;
355 //old = be32_to_cpu(*(__be32 *)bh->b_data);
356 //*(__be32 *)bh->b_data = cpu_to_be32(old - new);
357 //mark_buffer_dirty(bh);
358 //}
359 /* correct offset for the bitmap count below */
360 //offset++;
361 }
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);
367
368 /* recalculate bitmap count for last block */
369 bm--;
370 bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4);
371
372out:
373 affs_brelse(bh);
374 affs_brelse(bmap_bh);
375 return res;
376}
377
378void affs_free_bitmap(struct super_block *sb)
379{
380 struct affs_sb_info *sbi = AFFS_SB(sb);
381
382 if (!sbi->s_bitmap)
383 return;
384
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;
390}