xref: /linux/fs/ntfs/bitmap.c (revision 8506a8031ebfa0e60aaffe7cf4170826399b1f24)
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3  * NTFS kernel bitmap handling.
4  *
5  * Copyright (c) 2004-2005 Anton Altaparmakov
6  * Copyright (c) 2025 LG Electronics Co., Ltd.
7  */
8 
9 #include <linux/bitops.h>
10 #include <linux/blkdev.h>
11 
12 #include "bitmap.h"
13 #include "ntfs.h"
14 
15 /*
16  * Check a $BadClus run against $Bitmap and optionally reserve its free bits.
17  * This is only used during mount, before the free-space scan starts. The
18  * scan will account for the repaired bits, so do not use the regular bitmap
19  * setters, which wait for that scan and assume every bit changes state.
20  * @free_bits counts only bits that were free, including on read-only mounts.
21  */
22 int ntfs_bitmap_check_used(struct ntfs_volume *vol, s64 start, s64 count,
23 		bool repair, s64 *free_bits)
24 {
25 	struct address_space *mapping = vol->lcnbmp_ino->i_mapping;
26 	const unsigned int bits_per_page = PAGE_SIZE * BITS_PER_BYTE;
27 	struct folio *folio;
28 	u8 *bitmap;
29 	unsigned int bit, end, bits;
30 	s64 nr_free;
31 
32 	if (start < 0 || count <= 0 || start >= vol->nr_clusters ||
33 	    count > vol->nr_clusters - start || NVolFreeClusterKnown(vol))
34 		return -EINVAL;
35 	if (repair && sb_rdonly(vol->sb))
36 		return -EROFS;
37 
38 	while (count) {
39 		folio = read_mapping_folio(mapping,
40 					   start >> (PAGE_SHIFT + 3), NULL);
41 		if (IS_ERR(folio))
42 			return PTR_ERR(folio);
43 
44 		folio_lock(folio);
45 		bitmap = kmap_local_folio(folio, 0);
46 		bit = start & (bits_per_page - 1);
47 		bits = min_t(s64, count, bits_per_page - bit);
48 		end = bit + bits;
49 		nr_free = 0;
50 		for (bit = find_next_zero_bit_le(bitmap, end, bit); bit < end;
51 		     bit = find_next_zero_bit_le(bitmap, end, bit + 1)) {
52 			nr_free++;
53 			if (repair)
54 				__set_bit_le(bit, bitmap);
55 		}
56 		kunmap_local(bitmap);
57 		if (repair && nr_free)
58 			folio_mark_dirty(folio);
59 		folio_unlock(folio);
60 		folio_put(folio);
61 		*free_bits += nr_free;
62 		start += bits;
63 		count -= bits;
64 	}
65 	return 0;
66 }
67 
68 int ntfs_trim_fs(struct ntfs_volume *vol, struct fstrim_range *range)
69 {
70 	size_t buf_clusters;
71 	pgoff_t index, start_index, end_index;
72 	struct file_ra_state *ra;
73 	struct folio *folio;
74 	unsigned long *bitmap;
75 	char *kaddr;
76 	u64 end, trimmed = 0, start_buf, end_buf, end_cluster, page_cluster;
77 	u64 start_cluster = ntfs_bytes_to_cluster(vol, range->start);
78 	u32 dq = bdev_discard_granularity(vol->sb->s_bdev);
79 	int ret = 0;
80 
81 	if (!dq)
82 		dq = vol->cluster_size;
83 
84 	if (start_cluster >= vol->nr_clusters)
85 		return -EINVAL;
86 
87 	if (range->len == (u64)-1)
88 		end_cluster = vol->nr_clusters;
89 	else {
90 		end_cluster = ntfs_bytes_to_cluster(vol,
91 				(range->start + range->len + vol->cluster_size - 1));
92 		if (end_cluster > vol->nr_clusters)
93 			end_cluster = vol->nr_clusters;
94 	}
95 
96 	ra = kzalloc_obj(*ra, GFP_NOFS);
97 	if (!ra)
98 		return -ENOMEM;
99 
100 	buf_clusters = PAGE_SIZE * 8;
101 	start_index = start_cluster / buf_clusters;
102 	end_index = DIV_ROUND_UP_ULL(end_cluster, buf_clusters);
103 
104 	for (index = start_index; index < end_index; index++) {
105 		folio = ntfs_get_locked_folio(vol->lcnbmp_ino->i_mapping,
106 				index, end_index, ra);
107 		if (IS_ERR(folio)) {
108 			ret = PTR_ERR(folio);
109 			goto out_free;
110 		}
111 
112 		kaddr = kmap_local_folio(folio, 0);
113 		bitmap = (unsigned long *)kaddr;
114 
115 		page_cluster = (u64)index * buf_clusters;
116 		start_buf = max_t(u64, page_cluster, start_cluster);
117 		end_buf = min_t(u64, page_cluster + buf_clusters, end_cluster);
118 
119 		end = start_buf;
120 		while (end < end_buf) {
121 			u64 aligned_start, aligned_end, aligned_count;
122 			u64 start = find_next_zero_bit(bitmap, end_buf - page_cluster,
123 					end - page_cluster) + page_cluster;
124 			if (start >= end_buf)
125 				break;
126 
127 			end = find_next_bit(bitmap, end_buf - page_cluster,
128 					start - page_cluster) + page_cluster;
129 
130 			aligned_start = ALIGN(ntfs_cluster_to_bytes(vol, start), dq);
131 			aligned_end = ALIGN_DOWN(ntfs_cluster_to_bytes(vol, end), dq);
132 			if (aligned_start >= aligned_end)
133 				continue;
134 			aligned_count = aligned_end - aligned_start;
135 			if (aligned_count >= range->minlen) {
136 				ret = blkdev_issue_discard(vol->sb->s_bdev, aligned_start >> 9,
137 						aligned_count >> 9, GFP_NOFS);
138 				if (ret)
139 					goto out_unmap;
140 				trimmed += aligned_count;
141 			}
142 		}
143 
144 out_unmap:
145 		kunmap_local(kaddr);
146 		folio_unlock(folio);
147 		folio_put(folio);
148 
149 		if (ret)
150 			goto out_free;
151 	}
152 
153 	range->len = trimmed;
154 
155 out_free:
156 	kfree(ra);
157 	return ret;
158 }
159 
160 /*
161  * __ntfs_bitmap_set_bits_in_run - set a run of bits in a bitmap to a value
162  * @vi:			vfs inode describing the bitmap
163  * @start_bit:		first bit to set
164  * @count:		number of bits to set
165  * @value:		value to set the bits to (i.e. 0 or 1)
166  * @is_rollback:	if 'true' this is a rollback operation
167  *
168  * Set @count bits starting at bit @start_bit in the bitmap described by the
169  * vfs inode @vi to @value, where @value is either 0 or 1.
170  *
171  * @is_rollback should always be 'false', it is for internal use to rollback
172  * errors.  You probably want to use ntfs_bitmap_set_bits_in_run() instead.
173  *
174  * Return 0 on success and -errno on error.
175  */
176 int __ntfs_bitmap_set_bits_in_run(struct inode *vi, const s64 start_bit,
177 		const s64 count, const u8 value, const bool is_rollback)
178 {
179 	s64 cnt = count;
180 	pgoff_t index, end_index;
181 	struct address_space *mapping;
182 	struct folio *folio;
183 	u8 *kaddr;
184 	int pos, len, err;
185 	u8 bit;
186 	struct ntfs_inode *ni = NTFS_I(vi);
187 	struct ntfs_volume *vol = ni->vol;
188 
189 	ntfs_debug("Entering for i_ino 0x%llx, start_bit 0x%llx, count 0x%llx, value %u.%s",
190 			ni->mft_no, (unsigned long long)start_bit,
191 			(unsigned long long)cnt, (unsigned int)value,
192 			is_rollback ? " (rollback)" : "");
193 
194 	if (start_bit < 0 || cnt < 0 || value > 1)
195 		return -EINVAL;
196 
197 	/*
198 	 * Calculate the indices for the pages containing the first and last
199 	 * bits, i.e. @start_bit and @start_bit + @cnt - 1, respectively.
200 	 */
201 	index = start_bit >> (3 + PAGE_SHIFT);
202 	end_index = (start_bit + cnt - 1) >> (3 + PAGE_SHIFT);
203 
204 	/* Get the page containing the first bit (@start_bit). */
205 	mapping = vi->i_mapping;
206 	folio = read_mapping_folio(mapping, index, NULL);
207 	if (IS_ERR(folio)) {
208 		if (!is_rollback)
209 			ntfs_error(vi->i_sb,
210 				"Failed to map first page (error %li), aborting.",
211 				PTR_ERR(folio));
212 		return PTR_ERR(folio);
213 	}
214 
215 	folio_lock(folio);
216 	kaddr = kmap_local_folio(folio, 0);
217 
218 	/* Set @pos to the position of the byte containing @start_bit. */
219 	pos = (start_bit >> 3) & ~PAGE_MASK;
220 
221 	/* Calculate the position of @start_bit in the first byte. */
222 	bit = start_bit & 7;
223 
224 	/* If the first byte is partial, modify the appropriate bits in it. */
225 	if (bit) {
226 		u8 *byte = kaddr + pos;
227 
228 		if (ni->mft_no == FILE_Bitmap)
229 			ntfs_set_lcn_empty_bits(vol, index, value, min_t(s64, 8 - bit, cnt));
230 		while ((bit & 7) && cnt) {
231 			cnt--;
232 			if (value)
233 				*byte |= 1 << bit++;
234 			else
235 				*byte &= ~(1 << bit++);
236 		}
237 		/* If we are done, unmap the page and return success. */
238 		if (!cnt)
239 			goto done;
240 
241 		/* Update @pos to the new position. */
242 		pos++;
243 	}
244 	/*
245 	 * Depending on @value, modify all remaining whole bytes in the page up
246 	 * to @cnt.
247 	 */
248 	len = min_t(s64, cnt >> 3, PAGE_SIZE - pos);
249 	memset(kaddr + pos, value ? 0xff : 0, len);
250 	cnt -= len << 3;
251 	if (ni->mft_no == FILE_Bitmap)
252 		ntfs_set_lcn_empty_bits(vol, index, value, len << 3);
253 
254 	/* Update @len to point to the first not-done byte in the page. */
255 	if (cnt < 8)
256 		len += pos;
257 
258 	/* If we are not in the last page, deal with all subsequent pages. */
259 	while (index < end_index) {
260 		if (cnt <= 0) {
261 			err = -EIO;
262 			goto rollback;
263 		}
264 
265 		/* Update @index and get the next folio. */
266 		folio_mark_dirty(folio);
267 		folio_unlock(folio);
268 		kunmap_local(kaddr);
269 		folio_put(folio);
270 		folio = read_mapping_folio(mapping, ++index, NULL);
271 		if (IS_ERR(folio)) {
272 			ntfs_error(vi->i_sb,
273 				   "Failed to map subsequent page (error %li), aborting.",
274 				   PTR_ERR(folio));
275 			err = PTR_ERR(folio);
276 			goto rollback;
277 		}
278 
279 		folio_lock(folio);
280 		kaddr = kmap_local_folio(folio, 0);
281 		/*
282 		 * Depending on @value, modify all remaining whole bytes in the
283 		 * page up to @cnt.
284 		 */
285 		len = min_t(s64, cnt >> 3, PAGE_SIZE);
286 		memset(kaddr, value ? 0xff : 0, len);
287 		cnt -= len << 3;
288 		if (ni->mft_no == FILE_Bitmap)
289 			ntfs_set_lcn_empty_bits(vol, index, value, len << 3);
290 	}
291 	/*
292 	 * The currently mapped page is the last one.  If the last byte is
293 	 * partial, modify the appropriate bits in it.  Note, @len is the
294 	 * position of the last byte inside the page.
295 	 */
296 	if (cnt) {
297 		u8 *byte;
298 
299 		WARN_ON(cnt > 7);
300 
301 		bit = cnt;
302 		byte = kaddr + len;
303 		if (ni->mft_no == FILE_Bitmap)
304 			ntfs_set_lcn_empty_bits(vol, index, value, bit);
305 		while (bit--) {
306 			if (value)
307 				*byte |= 1 << bit;
308 			else
309 				*byte &= ~(1 << bit);
310 		}
311 	}
312 done:
313 	/* We are done.  Unmap the folio and return success. */
314 	folio_mark_dirty(folio);
315 	folio_unlock(folio);
316 	kunmap_local(kaddr);
317 	folio_put(folio);
318 	ntfs_debug("Done.");
319 	return 0;
320 rollback:
321 	/*
322 	 * Current state:
323 	 *	- no pages are mapped
324 	 *	- @count - @cnt is the number of bits that have been modified
325 	 */
326 	if (is_rollback)
327 		return err;
328 	if (count != cnt)
329 		pos = __ntfs_bitmap_set_bits_in_run(vi, start_bit, count - cnt,
330 				value ? 0 : 1, true);
331 	else
332 		pos = 0;
333 	if (!pos) {
334 		/* Rollback was successful. */
335 		ntfs_error(vi->i_sb,
336 			"Failed to map subsequent page (error %i), aborting.",
337 			err);
338 	} else {
339 		/* Rollback failed. */
340 		ntfs_error(vi->i_sb,
341 			"Failed to map subsequent page (error %i) and rollback failed (error %i). Aborting and leaving inconsistent metadata. Unmount and run chkdsk.",
342 			err, pos);
343 		NVolSetErrors(NTFS_SB(vi->i_sb));
344 	}
345 	return err;
346 }
347