blob: a32246b8359e50d99e658040b0e12a0bd8f4c5a1 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
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
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090010#include <linux/slab.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070011#include "affs.h"
12
Linus Torvalds1da177e2005-04-16 15:20:36 -070013u32
14affs_count_free_blocks(struct super_block *sb)
15{
16 struct affs_bm_info *bm;
17 u32 free;
18 int i;
19
20 pr_debug("AFFS: count_free_blocks()\n");
21
22 if (sb->s_flags & MS_RDONLY)
23 return 0;
24
Matthias Kaehlcke7d135a52008-07-25 19:44:51 -070025 mutex_lock(&AFFS_SB(sb)->s_bmlock);
Linus Torvalds1da177e2005-04-16 15:20:36 -070026
27 bm = AFFS_SB(sb)->s_bitmap;
28 free = 0;
29 for (i = AFFS_SB(sb)->s_bmap_count; i > 0; bm++, i--)
30 free += bm->bm_free;
31
Matthias Kaehlcke7d135a52008-07-25 19:44:51 -070032 mutex_unlock(&AFFS_SB(sb)->s_bmlock);
Linus Torvalds1da177e2005-04-16 15:20:36 -070033
34 return free;
35}
36
37void
38affs_free_block(struct super_block *sb, u32 block)
39{
40 struct affs_sb_info *sbi = AFFS_SB(sb);
41 struct affs_bm_info *bm;
42 struct buffer_head *bh;
43 u32 blk, bmap, bit, mask, tmp;
44 __be32 *data;
45
46 pr_debug("AFFS: free_block(%u)\n", block);
47
48 if (block > sbi->s_partition_size)
49 goto err_range;
50
51 blk = block - sbi->s_reserved;
52 bmap = blk / sbi->s_bmap_bits;
53 bit = blk % sbi->s_bmap_bits;
54 bm = &sbi->s_bitmap[bmap];
55
Matthias Kaehlcke7d135a52008-07-25 19:44:51 -070056 mutex_lock(&sbi->s_bmlock);
Linus Torvalds1da177e2005-04-16 15:20:36 -070057
58 bh = sbi->s_bmap_bh;
59 if (sbi->s_last_bmap != bmap) {
60 affs_brelse(bh);
61 bh = affs_bread(sb, bm->bm_key);
62 if (!bh)
63 goto err_bh_read;
64 sbi->s_bmap_bh = bh;
65 sbi->s_last_bmap = bmap;
66 }
67
68 mask = 1 << (bit & 31);
69 data = (__be32 *)bh->b_data + bit / 32 + 1;
70
71 /* mark block free */
72 tmp = be32_to_cpu(*data);
73 if (tmp & mask)
74 goto err_free;
75 *data = cpu_to_be32(tmp | mask);
76
77 /* fix checksum */
78 tmp = be32_to_cpu(*(__be32 *)bh->b_data);
79 *(__be32 *)bh->b_data = cpu_to_be32(tmp - mask);
80
81 mark_buffer_dirty(bh);
Artem Bityutskiy3dd84782012-06-06 18:56:57 +030082 affs_mark_sb_dirty(sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -070083 bm->bm_free++;
84
Matthias Kaehlcke7d135a52008-07-25 19:44:51 -070085 mutex_unlock(&sbi->s_bmlock);
Linus Torvalds1da177e2005-04-16 15:20:36 -070086 return;
87
88err_free:
89 affs_warning(sb,"affs_free_block","Trying to free block %u which is already free", block);
Matthias Kaehlcke7d135a52008-07-25 19:44:51 -070090 mutex_unlock(&sbi->s_bmlock);
Linus Torvalds1da177e2005-04-16 15:20:36 -070091 return;
92
93err_bh_read:
94 affs_error(sb,"affs_free_block","Cannot read bitmap block %u", bm->bm_key);
95 sbi->s_bmap_bh = NULL;
96 sbi->s_last_bmap = ~0;
Matthias Kaehlcke7d135a52008-07-25 19:44:51 -070097 mutex_unlock(&sbi->s_bmlock);
Linus Torvalds1da177e2005-04-16 15:20:36 -070098 return;
99
100err_range:
101 affs_error(sb, "affs_free_block","Block %u outside partition", block);
102 return;
103}
104
105/*
106 * Allocate a block in the given allocation zone.
107 * Since we have to byte-swap the bitmap on little-endian
Daniel Mack3ad2f3f2010-02-03 08:01:28 +0800108 * machines, this is rather expensive. Therefore we will
Linus Torvalds1da177e2005-04-16 15:20:36 -0700109 * preallocate up to 16 blocks from the same word, if
110 * possible. We are not doing preallocations in the
111 * header zone, though.
112 */
113
114u32
115affs_alloc_block(struct inode *inode, u32 goal)
116{
117 struct super_block *sb;
118 struct affs_sb_info *sbi;
119 struct affs_bm_info *bm;
120 struct buffer_head *bh;
121 __be32 *data, *enddata;
122 u32 blk, bmap, bit, mask, mask2, tmp;
123 int i;
124
125 sb = inode->i_sb;
126 sbi = AFFS_SB(sb);
127
128 pr_debug("AFFS: balloc(inode=%lu,goal=%u): ", inode->i_ino, goal);
129
130 if (AFFS_I(inode)->i_pa_cnt) {
131 pr_debug("%d\n", AFFS_I(inode)->i_lastalloc+1);
132 AFFS_I(inode)->i_pa_cnt--;
133 return ++AFFS_I(inode)->i_lastalloc;
134 }
135
136 if (!goal || goal > sbi->s_partition_size) {
137 if (goal)
138 affs_warning(sb, "affs_balloc", "invalid goal %d", goal);
139 //if (!AFFS_I(inode)->i_last_block)
140 // affs_warning(sb, "affs_balloc", "no last alloc block");
141 goal = sbi->s_reserved;
142 }
143
144 blk = goal - sbi->s_reserved;
145 bmap = blk / sbi->s_bmap_bits;
146 bm = &sbi->s_bitmap[bmap];
147
Matthias Kaehlcke7d135a52008-07-25 19:44:51 -0700148 mutex_lock(&sbi->s_bmlock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700149
150 if (bm->bm_free)
151 goto find_bmap_bit;
152
153find_bmap:
154 /* search for the next bmap buffer with free bits */
155 i = sbi->s_bmap_count;
156 do {
157 if (--i < 0)
158 goto err_full;
159 bmap++;
160 bm++;
161 if (bmap < sbi->s_bmap_count)
162 continue;
163 /* restart search at zero */
164 bmap = 0;
165 bm = sbi->s_bitmap;
166 } while (!bm->bm_free);
167 blk = bmap * sbi->s_bmap_bits;
168
169find_bmap_bit:
170
171 bh = sbi->s_bmap_bh;
172 if (sbi->s_last_bmap != bmap) {
173 affs_brelse(bh);
174 bh = affs_bread(sb, bm->bm_key);
175 if (!bh)
176 goto err_bh_read;
177 sbi->s_bmap_bh = bh;
178 sbi->s_last_bmap = bmap;
179 }
180
181 /* find an unused block in this bitmap block */
182 bit = blk % sbi->s_bmap_bits;
183 data = (__be32 *)bh->b_data + bit / 32 + 1;
184 enddata = (__be32 *)((u8 *)bh->b_data + sb->s_blocksize);
185 mask = ~0UL << (bit & 31);
186 blk &= ~31UL;
187
188 tmp = be32_to_cpu(*data);
189 if (tmp & mask)
190 goto find_bit;
191
192 /* scan the rest of the buffer */
193 do {
194 blk += 32;
195 if (++data >= enddata)
196 /* didn't find something, can only happen
197 * if scan didn't start at 0, try next bmap
198 */
199 goto find_bmap;
200 } while (!*data);
201 tmp = be32_to_cpu(*data);
202 mask = ~0;
203
204find_bit:
205 /* finally look for a free bit in the word */
206 bit = ffs(tmp & mask) - 1;
207 blk += bit + sbi->s_reserved;
208 mask2 = mask = 1 << (bit & 31);
209 AFFS_I(inode)->i_lastalloc = blk;
210
211 /* prealloc as much as possible within this word */
212 while ((mask2 <<= 1)) {
213 if (!(tmp & mask2))
214 break;
215 AFFS_I(inode)->i_pa_cnt++;
216 mask |= mask2;
217 }
218 bm->bm_free -= AFFS_I(inode)->i_pa_cnt + 1;
219
220 *data = cpu_to_be32(tmp & ~mask);
221
222 /* fix checksum */
223 tmp = be32_to_cpu(*(__be32 *)bh->b_data);
224 *(__be32 *)bh->b_data = cpu_to_be32(tmp + mask);
225
226 mark_buffer_dirty(bh);
Artem Bityutskiy3dd84782012-06-06 18:56:57 +0300227 affs_mark_sb_dirty(sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700228
Matthias Kaehlcke7d135a52008-07-25 19:44:51 -0700229 mutex_unlock(&sbi->s_bmlock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700230
231 pr_debug("%d\n", blk);
232 return blk;
233
234err_bh_read:
235 affs_error(sb,"affs_read_block","Cannot read bitmap block %u", bm->bm_key);
236 sbi->s_bmap_bh = NULL;
237 sbi->s_last_bmap = ~0;
238err_full:
Matthias Kaehlcke7d135a52008-07-25 19:44:51 -0700239 mutex_unlock(&sbi->s_bmlock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700240 pr_debug("failed\n");
241 return 0;
242}
243
244int affs_init_bitmap(struct super_block *sb, int *flags)
245{
246 struct affs_bm_info *bm;
247 struct buffer_head *bmap_bh = NULL, *bh = NULL;
248 __be32 *bmap_blk;
249 u32 size, blk, end, offset, mask;
250 int i, res = 0;
251 struct affs_sb_info *sbi = AFFS_SB(sb);
252
253 if (*flags & MS_RDONLY)
254 return 0;
255
256 if (!AFFS_ROOT_TAIL(sb, sbi->s_root_bh)->bm_flag) {
257 printk(KERN_NOTICE "AFFS: Bitmap invalid - mounting %s read only\n",
258 sb->s_id);
259 *flags |= MS_RDONLY;
260 return 0;
261 }
262
263 sbi->s_last_bmap = ~0;
264 sbi->s_bmap_bh = NULL;
265 sbi->s_bmap_bits = sb->s_blocksize * 8 - 32;
266 sbi->s_bmap_count = (sbi->s_partition_size - sbi->s_reserved +
267 sbi->s_bmap_bits - 1) / sbi->s_bmap_bits;
268 size = sbi->s_bmap_count * sizeof(*bm);
Yan Burmanb593e482006-12-06 20:40:32 -0800269 bm = sbi->s_bitmap = kzalloc(size, GFP_KERNEL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700270 if (!sbi->s_bitmap) {
271 printk(KERN_ERR "AFFS: Bitmap allocation failed\n");
272 return -ENOMEM;
273 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700274
275 bmap_blk = (__be32 *)sbi->s_root_bh->b_data;
276 blk = sb->s_blocksize / 4 - 49;
277 end = blk + 25;
278
279 for (i = sbi->s_bmap_count; i > 0; bm++, i--) {
280 affs_brelse(bh);
281
282 bm->bm_key = be32_to_cpu(bmap_blk[blk]);
283 bh = affs_bread(sb, bm->bm_key);
284 if (!bh) {
285 printk(KERN_ERR "AFFS: Cannot read bitmap\n");
286 res = -EIO;
287 goto out;
288 }
289 if (affs_checksum_block(sb, bh)) {
290 printk(KERN_WARNING "AFFS: Bitmap %u invalid - mounting %s read only.\n",
291 bm->bm_key, sb->s_id);
292 *flags |= MS_RDONLY;
293 goto out;
294 }
295 pr_debug("AFFS: read bitmap block %d: %d\n", blk, bm->bm_key);
Akinobu Mita0121ad62012-07-30 14:41:00 -0700296 bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700297
298 /* Don't try read the extension if this is the last block,
299 * but we also need the right bm pointer below
300 */
301 if (++blk < end || i == 1)
302 continue;
303 if (bmap_bh)
304 affs_brelse(bmap_bh);
305 bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk]));
306 if (!bmap_bh) {
307 printk(KERN_ERR "AFFS: Cannot read bitmap extension\n");
308 res = -EIO;
309 goto out;
310 }
311 bmap_blk = (__be32 *)bmap_bh->b_data;
312 blk = 0;
313 end = sb->s_blocksize / 4 - 1;
314 }
315
316 offset = (sbi->s_partition_size - sbi->s_reserved) % sbi->s_bmap_bits;
317 mask = ~(0xFFFFFFFFU << (offset & 31));
318 pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask);
319 offset = offset / 32 + 1;
320
321 if (mask) {
322 u32 old, new;
323
324 /* Mark unused bits in the last word as allocated */
325 old = be32_to_cpu(((__be32 *)bh->b_data)[offset]);
326 new = old & mask;
327 //if (old != new) {
328 ((__be32 *)bh->b_data)[offset] = cpu_to_be32(new);
329 /* fix checksum */
330 //new -= old;
331 //old = be32_to_cpu(*(__be32 *)bh->b_data);
332 //*(__be32 *)bh->b_data = cpu_to_be32(old - new);
333 //mark_buffer_dirty(bh);
334 //}
335 /* correct offset for the bitmap count below */
336 //offset++;
337 }
338 while (++offset < sb->s_blocksize / 4)
339 ((__be32 *)bh->b_data)[offset] = 0;
340 ((__be32 *)bh->b_data)[0] = 0;
341 ((__be32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh));
342 mark_buffer_dirty(bh);
343
344 /* recalculate bitmap count for last block */
345 bm--;
Akinobu Mita0121ad62012-07-30 14:41:00 -0700346 bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700347
348out:
349 affs_brelse(bh);
350 affs_brelse(bmap_bh);
351 return res;
352}
353
354void affs_free_bitmap(struct super_block *sb)
355{
356 struct affs_sb_info *sbi = AFFS_SB(sb);
357
358 if (!sbi->s_bitmap)
359 return;
360
361 affs_brelse(sbi->s_bmap_bh);
362 sbi->s_bmap_bh = NULL;
363 sbi->s_last_bmap = ~0;
364 kfree(sbi->s_bitmap);
365 sbi->s_bitmap = NULL;
366}