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 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 */ 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