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
ntfs_trim_fs(struct ntfs_volume * vol,struct fstrim_range * range)15 int ntfs_trim_fs(struct ntfs_volume *vol, struct fstrim_range *range)
16 {
17 size_t buf_clusters;
18 pgoff_t index, start_index, end_index;
19 struct file_ra_state *ra;
20 struct folio *folio;
21 unsigned long *bitmap;
22 char *kaddr;
23 u64 end, trimmed = 0, start_buf, end_buf, end_cluster;
24 u64 start_cluster = ntfs_bytes_to_cluster(vol, range->start);
25 u32 dq = bdev_discard_granularity(vol->sb->s_bdev);
26 int ret = 0;
27
28 if (!dq)
29 dq = vol->cluster_size;
30
31 if (start_cluster >= vol->nr_clusters)
32 return -EINVAL;
33
34 if (range->len == (u64)-1)
35 end_cluster = vol->nr_clusters;
36 else {
37 end_cluster = ntfs_bytes_to_cluster(vol,
38 (range->start + range->len + vol->cluster_size - 1));
39 if (end_cluster > vol->nr_clusters)
40 end_cluster = vol->nr_clusters;
41 }
42
43 ra = kzalloc_obj(*ra, GFP_NOFS);
44 if (!ra)
45 return -ENOMEM;
46
47 buf_clusters = PAGE_SIZE * 8;
48 start_index = start_cluster >> 15;
49 end_index = (end_cluster + buf_clusters - 1) >> 15;
50
51 for (index = start_index; index < end_index; index++) {
52 folio = ntfs_get_locked_folio(vol->lcnbmp_ino->i_mapping,
53 index, end_index, ra);
54 if (IS_ERR(folio)) {
55 ret = PTR_ERR(folio);
56 goto out_free;
57 }
58
59 kaddr = kmap_local_folio(folio, 0);
60 bitmap = (unsigned long *)kaddr;
61
62 start_buf = max_t(u64, index * buf_clusters, start_cluster);
63 end_buf = min_t(u64, (index + 1) * buf_clusters, end_cluster);
64
65 end = start_buf;
66 while (end < end_buf) {
67 u64 aligned_start, aligned_end, aligned_count;
68 u64 start = find_next_zero_bit(bitmap, end_buf - start_buf,
69 end - start_buf) + start_buf;
70 if (start >= end_buf)
71 break;
72
73 end = find_next_bit(bitmap, end_buf - start_buf,
74 start - start_buf) + start_buf;
75
76 aligned_start = ALIGN(ntfs_cluster_to_bytes(vol, start), dq);
77 aligned_end = ALIGN_DOWN(ntfs_cluster_to_bytes(vol, end), dq);
78 if (aligned_start >= aligned_end)
79 continue;
80 aligned_count = aligned_end - aligned_start;
81 if (aligned_count >= range->minlen) {
82 ret = blkdev_issue_discard(vol->sb->s_bdev, aligned_start >> 9,
83 aligned_count >> 9, GFP_NOFS);
84 if (ret)
85 goto out_unmap;
86 trimmed += aligned_count;
87 }
88 }
89
90 out_unmap:
91 kunmap_local(kaddr);
92 folio_unlock(folio);
93 folio_put(folio);
94
95 if (ret)
96 goto out_free;
97 }
98
99 range->len = trimmed;
100
101 out_free:
102 kfree(ra);
103 return ret;
104 }
105
106 /*
107 * __ntfs_bitmap_set_bits_in_run - set a run of bits in a bitmap to a value
108 * @vi: vfs inode describing the bitmap
109 * @start_bit: first bit to set
110 * @count: number of bits to set
111 * @value: value to set the bits to (i.e. 0 or 1)
112 * @is_rollback: if 'true' this is a rollback operation
113 *
114 * Set @count bits starting at bit @start_bit in the bitmap described by the
115 * vfs inode @vi to @value, where @value is either 0 or 1.
116 *
117 * @is_rollback should always be 'false', it is for internal use to rollback
118 * errors. You probably want to use ntfs_bitmap_set_bits_in_run() instead.
119 *
120 * Return 0 on success and -errno on error.
121 */
__ntfs_bitmap_set_bits_in_run(struct inode * vi,const s64 start_bit,const s64 count,const u8 value,const bool is_rollback)122 int __ntfs_bitmap_set_bits_in_run(struct inode *vi, const s64 start_bit,
123 const s64 count, const u8 value, const bool is_rollback)
124 {
125 s64 cnt = count;
126 pgoff_t index, end_index;
127 struct address_space *mapping;
128 struct folio *folio;
129 u8 *kaddr;
130 int pos, len, err;
131 u8 bit;
132 struct ntfs_inode *ni = NTFS_I(vi);
133 struct ntfs_volume *vol = ni->vol;
134
135 ntfs_debug("Entering for i_ino 0x%llx, start_bit 0x%llx, count 0x%llx, value %u.%s",
136 ni->mft_no, (unsigned long long)start_bit,
137 (unsigned long long)cnt, (unsigned int)value,
138 is_rollback ? " (rollback)" : "");
139
140 if (start_bit < 0 || cnt < 0 || value > 1)
141 return -EINVAL;
142
143 /*
144 * Calculate the indices for the pages containing the first and last
145 * bits, i.e. @start_bit and @start_bit + @cnt - 1, respectively.
146 */
147 index = start_bit >> (3 + PAGE_SHIFT);
148 end_index = (start_bit + cnt - 1) >> (3 + PAGE_SHIFT);
149
150 /* Get the page containing the first bit (@start_bit). */
151 mapping = vi->i_mapping;
152 folio = read_mapping_folio(mapping, index, NULL);
153 if (IS_ERR(folio)) {
154 if (!is_rollback)
155 ntfs_error(vi->i_sb,
156 "Failed to map first page (error %li), aborting.",
157 PTR_ERR(folio));
158 return PTR_ERR(folio);
159 }
160
161 folio_lock(folio);
162 kaddr = kmap_local_folio(folio, 0);
163
164 /* Set @pos to the position of the byte containing @start_bit. */
165 pos = (start_bit >> 3) & ~PAGE_MASK;
166
167 /* Calculate the position of @start_bit in the first byte. */
168 bit = start_bit & 7;
169
170 /* If the first byte is partial, modify the appropriate bits in it. */
171 if (bit) {
172 u8 *byte = kaddr + pos;
173
174 if (ni->mft_no == FILE_Bitmap)
175 ntfs_set_lcn_empty_bits(vol, index, value, min_t(s64, 8 - bit, cnt));
176 while ((bit & 7) && cnt) {
177 cnt--;
178 if (value)
179 *byte |= 1 << bit++;
180 else
181 *byte &= ~(1 << bit++);
182 }
183 /* If we are done, unmap the page and return success. */
184 if (!cnt)
185 goto done;
186
187 /* Update @pos to the new position. */
188 pos++;
189 }
190 /*
191 * Depending on @value, modify all remaining whole bytes in the page up
192 * to @cnt.
193 */
194 len = min_t(s64, cnt >> 3, PAGE_SIZE - pos);
195 memset(kaddr + pos, value ? 0xff : 0, len);
196 cnt -= len << 3;
197 if (ni->mft_no == FILE_Bitmap)
198 ntfs_set_lcn_empty_bits(vol, index, value, len << 3);
199
200 /* Update @len to point to the first not-done byte in the page. */
201 if (cnt < 8)
202 len += pos;
203
204 /* If we are not in the last page, deal with all subsequent pages. */
205 while (index < end_index) {
206 if (cnt <= 0) {
207 err = -EIO;
208 goto rollback;
209 }
210
211 /* Update @index and get the next folio. */
212 folio_mark_dirty(folio);
213 folio_unlock(folio);
214 kunmap_local(kaddr);
215 folio_put(folio);
216 folio = read_mapping_folio(mapping, ++index, NULL);
217 if (IS_ERR(folio)) {
218 ntfs_error(vi->i_sb,
219 "Failed to map subsequent page (error %li), aborting.",
220 PTR_ERR(folio));
221 err = PTR_ERR(folio);
222 goto rollback;
223 }
224
225 folio_lock(folio);
226 kaddr = kmap_local_folio(folio, 0);
227 /*
228 * Depending on @value, modify all remaining whole bytes in the
229 * page up to @cnt.
230 */
231 len = min_t(s64, cnt >> 3, PAGE_SIZE);
232 memset(kaddr, value ? 0xff : 0, len);
233 cnt -= len << 3;
234 if (ni->mft_no == FILE_Bitmap)
235 ntfs_set_lcn_empty_bits(vol, index, value, len << 3);
236 }
237 /*
238 * The currently mapped page is the last one. If the last byte is
239 * partial, modify the appropriate bits in it. Note, @len is the
240 * position of the last byte inside the page.
241 */
242 if (cnt) {
243 u8 *byte;
244
245 WARN_ON(cnt > 7);
246
247 bit = cnt;
248 byte = kaddr + len;
249 if (ni->mft_no == FILE_Bitmap)
250 ntfs_set_lcn_empty_bits(vol, index, value, bit);
251 while (bit--) {
252 if (value)
253 *byte |= 1 << bit;
254 else
255 *byte &= ~(1 << bit);
256 }
257 }
258 done:
259 /* We are done. Unmap the folio and return success. */
260 folio_mark_dirty(folio);
261 folio_unlock(folio);
262 kunmap_local(kaddr);
263 folio_put(folio);
264 ntfs_debug("Done.");
265 return 0;
266 rollback:
267 /*
268 * Current state:
269 * - no pages are mapped
270 * - @count - @cnt is the number of bits that have been modified
271 */
272 if (is_rollback)
273 return err;
274 if (count != cnt)
275 pos = __ntfs_bitmap_set_bits_in_run(vi, start_bit, count - cnt,
276 value ? 0 : 1, true);
277 else
278 pos = 0;
279 if (!pos) {
280 /* Rollback was successful. */
281 ntfs_error(vi->i_sb,
282 "Failed to map subsequent page (error %i), aborting.",
283 err);
284 } else {
285 /* Rollback failed. */
286 ntfs_error(vi->i_sb,
287 "Failed to map subsequent page (error %i) and rollback failed (error %i). Aborting and leaving inconsistent metadata. Unmount and run chkdsk.",
288 err, pos);
289 NVolSetErrors(NTFS_SB(vi->i_sb));
290 }
291 return err;
292 }
293