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