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