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
13u32
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("%s()\n", __func__);
21
22	if (sb->s_flags & MS_RDONLY)
23		return 0;
24
25	mutex_lock(&AFFS_SB(sb)->s_bmlock);
26
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
32	mutex_unlock(&AFFS_SB(sb)->s_bmlock);
33
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("%s(%u)\n", __func__, 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
56	mutex_lock(&sbi->s_bmlock);
57
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);
82	affs_mark_sb_dirty(sb);
83	bm->bm_free++;
84
85	mutex_unlock(&sbi->s_bmlock);
86	return;
87
88err_free:
89	affs_warning(sb,"affs_free_block","Trying to free block %u which is already free", block);
90	mutex_unlock(&sbi->s_bmlock);
91	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;
97	mutex_unlock(&sbi->s_bmlock);
98	return;
99
100err_range:
101	affs_error(sb, "affs_free_block","Block %u outside partition", block);
102}
103
104/*
105 * Allocate a block in the given allocation zone.
106 * Since we have to byte-swap the bitmap on little-endian
107 * machines, this is rather expensive. Therefore we will
108 * preallocate up to 16 blocks from the same word, if
109 * possible. We are not doing preallocations in the
110 * header zone, though.
111 */
112
113u32
114affs_alloc_block(struct inode *inode, u32 goal)
115{
116	struct super_block *sb;
117	struct affs_sb_info *sbi;
118	struct affs_bm_info *bm;
119	struct buffer_head *bh;
120	__be32 *data, *enddata;
121	u32 blk, bmap, bit, mask, mask2, tmp;
122	int i;
123
124	sb = inode->i_sb;
125	sbi = AFFS_SB(sb);
126
127	pr_debug("balloc(inode=%lu,goal=%u): ", inode->i_ino, goal);
128
129	if (AFFS_I(inode)->i_pa_cnt) {
130		pr_debug("%d\n", AFFS_I(inode)->i_lastalloc+1);
131		AFFS_I(inode)->i_pa_cnt--;
132		return ++AFFS_I(inode)->i_lastalloc;
133	}
134
135	if (!goal || goal > sbi->s_partition_size) {
136		if (goal)
137			affs_warning(sb, "affs_balloc", "invalid goal %d", goal);
138		//if (!AFFS_I(inode)->i_last_block)
139		//	affs_warning(sb, "affs_balloc", "no last alloc block");
140		goal = sbi->s_reserved;
141	}
142
143	blk = goal - sbi->s_reserved;
144	bmap = blk / sbi->s_bmap_bits;
145	bm = &sbi->s_bitmap[bmap];
146
147	mutex_lock(&sbi->s_bmlock);
148
149	if (bm->bm_free)
150		goto find_bmap_bit;
151
152find_bmap:
153	/* search for the next bmap buffer with free bits */
154	i = sbi->s_bmap_count;
155	do {
156		if (--i < 0)
157			goto err_full;
158		bmap++;
159		bm++;
160		if (bmap < sbi->s_bmap_count)
161			continue;
162		/* restart search at zero */
163		bmap = 0;
164		bm = sbi->s_bitmap;
165	} while (!bm->bm_free);
166	blk = bmap * sbi->s_bmap_bits;
167
168find_bmap_bit:
169
170	bh = sbi->s_bmap_bh;
171	if (sbi->s_last_bmap != bmap) {
172		affs_brelse(bh);
173		bh = affs_bread(sb, bm->bm_key);
174		if (!bh)
175			goto err_bh_read;
176		sbi->s_bmap_bh = bh;
177		sbi->s_last_bmap = bmap;
178	}
179
180	/* find an unused block in this bitmap block */
181	bit = blk % sbi->s_bmap_bits;
182	data = (__be32 *)bh->b_data + bit / 32 + 1;
183	enddata = (__be32 *)((u8 *)bh->b_data + sb->s_blocksize);
184	mask = ~0UL << (bit & 31);
185	blk &= ~31UL;
186
187	tmp = be32_to_cpu(*data);
188	if (tmp & mask)
189		goto find_bit;
190
191	/* scan the rest of the buffer */
192	do {
193		blk += 32;
194		if (++data >= enddata)
195			/* didn't find something, can only happen
196			 * if scan didn't start at 0, try next bmap
197			 */
198			goto find_bmap;
199	} while (!*data);
200	tmp = be32_to_cpu(*data);
201	mask = ~0;
202
203find_bit:
204	/* finally look for a free bit in the word */
205	bit = ffs(tmp & mask) - 1;
206	blk += bit + sbi->s_reserved;
207	mask2 = mask = 1 << (bit & 31);
208	AFFS_I(inode)->i_lastalloc = blk;
209
210	/* prealloc as much as possible within this word */
211	while ((mask2 <<= 1)) {
212		if (!(tmp & mask2))
213			break;
214		AFFS_I(inode)->i_pa_cnt++;
215		mask |= mask2;
216	}
217	bm->bm_free -= AFFS_I(inode)->i_pa_cnt + 1;
218
219	*data = cpu_to_be32(tmp & ~mask);
220
221	/* fix checksum */
222	tmp = be32_to_cpu(*(__be32 *)bh->b_data);
223	*(__be32 *)bh->b_data = cpu_to_be32(tmp + mask);
224
225	mark_buffer_dirty(bh);
226	affs_mark_sb_dirty(sb);
227
228	mutex_unlock(&sbi->s_bmlock);
229
230	pr_debug("%d\n", blk);
231	return blk;
232
233err_bh_read:
234	affs_error(sb,"affs_read_block","Cannot read bitmap block %u", bm->bm_key);
235	sbi->s_bmap_bh = NULL;
236	sbi->s_last_bmap = ~0;
237err_full:
238	mutex_unlock(&sbi->s_bmlock);
239	pr_debug("failed\n");
240	return 0;
241}
242
243int affs_init_bitmap(struct super_block *sb, int *flags)
244{
245	struct affs_bm_info *bm;
246	struct buffer_head *bmap_bh = NULL, *bh = NULL;
247	__be32 *bmap_blk;
248	u32 size, blk, end, offset, mask;
249	int i, res = 0;
250	struct affs_sb_info *sbi = AFFS_SB(sb);
251
252	if (*flags & MS_RDONLY)
253		return 0;
254
255	if (!AFFS_ROOT_TAIL(sb, sbi->s_root_bh)->bm_flag) {
256		pr_notice("Bitmap invalid - mounting %s read only\n", sb->s_id);
257		*flags |= MS_RDONLY;
258		return 0;
259	}
260
261	sbi->s_last_bmap = ~0;
262	sbi->s_bmap_bh = NULL;
263	sbi->s_bmap_bits = sb->s_blocksize * 8 - 32;
264	sbi->s_bmap_count = (sbi->s_partition_size - sbi->s_reserved +
265				 sbi->s_bmap_bits - 1) / sbi->s_bmap_bits;
266	size = sbi->s_bmap_count * sizeof(*bm);
267	bm = sbi->s_bitmap = kzalloc(size, GFP_KERNEL);
268	if (!sbi->s_bitmap) {
269		pr_err("Bitmap allocation failed\n");
270		return -ENOMEM;
271	}
272
273	bmap_blk = (__be32 *)sbi->s_root_bh->b_data;
274	blk = sb->s_blocksize / 4 - 49;
275	end = blk + 25;
276
277	for (i = sbi->s_bmap_count; i > 0; bm++, i--) {
278		affs_brelse(bh);
279
280		bm->bm_key = be32_to_cpu(bmap_blk[blk]);
281		bh = affs_bread(sb, bm->bm_key);
282		if (!bh) {
283			pr_err("Cannot read bitmap\n");
284			res = -EIO;
285			goto out;
286		}
287		if (affs_checksum_block(sb, bh)) {
288			pr_warn("Bitmap %u invalid - mounting %s read only.\n",
289				bm->bm_key, sb->s_id);
290			*flags |= MS_RDONLY;
291			goto out;
292		}
293		pr_debug("read bitmap block %d: %d\n", blk, bm->bm_key);
294		bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4);
295
296		/* Don't try read the extension if this is the last block,
297		 * but we also need the right bm pointer below
298		 */
299		if (++blk < end || i == 1)
300			continue;
301		if (bmap_bh)
302			affs_brelse(bmap_bh);
303		bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk]));
304		if (!bmap_bh) {
305			pr_err("Cannot read bitmap extension\n");
306			res = -EIO;
307			goto out;
308		}
309		bmap_blk = (__be32 *)bmap_bh->b_data;
310		blk = 0;
311		end = sb->s_blocksize / 4 - 1;
312	}
313
314	offset = (sbi->s_partition_size - sbi->s_reserved) % sbi->s_bmap_bits;
315	mask = ~(0xFFFFFFFFU << (offset & 31));
316	pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask);
317	offset = offset / 32 + 1;
318
319	if (mask) {
320		u32 old, new;
321
322		/* Mark unused bits in the last word as allocated */
323		old = be32_to_cpu(((__be32 *)bh->b_data)[offset]);
324		new = old & mask;
325		//if (old != new) {
326			((__be32 *)bh->b_data)[offset] = cpu_to_be32(new);
327			/* fix checksum */
328			//new -= old;
329			//old = be32_to_cpu(*(__be32 *)bh->b_data);
330			//*(__be32 *)bh->b_data = cpu_to_be32(old - new);
331			//mark_buffer_dirty(bh);
332		//}
333		/* correct offset for the bitmap count below */
334		//offset++;
335	}
336	while (++offset < sb->s_blocksize / 4)
337		((__be32 *)bh->b_data)[offset] = 0;
338	((__be32 *)bh->b_data)[0] = 0;
339	((__be32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh));
340	mark_buffer_dirty(bh);
341
342	/* recalculate bitmap count for last block */
343	bm--;
344	bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4);
345
346out:
347	affs_brelse(bh);
348	affs_brelse(bmap_bh);
349	return res;
350}
351
352void affs_free_bitmap(struct super_block *sb)
353{
354	struct affs_sb_info *sbi = AFFS_SB(sb);
355
356	if (!sbi->s_bitmap)
357		return;
358
359	affs_brelse(sbi->s_bmap_bh);
360	sbi->s_bmap_bh = NULL;
361	sbi->s_last_bmap = ~0;
362	kfree(sbi->s_bitmap);
363	sbi->s_bitmap = NULL;
364}
365