?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/dtor/input
[linux-btrfs-devel.git] / fs / affs / bitmap.c
blob3e262711ae06edfc0202e0914bd1627c1ccb643f
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/slab.h>
11 #include "affs.h"
12
13 /* This is, of course, shamelessly stolen from fs/minix */
14
15 static const int nibblemap[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
16
17 static u32
18 affs_count_free_bits(u32 blocksize, const void *data)
19 {
20 const u32 *map;
21 u32 free;
22 u32 tmp;
23
24 map = data;
25 free = 0;
26 for (blocksize /= 4; blocksize > 0; blocksize--) {
27 tmp = *map++;
28 while (tmp) {
29 free += nibblemap[tmp & 0xf];
30 tmp >>= 4;
31 }
32 }
33
34 return free;
35 }
36
37 u32
38 affs_count_free_blocks(struct super_block *sb)
39 {
40 struct affs_bm_info *bm;
41 u32 free;
42 int i;
43
44 pr_debug("AFFS: count_free_blocks()\n");
45
46 if (sb->s_flags & MS_RDONLY)
47 return 0;
48
49 mutex_lock(&AFFS_SB(sb)->s_bmlock);
50
51 bm = AFFS_SB(sb)->s_bitmap;
52 free = 0;
53 for (i = AFFS_SB(sb)->s_bmap_count; i > 0; bm++, i--)
54 free += bm->bm_free;
55
56 mutex_unlock(&AFFS_SB(sb)->s_bmlock);
57
58 return free;
59 }
60
61 void
62 affs_free_block(struct super_block *sb, u32 block)
63 {
64 struct affs_sb_info *sbi = AFFS_SB(sb);
65 struct affs_bm_info *bm;
66 struct buffer_head *bh;
67 u32 blk, bmap, bit, mask, tmp;
68 __be32 *data;
69
70 pr_debug("AFFS: free_block(%u)\n", block);
71
72 if (block > sbi->s_partition_size)
73 goto err_range;
74
75 blk = block - sbi->s_reserved;
76 bmap = blk / sbi->s_bmap_bits;
77 bit = blk % sbi->s_bmap_bits;
78 bm = &sbi->s_bitmap[bmap];
79
80 mutex_lock(&sbi->s_bmlock);
81
82 bh = sbi->s_bmap_bh;
83 if (sbi->s_last_bmap != bmap) {
84 affs_brelse(bh);
85 bh = affs_bread(sb, bm->bm_key);
86 if (!bh)
87 goto err_bh_read;
88 sbi->s_bmap_bh = bh;
89 sbi->s_last_bmap = bmap;
90 }
91
92 mask = 1 << (bit & 31);
93 data = (__be32 *)bh->b_data + bit / 32 + 1;
94
95 /* mark block free */
96 tmp = be32_to_cpu(*data);
97 if (tmp & mask)
98 goto err_free;
99 *data = cpu_to_be32(tmp | mask);
100
101 /* fix checksum */
102 tmp = be32_to_cpu(*(__be32 *)bh->b_data);
103 *(__be32 *)bh->b_data = cpu_to_be32(tmp - mask);
104
105 mark_buffer_dirty(bh);
106 sb->s_dirt = 1;
107 bm->bm_free++;
108
109 mutex_unlock(&sbi->s_bmlock);
110 return;
111
112 err_free:
113 affs_warning(sb,"affs_free_block","Trying to free block %u which is already free", block);
114 mutex_unlock(&sbi->s_bmlock);
115 return;
116
117 err_bh_read:
118 affs_error(sb,"affs_free_block","Cannot read bitmap block %u", bm->bm_key);
119 sbi->s_bmap_bh = NULL;
120 sbi->s_last_bmap = ~0;
121 mutex_unlock(&sbi->s_bmlock);
122 return;
123
124 err_range:
125 affs_error(sb, "affs_free_block","Block %u outside partition", block);
126 return;
127 }
128
129 /*
130 * Allocate a block in the given allocation zone.
131 * Since we have to byte-swap the bitmap on little-endian
132 * machines, this is rather expensive. Therefore we will
133 * preallocate up to 16 blocks from the same word, if
134 * possible. We are not doing preallocations in the
135 * header zone, though.
136 */
137
138 u32
139 affs_alloc_block(struct inode *inode, u32 goal)
140 {
141 struct super_block *sb;
142 struct affs_sb_info *sbi;
143 struct affs_bm_info *bm;
144 struct buffer_head *bh;
145 __be32 *data, *enddata;
146 u32 blk, bmap, bit, mask, mask2, tmp;
147 int i;
148
149 sb = inode->i_sb;
150 sbi = AFFS_SB(sb);
151
152 pr_debug("AFFS: balloc(inode=%lu,goal=%u): ", inode->i_ino, goal);
153
154 if (AFFS_I(inode)->i_pa_cnt) {
155 pr_debug("%d\n", AFFS_I(inode)->i_lastalloc+1);
156 AFFS_I(inode)->i_pa_cnt--;
157 return ++AFFS_I(inode)->i_lastalloc;
158 }
159
160 if (!goal || goal > sbi->s_partition_size) {
161 if (goal)
162 affs_warning(sb, "affs_balloc", "invalid goal %d", goal);
163 //if (!AFFS_I(inode)->i_last_block)
164 // affs_warning(sb, "affs_balloc", "no last alloc block");
165 goal = sbi->s_reserved;
166 }
167
168 blk = goal - sbi->s_reserved;
169 bmap = blk / sbi->s_bmap_bits;
170 bm = &sbi->s_bitmap[bmap];
171
172 mutex_lock(&sbi->s_bmlock);
173
174 if (bm->bm_free)
175 goto find_bmap_bit;
176
177 find_bmap:
178 /* search for the next bmap buffer with free bits */
179 i = sbi->s_bmap_count;
180 do {
181 if (--i < 0)
182 goto err_full;
183 bmap++;
184 bm++;
185 if (bmap < sbi->s_bmap_count)
186 continue;
187 /* restart search at zero */
188 bmap = 0;
189 bm = sbi->s_bitmap;
190 } while (!bm->bm_free);
191 blk = bmap * sbi->s_bmap_bits;
192
193 find_bmap_bit:
194
195 bh = sbi->s_bmap_bh;
196 if (sbi->s_last_bmap != bmap) {
197 affs_brelse(bh);
198 bh = affs_bread(sb, bm->bm_key);
199 if (!bh)
200 goto err_bh_read;
201 sbi->s_bmap_bh = bh;
202 sbi->s_last_bmap = bmap;
203 }
204
205 /* find an unused block in this bitmap block */
206 bit = blk % sbi->s_bmap_bits;
207 data = (__be32 *)bh->b_data + bit / 32 + 1;
208 enddata = (__be32 *)((u8 *)bh->b_data + sb->s_blocksize);
209 mask = ~0UL << (bit & 31);
210 blk &= ~31UL;
211
212 tmp = be32_to_cpu(*data);
213 if (tmp & mask)
214 goto find_bit;
215
216 /* scan the rest of the buffer */
217 do {
218 blk += 32;
219 if (++data >= enddata)
220 /* didn't find something, can only happen
221 * if scan didn't start at 0, try next bmap
222 */
223 goto find_bmap;
224 } while (!*data);
225 tmp = be32_to_cpu(*data);
226 mask = ~0;
227
228 find_bit:
229 /* finally look for a free bit in the word */
230 bit = ffs(tmp & mask) - 1;
231 blk += bit + sbi->s_reserved;
232 mask2 = mask = 1 << (bit & 31);
233 AFFS_I(inode)->i_lastalloc = blk;
234
235 /* prealloc as much as possible within this word */
236 while ((mask2 <<= 1)) {
237 if (!(tmp & mask2))
238 break;
239 AFFS_I(inode)->i_pa_cnt++;
240 mask |= mask2;
241 }
242 bm->bm_free -= AFFS_I(inode)->i_pa_cnt + 1;
243
244 *data = cpu_to_be32(tmp & ~mask);
245
246 /* fix checksum */
247 tmp = be32_to_cpu(*(__be32 *)bh->b_data);
248 *(__be32 *)bh->b_data = cpu_to_be32(tmp + mask);
249
250 mark_buffer_dirty(bh);
251 sb->s_dirt = 1;
252
253 mutex_unlock(&sbi->s_bmlock);
254
255 pr_debug("%d\n", blk);
256 return blk;
257
258 err_bh_read:
259 affs_error(sb,"affs_read_block","Cannot read bitmap block %u", bm->bm_key);
260 sbi->s_bmap_bh = NULL;
261 sbi->s_last_bmap = ~0;
262 err_full:
263 mutex_unlock(&sbi->s_bmlock);
264 pr_debug("failed\n");
265 return 0;
266 }
267
268 int affs_init_bitmap(struct super_block *sb, int *flags)
269 {
270 struct affs_bm_info *bm;
271 struct buffer_head *bmap_bh = NULL, *bh = NULL;
272 __be32 *bmap_blk;
273 u32 size, blk, end, offset, mask;
274 int i, res = 0;
275 struct affs_sb_info *sbi = AFFS_SB(sb);
276
277 if (*flags & MS_RDONLY)
278 return 0;
279
280 if (!AFFS_ROOT_TAIL(sb, sbi->s_root_bh)->bm_flag) {
281 printk(KERN_NOTICE "AFFS: Bitmap invalid - mounting %s read only\n",
282 sb->s_id);
283 *flags |= MS_RDONLY;
284 return 0;
285 }
286
287 sbi->s_last_bmap = ~0;
288 sbi->s_bmap_bh = NULL;
289 sbi->s_bmap_bits = sb->s_blocksize * 8 - 32;
290 sbi->s_bmap_count = (sbi->s_partition_size - sbi->s_reserved +
291 sbi->s_bmap_bits - 1) / sbi->s_bmap_bits;
292 size = sbi->s_bmap_count * sizeof(*bm);
293 bm = sbi->s_bitmap = kzalloc(size, GFP_KERNEL);
294 if (!sbi->s_bitmap) {
295 printk(KERN_ERR "AFFS: Bitmap allocation failed\n");
296 return -ENOMEM;
297 }
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
372 out:
373 affs_brelse(bh);
374 affs_brelse(bmap_bh);
375 return res;
376 }
377
378 void 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 }
Linux Btrfs Development