1// SPDX-License-Identifier: GPL-2.0
2/*
3 *  linux/fs/affs/bitmap.c
4 *
5 *  (c) 1996 Hans-Joachim Widmaier
6 *
7 *  bitmap.c contains the code that handles all bitmap related stuff -
8 *  block allocation, deallocation, calculation of free space.
9 */
10
11#include <linux/slab.h>
12#include "affs.h"
13
14u32
15affs_count_free_blocks(struct super_block *sb)
16{
17	struct affs_bm_info *bm;
18	u32 free;
19	int i;
20
21	pr_debug("%s()\n", __func__);
22
23	if (sb_rdonly(sb))
24		return 0;
25
26	mutex_lock(&AFFS_SB(sb)->s_bmlock);
27
28	bm = AFFS_SB(sb)->s_bitmap;
29	free = 0;
30	for (i = AFFS_SB(sb)->s_bmap_count; i > 0; bm++, i--)
31		free += bm->bm_free;
32
33	mutex_unlock(&AFFS_SB(sb)->s_bmlock);
34
35	return free;
36}
37
38void
39affs_free_block(struct super_block *sb, u32 block)
40{
41	struct affs_sb_info *sbi = AFFS_SB(sb);
42	struct affs_bm_info *bm;
43	struct buffer_head *bh;
44	u32 blk, bmap, bit, mask, tmp;
45	__be32 *data;
46
47	pr_debug("%s(%u)\n", __func__, block);
48
49	if (block > sbi->s_partition_size)
50		goto err_range;
51
52	blk     = block - sbi->s_reserved;
53	bmap    = blk / sbi->s_bmap_bits;
54	bit     = blk % sbi->s_bmap_bits;
55	bm      = &sbi->s_bitmap[bmap];
56
57	mutex_lock(&sbi->s_bmlock);
58
59	bh = sbi->s_bmap_bh;
60	if (sbi->s_last_bmap != bmap) {
61		affs_brelse(bh);
62		bh = affs_bread(sb, bm->bm_key);
63		if (!bh)
64			goto err_bh_read;
65		sbi->s_bmap_bh = bh;
66		sbi->s_last_bmap = bmap;
67	}
68
69	mask = 1 << (bit & 31);
70	data = (__be32 *)bh->b_data + bit / 32 + 1;
71
72	/* mark block free */
73	tmp = be32_to_cpu(*data);
74	if (tmp & mask)
75		goto err_free;
76	*data = cpu_to_be32(tmp | mask);
77
78	/* fix checksum */
79	tmp = be32_to_cpu(*(__be32 *)bh->b_data);
80	*(__be32 *)bh->b_data = cpu_to_be32(tmp - mask);
81
82	mark_buffer_dirty(bh);
83	affs_mark_sb_dirty(sb);
84	bm->bm_free++;
85
86	mutex_unlock(&sbi->s_bmlock);
87	return;
88
89err_free:
90	affs_warning(sb,"affs_free_block","Trying to free block %u which is already free", block);
91	mutex_unlock(&sbi->s_bmlock);
92	return;
93
94err_bh_read:
95	affs_error(sb,"affs_free_block","Cannot read bitmap block %u", bm->bm_key);
96	sbi->s_bmap_bh = NULL;
97	sbi->s_last_bmap = ~0;
98	mutex_unlock(&sbi->s_bmlock);
99	return;
100
101err_range:
102	affs_error(sb, "affs_free_block","Block %u outside partition", block);
103}
104
105/*
106 * Allocate a block in the given allocation zone.
107 * Since we have to byte-swap the bitmap on little-endian
108 * machines, this is rather expensive. Therefore we will
109 * 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("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
148	mutex_lock(&sbi->s_bmlock);
149
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);
227	affs_mark_sb_dirty(sb);
228
229	mutex_unlock(&sbi->s_bmlock);
230
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:
239	mutex_unlock(&sbi->s_bmlock);
240	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 & SB_RDONLY)
254		return 0;
255
256	if (!AFFS_ROOT_TAIL(sb, sbi->s_root_bh)->bm_flag) {
257		pr_notice("Bitmap invalid - mounting %s read only\n", sb->s_id);
258		*flags |= SB_RDONLY;
259		return 0;
260	}
261
262	sbi->s_last_bmap = ~0;
263	sbi->s_bmap_bh = NULL;
264	sbi->s_bmap_bits = sb->s_blocksize * 8 - 32;
265	sbi->s_bmap_count = (sbi->s_partition_size - sbi->s_reserved +
266				 sbi->s_bmap_bits - 1) / sbi->s_bmap_bits;
267	size = sbi->s_bmap_count * sizeof(*bm);
268	bm = sbi->s_bitmap = kzalloc(size, GFP_KERNEL);
269	if (!sbi->s_bitmap) {
270		pr_err("Bitmap allocation failed\n");
271		return -ENOMEM;
272	}
273
274	bmap_blk = (__be32 *)sbi->s_root_bh->b_data;
275	blk = sb->s_blocksize / 4 - 49;
276	end = blk + 25;
277
278	for (i = sbi->s_bmap_count; i > 0; bm++, i--) {
279		affs_brelse(bh);
280
281		bm->bm_key = be32_to_cpu(bmap_blk[blk]);
282		bh = affs_bread(sb, bm->bm_key);
283		if (!bh) {
284			pr_err("Cannot read bitmap\n");
285			res = -EIO;
286			goto out;
287		}
288		if (affs_checksum_block(sb, bh)) {
289			pr_warn("Bitmap %u invalid - mounting %s read only.\n",
290				bm->bm_key, sb->s_id);
291			*flags |= SB_RDONLY;
292			goto out;
293		}
294		pr_debug("read bitmap block %d: %d\n", blk, bm->bm_key);
295		bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4);
296
297		/* Don't try read the extension if this is the last block,
298		 * but we also need the right bm pointer below
299		 */
300		if (++blk < end || i == 1)
301			continue;
302		if (bmap_bh)
303			affs_brelse(bmap_bh);
304		bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk]));
305		if (!bmap_bh) {
306			pr_err("Cannot read bitmap extension\n");
307			res = -EIO;
308			goto out;
309		}
310		bmap_blk = (__be32 *)bmap_bh->b_data;
311		blk = 0;
312		end = sb->s_blocksize / 4 - 1;
313	}
314
315	offset = (sbi->s_partition_size - sbi->s_reserved) % sbi->s_bmap_bits;
316	mask = ~(0xFFFFFFFFU << (offset & 31));
317	pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask);
318	offset = offset / 32 + 1;
319
320	if (mask) {
321		u32 old, new;
322
323		/* Mark unused bits in the last word as allocated */
324		old = be32_to_cpu(((__be32 *)bh->b_data)[offset]);
325		new = old & mask;
326		//if (old != new) {
327			((__be32 *)bh->b_data)[offset] = cpu_to_be32(new);
328			/* fix checksum */
329			//new -= old;
330			//old = be32_to_cpu(*(__be32 *)bh->b_data);
331			//*(__be32 *)bh->b_data = cpu_to_be32(old - new);
332			//mark_buffer_dirty(bh);
333		//}
334		/* correct offset for the bitmap count below */
335		//offset++;
336	}
337	while (++offset < sb->s_blocksize / 4)
338		((__be32 *)bh->b_data)[offset] = 0;
339	((__be32 *)bh->b_data)[0] = 0;
340	((__be32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh));
341	mark_buffer_dirty(bh);
342
343	/* recalculate bitmap count for last block */
344	bm--;
345	bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4);
346
347out:
348	affs_brelse(bh);
349	affs_brelse(bmap_bh);
350	return res;
351}
352
353void affs_free_bitmap(struct super_block *sb)
354{
355	struct affs_sb_info *sbi = AFFS_SB(sb);
356
357	if (!sbi->s_bitmap)
358		return;
359
360	affs_brelse(sbi->s_bmap_bh);
361	sbi->s_bmap_bh = NULL;
362	sbi->s_last_bmap = ~0;
363	kfree(sbi->s_bitmap);
364	sbi->s_bitmap = NULL;
365}
366