1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * Cluster (de)allocation code. 4 * 5 * Copyright (c) 2004-2005 Anton Altaparmakov 6 * Copyright (c) 2025 LG Electronics Co., Ltd. 7 * 8 * Part of this file is based on code from the NTFS-3G. 9 * and is copyrighted by the respective authors below: 10 * Copyright (c) 2002-2004 Anton Altaparmakov 11 * Copyright (c) 2004 Yura Pakhuchiy 12 * Copyright (c) 2004-2008 Szabolcs Szakacsits 13 * Copyright (c) 2008-2009 Jean-Pierre Andre 14 */ 15 16 #include <linux/blkdev.h> 17 18 #include "lcnalloc.h" 19 #include "bitmap.h" 20 #include "ntfs.h" 21 22 /* 23 * ntfs_cluster_free_from_rl_nolock - free clusters from runlist 24 * @vol: mounted ntfs volume on which to free the clusters 25 * @rl: runlist describing the clusters to free 26 * 27 * Free all the clusters described by the runlist @rl on the volume @vol. In 28 * the case of an error being returned, at least some of the clusters were not 29 * freed. 30 * 31 * Return 0 on success and -errno on error. 32 * 33 * Locking: - The volume lcn bitmap must be locked for writing on entry and is 34 * left locked on return. 35 */ 36 int ntfs_cluster_free_from_rl_nolock(struct ntfs_volume *vol, 37 const struct runlist_element *rl) 38 { 39 struct inode *lcnbmp_vi = vol->lcnbmp_ino; 40 int ret = 0; 41 s64 nr_freed = 0; 42 43 ntfs_debug("Entering."); 44 if (!rl) 45 return 0; 46 47 if (!NVolFreeClusterKnown(vol)) 48 wait_event(vol->free_waitq, NVolFreeClusterKnown(vol)); 49 50 for (; rl->length; rl++) { 51 int err; 52 53 if (rl->lcn < 0) 54 continue; 55 err = ntfs_bitmap_clear_run(lcnbmp_vi, rl->lcn, rl->length); 56 if (likely(!err)) 57 nr_freed += rl->length; 58 else if (!ret || ret == -ENOMEM) 59 ret = err; 60 } 61 ntfs_inc_free_clusters(vol, nr_freed); 62 ntfs_debug("Done."); 63 return ret; 64 } 65 66 static s64 max_empty_bit_range(unsigned char *buf, int size) 67 { 68 int i, j, run = 0; 69 int max_range = 0; 70 s64 start_pos = -1; 71 72 ntfs_debug("Entering\n"); 73 74 i = 0; 75 while (i < size) { 76 switch (*buf) { 77 case 0: 78 do { 79 buf++; 80 run += 8; 81 i++; 82 } while ((i < size) && !*buf); 83 break; 84 case 255: 85 if (run > max_range) { 86 max_range = run; 87 start_pos = (s64)i * 8 - run; 88 } 89 run = 0; 90 do { 91 buf++; 92 i++; 93 } while ((i < size) && (*buf == 255)); 94 break; 95 default: 96 for (j = 0; j < 8; j++) { 97 int bit = *buf & (1 << j); 98 99 if (bit) { 100 if (run > max_range) { 101 max_range = run; 102 start_pos = (s64)i * 8 + (j - run); 103 } 104 run = 0; 105 } else 106 run++; 107 } 108 i++; 109 buf++; 110 } 111 } 112 113 if (run > max_range) 114 start_pos = (s64)i * 8 - run; 115 116 return start_pos; 117 } 118 119 /* 120 * ntfs_cluster_alloc - allocate clusters on an ntfs volume 121 * @vol: mounted ntfs volume on which to allocate clusters 122 * @start_vcn: vcn of the first allocated cluster 123 * @count: number of clusters to allocate 124 * @start_lcn: starting lcn at which to allocate the clusters or -1 if none 125 * @zone: zone from which to allocate (MFT_ZONE or DATA_ZONE) 126 * @is_extension: if true, the caller is extending an attribute 127 * @is_contig: if true, require contiguous allocation 128 * @is_dealloc: if true, the allocation is for deallocation purposes 129 * 130 * Allocate @count clusters preferably starting at cluster @start_lcn or at the 131 * current allocator position if @start_lcn is -1, on the mounted ntfs volume 132 * @vol. @zone is either DATA_ZONE for allocation of normal clusters or 133 * MFT_ZONE for allocation of clusters for the master file table, i.e. the 134 * $MFT/$DATA attribute. 135 * 136 * @start_vcn specifies the vcn of the first allocated cluster. This makes 137 * merging the resulting runlist with the old runlist easier. 138 * 139 * If @is_extension is 'true', the caller is allocating clusters to extend an 140 * attribute and if it is 'false', the caller is allocating clusters to fill a 141 * hole in an attribute. Practically the difference is that if @is_extension 142 * is 'true' the returned runlist will be terminated with LCN_ENOENT and if 143 * @is_extension is 'false' the runlist will be terminated with 144 * LCN_RL_NOT_MAPPED. 145 * 146 * You need to check the return value with IS_ERR(). If this is false, the 147 * function was successful and the return value is a runlist describing the 148 * allocated cluster(s). If IS_ERR() is true, the function failed and 149 * PTR_ERR() gives you the error code. 150 * 151 * Notes on the allocation algorithm 152 * ================================= 153 * 154 * There are two data zones. First is the area between the end of the mft zone 155 * and the end of the volume, and second is the area between the start of the 156 * volume and the start of the mft zone. On unmodified/standard NTFS 1.x 157 * volumes, the second data zone does not exist due to the mft zone being 158 * expanded to cover the start of the volume in order to reserve space for the 159 * mft bitmap attribute. 160 * 161 * This is not the prettiest function but the complexity stems from the need of 162 * implementing the mft vs data zoned approach and from the fact that we have 163 * access to the lcn bitmap in portions of up to 8192 bytes at a time, so we 164 * need to cope with crossing over boundaries of two buffers. Further, the 165 * fact that the allocator allows for caller supplied hints as to the location 166 * of where allocation should begin and the fact that the allocator keeps track 167 * of where in the data zones the next natural allocation should occur, 168 * contribute to the complexity of the function. But it should all be 169 * worthwhile, because this allocator should: 1) be a full implementation of 170 * the MFT zone approach used by Windows NT, 2) cause reduction in 171 * fragmentation, and 3) be speedy in allocations (the code is not optimized 172 * for speed, but the algorithm is, so further speed improvements are probably 173 * possible). 174 * 175 * Locking: - The volume lcn bitmap must be unlocked on entry and is unlocked 176 * on return. 177 * - This function takes the volume lcn bitmap lock for writing and 178 * modifies the bitmap contents. 179 * 180 * Return: Runlist describing the allocated cluster(s) on success, error pointer 181 * on failure. 182 */ 183 struct runlist_element *ntfs_cluster_alloc(struct ntfs_volume *vol, const s64 start_vcn, 184 const s64 count, const s64 start_lcn, 185 const int zone, 186 const bool is_extension, 187 const bool is_contig, 188 const bool is_dealloc) 189 { 190 s64 zone_start, zone_end, bmp_pos, bmp_initial_pos, last_read_pos, lcn; 191 s64 prev_lcn = 0, prev_run_len = 0, mft_zone_size; 192 s64 clusters, free_clusters; 193 loff_t i_size; 194 struct inode *lcnbmp_vi; 195 struct runlist_element *rl = NULL; 196 struct address_space *mapping; 197 struct folio *folio = NULL; 198 u8 *buf = NULL, *byte; 199 int err = 0, rlpos, rlsize, buf_size, pg_off; 200 u8 pass, done_zones, search_zone, need_writeback = 0, bit; 201 unsigned int memalloc_flags; 202 u8 has_guess, used_zone_pos; 203 pgoff_t index; 204 205 ntfs_debug("Entering for start_vcn 0x%llx, count 0x%llx, start_lcn 0x%llx, zone %s_ZONE.", 206 start_vcn, count, start_lcn, 207 zone == MFT_ZONE ? "MFT" : "DATA"); 208 209 lcnbmp_vi = vol->lcnbmp_ino; 210 if (start_vcn < 0 || start_lcn < LCN_HOLE || 211 zone < FIRST_ZONE || zone > LAST_ZONE) 212 return ERR_PTR(-EINVAL); 213 214 /* Return NULL if @count is zero. */ 215 if (count < 0 || !count) 216 return ERR_PTR(-EINVAL); 217 218 memalloc_flags = memalloc_nofs_save(); 219 220 if (!NVolFreeClusterKnown(vol)) 221 wait_event(vol->free_waitq, NVolFreeClusterKnown(vol)); 222 free_clusters = atomic64_read(&vol->free_clusters); 223 224 /* Take the lcnbmp lock for writing. */ 225 down_write(&vol->lcnbmp_lock); 226 if (is_dealloc == false) 227 free_clusters -= atomic64_read(&vol->dirty_clusters); 228 229 if (free_clusters < count) { 230 err = -ENOSPC; 231 goto out_restore; 232 } 233 234 /* 235 * If no specific @start_lcn was requested, use the current data zone 236 * position, otherwise use the requested @start_lcn but make sure it 237 * lies outside the mft zone. Also set done_zones to 0 (no zones done) 238 * and pass depending on whether we are starting inside a zone (1) or 239 * at the beginning of a zone (2). If requesting from the MFT_ZONE, 240 * we either start at the current position within the mft zone or at 241 * the specified position. If the latter is out of bounds then we start 242 * at the beginning of the MFT_ZONE. 243 */ 244 done_zones = 0; 245 pass = 1; 246 /* 247 * zone_start and zone_end are the current search range. search_zone 248 * is 1 for mft zone, 2 for data zone 1 (end of mft zone till end of 249 * volume) and 4 for data zone 2 (start of volume till start of mft 250 * zone). 251 */ 252 has_guess = 1; 253 zone_start = start_lcn; 254 255 if (zone_start < 0) { 256 if (zone == DATA_ZONE) 257 zone_start = vol->data1_zone_pos; 258 else 259 zone_start = vol->mft_zone_pos; 260 if (!zone_start) { 261 /* 262 * Zone starts at beginning of volume which means a 263 * single pass is sufficient. 264 */ 265 pass = 2; 266 } 267 has_guess = 0; 268 } 269 270 used_zone_pos = has_guess ? 0 : 1; 271 272 if (!zone_start || zone_start == vol->mft_zone_start || 273 zone_start == vol->mft_zone_end) 274 pass = 2; 275 276 if (zone_start < vol->mft_zone_start) { 277 zone_end = vol->mft_zone_start; 278 search_zone = 4; 279 /* Skip searching the mft zone. */ 280 done_zones |= 1; 281 } else if (zone_start < vol->mft_zone_end) { 282 zone_end = vol->mft_zone_end; 283 search_zone = 1; 284 } else { 285 zone_end = vol->nr_clusters; 286 search_zone = 2; 287 /* Skip searching the mft zone. */ 288 done_zones |= 1; 289 } 290 291 /* 292 * bmp_pos is the current bit position inside the bitmap. We use 293 * bmp_initial_pos to determine whether or not to do a zone switch. 294 */ 295 bmp_pos = bmp_initial_pos = zone_start; 296 297 /* Loop until all clusters are allocated, i.e. clusters == 0. */ 298 clusters = count; 299 rlpos = rlsize = 0; 300 mapping = lcnbmp_vi->i_mapping; 301 /* 302 * lcn_empty_bits_per_page is sized from nr_clusters, but $Bitmap can 303 * cover more clusters than that; bound the scan by the array. 304 */ 305 i_size = min_t(s64, i_size_read(lcnbmp_vi), 306 ((s64)vol->nr_clusters + 7) >> 3); 307 while (1) { 308 ntfs_debug("Start of outer while loop: done_zones 0x%x, search_zone %i, pass %i, zone_start 0x%llx, zone_end 0x%llx, bmp_initial_pos 0x%llx, bmp_pos 0x%llx, rlpos %i, rlsize %i.", 309 done_zones, search_zone, pass, 310 zone_start, zone_end, bmp_initial_pos, 311 bmp_pos, rlpos, rlsize); 312 /* Loop until we run out of free clusters. */ 313 last_read_pos = bmp_pos >> 3; 314 ntfs_debug("last_read_pos 0x%llx.", last_read_pos); 315 if (last_read_pos >= i_size) { 316 ntfs_debug("End of attribute reached. Skipping to zone_pass_done."); 317 goto zone_pass_done; 318 } 319 if (likely(folio)) { 320 if (need_writeback) { 321 ntfs_debug("Marking page dirty."); 322 folio_mark_dirty(folio); 323 need_writeback = 0; 324 } 325 folio_unlock(folio); 326 kunmap_local(buf); 327 folio_put(folio); 328 folio = NULL; 329 } 330 331 index = last_read_pos >> PAGE_SHIFT; 332 pg_off = last_read_pos & ~PAGE_MASK; 333 buf_size = PAGE_SIZE - pg_off; 334 if (unlikely(last_read_pos + buf_size > i_size)) 335 buf_size = i_size - last_read_pos; 336 buf_size <<= 3; 337 lcn = bmp_pos & 7; 338 bmp_pos &= ~(s64)7; 339 340 if (vol->lcn_empty_bits_per_page[index] == 0) 341 goto next_bmp_pos; 342 343 folio = read_mapping_folio(mapping, index, NULL); 344 if (IS_ERR(folio)) { 345 err = PTR_ERR(folio); 346 ntfs_error(vol->sb, "Failed to map page."); 347 goto out; 348 } 349 350 folio_lock(folio); 351 buf = kmap_local_folio(folio, 0) + pg_off; 352 ntfs_debug("Before inner while loop: buf_size %i, lcn 0x%llx, bmp_pos 0x%llx, need_writeback %i.", 353 buf_size, lcn, bmp_pos, need_writeback); 354 while (lcn < buf_size && lcn + bmp_pos < zone_end) { 355 byte = buf + (lcn >> 3); 356 ntfs_debug("In inner while loop: buf_size %i, lcn 0x%llx, bmp_pos 0x%llx, need_writeback %i, byte ofs 0x%x, *byte 0x%x.", 357 buf_size, lcn, bmp_pos, need_writeback, 358 (unsigned int)(lcn >> 3), 359 (unsigned int)*byte); 360 bit = 1 << (lcn & 7); 361 ntfs_debug("bit 0x%x.", bit); 362 363 if (has_guess) { 364 if (*byte & bit) { 365 if (is_contig == true && prev_run_len > 0) 366 goto done; 367 368 has_guess = 0; 369 break; 370 } 371 } else { 372 lcn = max_empty_bit_range(buf, buf_size >> 3); 373 if (lcn < 0) 374 break; 375 has_guess = 1; 376 continue; 377 } 378 /* 379 * A contiguous request gets a single run. The scan can 380 * move on without testing the clusters after the run 381 * (past a bitmap page that is full, to pass 2 or to 382 * another zone), so return the run when this cluster 383 * does not follow it. 384 */ 385 if (is_contig && rlpos && 386 lcn + bmp_pos != prev_lcn + prev_run_len) 387 goto out; 388 /* 389 * Allocate more memory if needed, including space for 390 * the terminator element. 391 * kvzalloc() operates on whole pages only. 392 */ 393 if ((rlpos + 2) * sizeof(*rl) > rlsize) { 394 struct runlist_element *rl2; 395 396 ntfs_debug("Reallocating memory."); 397 if (!rl) 398 ntfs_debug("First free bit is at s64 0x%llx.", 399 lcn + bmp_pos); 400 rl2 = kvzalloc(rlsize + PAGE_SIZE, GFP_NOFS); 401 if (unlikely(!rl2)) { 402 err = -ENOMEM; 403 ntfs_error(vol->sb, "Failed to allocate memory."); 404 goto out; 405 } 406 memcpy(rl2, rl, rlsize); 407 kvfree(rl); 408 rl = rl2; 409 rlsize += PAGE_SIZE; 410 ntfs_debug("Reallocated memory, rlsize 0x%x.", 411 rlsize); 412 } 413 /* Allocate the bitmap bit. */ 414 *byte |= bit; 415 /* We need to write this bitmap page to disk. */ 416 need_writeback = 1; 417 ntfs_debug("*byte 0x%x, need_writeback is set.", 418 (unsigned int)*byte); 419 ntfs_dec_free_clusters(vol, 1); 420 ntfs_set_lcn_empty_bits(vol, index, 1, 1); 421 422 /* 423 * Coalesce with previous run if adjacent LCNs. 424 * Otherwise, append a new run. 425 */ 426 ntfs_debug("Adding run (lcn 0x%llx, len 0x%llx), prev_lcn 0x%llx, lcn 0x%llx, bmp_pos 0x%llx, prev_run_len 0x%llx, rlpos %i.", 427 lcn + bmp_pos, 1ULL, prev_lcn, 428 lcn, bmp_pos, prev_run_len, rlpos); 429 if (prev_lcn == lcn + bmp_pos - prev_run_len && rlpos) { 430 ntfs_debug("Coalescing to run (lcn 0x%llx, len 0x%llx).", 431 rl[rlpos - 1].lcn, 432 rl[rlpos - 1].length); 433 rl[rlpos - 1].length = ++prev_run_len; 434 ntfs_debug("Run now (lcn 0x%llx, len 0x%llx), prev_run_len 0x%llx.", 435 rl[rlpos - 1].lcn, 436 rl[rlpos - 1].length, 437 prev_run_len); 438 } else { 439 if (likely(rlpos)) { 440 ntfs_debug("Adding new run, (previous run lcn 0x%llx, len 0x%llx).", 441 rl[rlpos - 1].lcn, rl[rlpos - 1].length); 442 rl[rlpos].vcn = rl[rlpos - 1].vcn + 443 prev_run_len; 444 } else { 445 ntfs_debug("Adding new run, is first run."); 446 rl[rlpos].vcn = start_vcn; 447 } 448 rl[rlpos].lcn = prev_lcn = lcn + bmp_pos; 449 rl[rlpos].length = prev_run_len = 1; 450 rlpos++; 451 } 452 /* Done? */ 453 if (!--clusters) { 454 s64 tc; 455 done: 456 if (!used_zone_pos) 457 goto out; 458 /* 459 * Update the current zone position. Positions 460 * of already scanned zones have been updated 461 * during the respective zone switches. 462 */ 463 tc = lcn + bmp_pos + 1; 464 ntfs_debug("Done. Updating current zone position, tc 0x%llx, search_zone %i.", 465 tc, search_zone); 466 switch (search_zone) { 467 case 1: 468 ntfs_debug("Before checks, vol->mft_zone_pos 0x%llx.", 469 vol->mft_zone_pos); 470 if (tc >= vol->mft_zone_end) { 471 vol->mft_zone_pos = 472 vol->mft_lcn; 473 if (!vol->mft_zone_end) 474 vol->mft_zone_pos = 0; 475 } else if ((bmp_initial_pos >= 476 vol->mft_zone_pos || 477 tc > vol->mft_zone_pos) 478 && tc >= vol->mft_lcn) 479 vol->mft_zone_pos = tc; 480 ntfs_debug("After checks, vol->mft_zone_pos 0x%llx.", 481 vol->mft_zone_pos); 482 break; 483 case 2: 484 ntfs_debug("Before checks, vol->data1_zone_pos 0x%llx.", 485 vol->data1_zone_pos); 486 if (tc >= vol->nr_clusters) 487 vol->data1_zone_pos = 488 vol->mft_zone_end; 489 else if ((bmp_initial_pos >= 490 vol->data1_zone_pos || 491 tc > vol->data1_zone_pos) 492 && tc >= vol->mft_zone_end) 493 vol->data1_zone_pos = tc; 494 ntfs_debug("After checks, vol->data1_zone_pos 0x%llx.", 495 vol->data1_zone_pos); 496 break; 497 case 4: 498 ntfs_debug("Before checks, vol->data2_zone_pos 0x%llx.", 499 vol->data2_zone_pos); 500 if (tc >= vol->mft_zone_start) 501 vol->data2_zone_pos = 0; 502 else if (bmp_initial_pos >= 503 vol->data2_zone_pos || 504 tc > vol->data2_zone_pos) 505 vol->data2_zone_pos = tc; 506 ntfs_debug("After checks, vol->data2_zone_pos 0x%llx.", 507 vol->data2_zone_pos); 508 break; 509 default: 510 WARN_ON(1); 511 } 512 ntfs_debug("Finished. Going to out."); 513 goto out; 514 } 515 lcn++; 516 } 517 518 if (!used_zone_pos) { 519 /* 520 * The run at @start_lcn reached the end of the buffer 521 * or the zone. A contiguous request gets that run 522 * alone, not a second one from the zone position. 523 */ 524 if (is_contig && rlpos) 525 goto out; 526 /* 527 * Leaving @start_lcn for the zone position starts the 528 * zone over as if no hint had been given, even if the 529 * search had already reached pass 2, whose range ends 530 * at @start_lcn. 531 */ 532 used_zone_pos = 1; 533 has_guess = 0; 534 pass = 1; 535 if (search_zone == 1) { 536 zone_start = vol->mft_zone_pos; 537 zone_end = vol->mft_zone_end; 538 } else if (search_zone == 2) { 539 zone_start = vol->data1_zone_pos; 540 zone_end = vol->nr_clusters; 541 } else { 542 zone_start = vol->data2_zone_pos; 543 zone_end = vol->mft_zone_start; 544 } 545 546 if (!zone_start || zone_start == vol->mft_zone_start || 547 zone_start == vol->mft_zone_end) 548 pass = 2; 549 bmp_pos = zone_start; 550 } else { 551 next_bmp_pos: 552 bmp_pos += buf_size; 553 } 554 555 ntfs_debug("After inner while loop: buf_size 0x%x, lcn 0x%llx, bmp_pos 0x%llx, need_writeback %i.", 556 buf_size, lcn, bmp_pos, need_writeback); 557 if (bmp_pos < zone_end) { 558 ntfs_debug("Continuing outer while loop, bmp_pos 0x%llx, zone_end 0x%llx.", 559 bmp_pos, zone_end); 560 continue; 561 } 562 zone_pass_done: /* Finished with the current zone pass. */ 563 ntfs_debug("At zone_pass_done, pass %i.", pass); 564 if (pass == 1) { 565 /* 566 * Now do pass 2, scanning the first part of the zone 567 * we omitted in pass 1. 568 */ 569 pass = 2; 570 zone_end = zone_start; 571 switch (search_zone) { 572 case 1: /* mft_zone */ 573 zone_start = vol->mft_zone_start; 574 break; 575 case 2: /* data1_zone */ 576 zone_start = vol->mft_zone_end; 577 break; 578 case 4: /* data2_zone */ 579 zone_start = 0; 580 break; 581 default: 582 WARN_ON(1); 583 } 584 /* Sanity check. */ 585 if (zone_end < zone_start) 586 zone_end = zone_start; 587 bmp_pos = zone_start; 588 ntfs_debug("Continuing outer while loop, pass 2, zone_start 0x%llx, zone_end 0x%llx, bmp_pos 0x%llx.", 589 zone_start, zone_end, bmp_pos); 590 continue; 591 } /* pass == 2 */ 592 done_zones_check: 593 ntfs_debug("At done_zones_check, search_zone %i, done_zones before 0x%x, done_zones after 0x%x.", 594 search_zone, done_zones, 595 done_zones | search_zone); 596 done_zones |= search_zone; 597 if (done_zones < 7) { 598 ntfs_debug("Switching zone."); 599 /* Now switch to the next zone we haven't done yet. */ 600 pass = 1; 601 switch (search_zone) { 602 case 1: 603 ntfs_debug("Switching from mft zone to data1 zone."); 604 /* Update mft zone position. */ 605 if (rlpos && used_zone_pos) { 606 s64 tc; 607 608 ntfs_debug("Before checks, vol->mft_zone_pos 0x%llx.", 609 vol->mft_zone_pos); 610 tc = rl[rlpos - 1].lcn + 611 rl[rlpos - 1].length; 612 if (tc >= vol->mft_zone_end) { 613 vol->mft_zone_pos = 614 vol->mft_lcn; 615 if (!vol->mft_zone_end) 616 vol->mft_zone_pos = 0; 617 } else if ((bmp_initial_pos >= 618 vol->mft_zone_pos || 619 tc > vol->mft_zone_pos) 620 && tc >= vol->mft_lcn) 621 vol->mft_zone_pos = tc; 622 ntfs_debug("After checks, vol->mft_zone_pos 0x%llx.", 623 vol->mft_zone_pos); 624 } 625 /* Switch from mft zone to data1 zone. */ 626 switch_to_data1_zone: search_zone = 2; 627 zone_start = bmp_initial_pos = 628 vol->data1_zone_pos; 629 zone_end = vol->nr_clusters; 630 if (zone_start == vol->mft_zone_end) 631 pass = 2; 632 if (zone_start >= zone_end) { 633 vol->data1_zone_pos = zone_start = 634 vol->mft_zone_end; 635 pass = 2; 636 } 637 break; 638 case 2: 639 ntfs_debug("Switching from data1 zone to data2 zone."); 640 /* Update data1 zone position. */ 641 if (rlpos && used_zone_pos) { 642 s64 tc; 643 644 ntfs_debug("Before checks, vol->data1_zone_pos 0x%llx.", 645 vol->data1_zone_pos); 646 tc = rl[rlpos - 1].lcn + 647 rl[rlpos - 1].length; 648 if (tc >= vol->nr_clusters) 649 vol->data1_zone_pos = 650 vol->mft_zone_end; 651 else if ((bmp_initial_pos >= 652 vol->data1_zone_pos || 653 tc > vol->data1_zone_pos) 654 && tc >= vol->mft_zone_end) 655 vol->data1_zone_pos = tc; 656 ntfs_debug("After checks, vol->data1_zone_pos 0x%llx.", 657 vol->data1_zone_pos); 658 } 659 /* Switch from data1 zone to data2 zone. */ 660 search_zone = 4; 661 zone_start = bmp_initial_pos = 662 vol->data2_zone_pos; 663 zone_end = vol->mft_zone_start; 664 if (!zone_start) 665 pass = 2; 666 if (zone_start >= zone_end) { 667 vol->data2_zone_pos = zone_start = 668 bmp_initial_pos = 0; 669 pass = 2; 670 } 671 break; 672 case 4: 673 ntfs_debug("Switching from data2 zone to data1 zone."); 674 /* Update data2 zone position. */ 675 if (rlpos && used_zone_pos) { 676 s64 tc; 677 678 ntfs_debug("Before checks, vol->data2_zone_pos 0x%llx.", 679 vol->data2_zone_pos); 680 tc = rl[rlpos - 1].lcn + 681 rl[rlpos - 1].length; 682 if (tc >= vol->mft_zone_start) 683 vol->data2_zone_pos = 0; 684 else if (bmp_initial_pos >= 685 vol->data2_zone_pos || 686 tc > vol->data2_zone_pos) 687 vol->data2_zone_pos = tc; 688 ntfs_debug("After checks, vol->data2_zone_pos 0x%llx.", 689 vol->data2_zone_pos); 690 } 691 /* Switch from data2 zone to data1 zone. */ 692 goto switch_to_data1_zone; 693 default: 694 WARN_ON(1); 695 } 696 ntfs_debug("After zone switch, search_zone %i, pass %i, bmp_initial_pos 0x%llx, zone_start 0x%llx, zone_end 0x%llx.", 697 search_zone, pass, 698 bmp_initial_pos, 699 zone_start, 700 zone_end); 701 bmp_pos = zone_start; 702 if (zone_start == zone_end) { 703 ntfs_debug("Empty zone, going to done_zones_check."); 704 /* Empty zone. Don't bother searching it. */ 705 goto done_zones_check; 706 } 707 ntfs_debug("Continuing outer while loop."); 708 continue; 709 } /* done_zones == 7 */ 710 ntfs_debug("All zones are finished."); 711 /* 712 * All zones are finished! If DATA_ZONE, shrink mft zone. If 713 * MFT_ZONE, we have really run out of space. 714 */ 715 mft_zone_size = vol->mft_zone_end - vol->mft_zone_start; 716 ntfs_debug("vol->mft_zone_start 0x%llx, vol->mft_zone_end 0x%llx, mft_zone_size 0x%llx.", 717 vol->mft_zone_start, vol->mft_zone_end, 718 mft_zone_size); 719 if (zone == MFT_ZONE || mft_zone_size <= 0) { 720 ntfs_debug("No free clusters left, going to out."); 721 /* Really no more space left on device. */ 722 err = -ENOSPC; 723 goto out; 724 } /* zone == DATA_ZONE && mft_zone_size > 0 */ 725 ntfs_debug("Shrinking mft zone."); 726 zone_end = vol->mft_zone_end; 727 mft_zone_size >>= 1; 728 if (mft_zone_size > 0) 729 vol->mft_zone_end = vol->mft_zone_start + mft_zone_size; 730 else /* mft zone and data2 zone no longer exist. */ 731 vol->data2_zone_pos = vol->mft_zone_start = 732 vol->mft_zone_end = 0; 733 if (vol->mft_zone_pos >= vol->mft_zone_end) { 734 vol->mft_zone_pos = vol->mft_lcn; 735 if (!vol->mft_zone_end) 736 vol->mft_zone_pos = 0; 737 } 738 bmp_pos = zone_start = bmp_initial_pos = 739 vol->data1_zone_pos = vol->mft_zone_end; 740 search_zone = 2; 741 pass = 2; 742 done_zones &= ~2; 743 ntfs_debug("After shrinking mft zone, mft_zone_size 0x%llx, vol->mft_zone_start 0x%llx, vol->mft_zone_end 0x%llx, vol->mft_zone_pos 0x%llx, search_zone 2, pass 2, dones_zones 0x%x, zone_start 0x%llx, zone_end 0x%llx, vol->data1_zone_pos 0x%llx, continuing outer while loop.", 744 mft_zone_size, vol->mft_zone_start, 745 vol->mft_zone_end, vol->mft_zone_pos, 746 done_zones, zone_start, zone_end, 747 vol->data1_zone_pos); 748 } 749 ntfs_debug("After outer while loop."); 750 out: 751 ntfs_debug("At out."); 752 /* Add runlist terminator element. */ 753 if (likely(rl)) { 754 rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length; 755 rl[rlpos].lcn = is_extension ? LCN_ENOENT : LCN_RL_NOT_MAPPED; 756 rl[rlpos].length = 0; 757 } 758 if (!IS_ERR_OR_NULL(folio)) { 759 if (need_writeback) { 760 ntfs_debug("Marking page dirty."); 761 folio_mark_dirty(folio); 762 need_writeback = 0; 763 } 764 folio_unlock(folio); 765 kunmap_local(buf); 766 folio_put(folio); 767 } 768 if (likely(!err)) { 769 if (!rl) { 770 err = -EIO; 771 goto out_restore; 772 } 773 if (is_dealloc == true) 774 ntfs_release_dirty_clusters(vol, rl->length); 775 ntfs_debug("Done."); 776 goto out_restore; 777 } 778 if (err != -ENOSPC) 779 ntfs_error(vol->sb, 780 "Failed to allocate clusters, aborting (error %i).", 781 err); 782 if (rl) { 783 int err2; 784 785 if (err == -ENOSPC) 786 ntfs_debug("Not enough space to complete allocation, err -ENOSPC, first free lcn 0x%llx, could allocate up to 0x%llx clusters.", 787 rl[0].lcn, count - clusters); 788 /* Deallocate all allocated clusters. */ 789 ntfs_debug("Attempting rollback..."); 790 err2 = ntfs_cluster_free_from_rl_nolock(vol, rl); 791 if (err2) { 792 ntfs_error(vol->sb, 793 "Failed to rollback (error %i). Leaving inconsistent metadata! Unmount and run chkdsk.", 794 err2); 795 NVolSetErrors(vol); 796 } 797 /* Free the runlist. */ 798 kvfree(rl); 799 } else if (err == -ENOSPC) 800 ntfs_debug("No space left at all, err = -ENOSPC, first free lcn = 0x%llx.", 801 vol->data1_zone_pos); 802 atomic64_set(&vol->dirty_clusters, 0); 803 804 out_restore: 805 up_write(&vol->lcnbmp_lock); 806 memalloc_nofs_restore(memalloc_flags); 807 808 return err < 0 ? ERR_PTR(err) : rl; 809 } 810 811 /* 812 * __ntfs_cluster_free - free clusters on an ntfs volume 813 * @ni: ntfs inode whose runlist describes the clusters to free 814 * @start_vcn: vcn in the runlist of @ni at which to start freeing clusters 815 * @count: number of clusters to free or -1 for all clusters 816 * @ctx: active attribute search context if present or NULL if not 817 * @is_rollback: true if this is a rollback operation 818 * 819 * Free @count clusters starting at the cluster @start_vcn in the runlist 820 * described by the vfs inode @ni. 821 * 822 * If @count is -1, all clusters from @start_vcn to the end of the runlist are 823 * deallocated. Thus, to completely free all clusters in a runlist, use 824 * @start_vcn = 0 and @count = -1. 825 * 826 * If @ctx is specified, it is an active search context of @ni and its base mft 827 * record. This is needed when __ntfs_cluster_free() encounters unmapped 828 * runlist fragments and allows their mapping. If you do not have the mft 829 * record mapped, you can specify @ctx as NULL and __ntfs_cluster_free() will 830 * perform the necessary mapping and unmapping. 831 * 832 * Note, __ntfs_cluster_free() saves the state of @ctx on entry and restores it 833 * before returning. Thus, @ctx will be left pointing to the same attribute on 834 * return as on entry. However, the actual pointers in @ctx may point to 835 * different memory locations on return, so you must remember to reset any 836 * cached pointers from the @ctx, i.e. after the call to __ntfs_cluster_free(), 837 * you will probably want to do: 838 * m = ctx->mrec; 839 * a = ctx->attr; 840 * Assuming you cache ctx->attr in a variable @a of type attr_record * and that 841 * you cache ctx->mrec in a variable @m of type struct mft_record *. 842 * 843 * @is_rollback should always be 'false', it is for internal use to rollback 844 * errors. You probably want to use ntfs_cluster_free() instead. 845 * 846 * Note, __ntfs_cluster_free() does not modify the runlist, so you have to 847 * remove from the runlist or mark sparse the freed runs later. 848 * 849 * Return the number of deallocated clusters (not counting sparse ones) on 850 * success and -errno on error. 851 * 852 * WARNING: If @ctx is supplied, regardless of whether success or failure is 853 * returned, you need to check IS_ERR(@ctx->mrec) and if 'true' the @ctx 854 * is no longer valid, i.e. you need to either call 855 * ntfs_attr_reinit_search_ctx() or ntfs_attr_put_search_ctx() on it. 856 * In that case PTR_ERR(@ctx->mrec) will give you the error code for 857 * why the mapping of the old inode failed. 858 * 859 * Locking: - The runlist described by @ni must be locked for writing on entry 860 * and is locked on return. Note the runlist may be modified when 861 * needed runlist fragments need to be mapped. 862 * - The volume lcn bitmap must be unlocked on entry and is unlocked 863 * on return. 864 * - This function takes the volume lcn bitmap lock for writing and 865 * modifies the bitmap contents. 866 * - If @ctx is NULL, the base mft record of @ni must not be mapped on 867 * entry and it will be left unmapped on return. 868 * - If @ctx is not NULL, the base mft record must be mapped on entry 869 * and it will be left mapped on return. 870 */ 871 s64 __ntfs_cluster_free(struct ntfs_inode *ni, const s64 start_vcn, s64 count, 872 struct ntfs_attr_search_ctx *ctx, const bool is_rollback) 873 { 874 s64 delta, to_free, total_freed, real_freed; 875 struct ntfs_volume *vol; 876 struct inode *lcnbmp_vi; 877 struct runlist_element *rl; 878 int err; 879 unsigned int memalloc_flags; 880 881 ntfs_debug("Entering for i_ino 0x%llx, start_vcn 0x%llx, count 0x%llx.%s", 882 ni->mft_no, start_vcn, count, 883 is_rollback ? " (rollback)" : ""); 884 vol = ni->vol; 885 lcnbmp_vi = vol->lcnbmp_ino; 886 if (start_vcn < 0 || count < -1) 887 return -EINVAL; 888 889 if (!NVolFreeClusterKnown(vol)) 890 wait_event(vol->free_waitq, NVolFreeClusterKnown(vol)); 891 892 /* 893 * Lock the lcn bitmap for writing but only if not rolling back. We 894 * must hold the lock all the way including through rollback otherwise 895 * rollback is not possible because once we have cleared a bit and 896 * dropped the lock, anyone could have set the bit again, thus 897 * allocating the cluster for another use. 898 */ 899 if (likely(!is_rollback)) { 900 memalloc_flags = memalloc_nofs_save(); 901 down_write(&vol->lcnbmp_lock); 902 } 903 904 total_freed = real_freed = 0; 905 906 rl = ntfs_attr_find_vcn_nolock(ni, start_vcn, ctx); 907 if (IS_ERR(rl)) { 908 err = PTR_ERR(rl); 909 if (err == -ENOENT) { 910 if (likely(!is_rollback)) { 911 up_write(&vol->lcnbmp_lock); 912 memalloc_nofs_restore(memalloc_flags); 913 } 914 return 0; 915 } 916 917 if (!is_rollback) 918 ntfs_error(vol->sb, 919 "Failed to find first runlist element (error %d), aborting.", 920 err); 921 goto err_out; 922 } 923 if (unlikely(rl->lcn < LCN_HOLE)) { 924 if (!is_rollback) 925 ntfs_error(vol->sb, "First runlist element has invalid lcn, aborting."); 926 err = -EIO; 927 goto err_out; 928 } 929 /* Find the starting cluster inside the run that needs freeing. */ 930 delta = start_vcn - rl->vcn; 931 932 /* The number of clusters in this run that need freeing. */ 933 to_free = rl->length - delta; 934 if (count >= 0 && to_free > count) 935 to_free = count; 936 937 if (likely(rl->lcn >= 0)) { 938 /* Do the actual freeing of the clusters in this run. */ 939 err = ntfs_bitmap_set_bits_in_run(lcnbmp_vi, rl->lcn + delta, 940 to_free, likely(!is_rollback) ? 0 : 1); 941 if (unlikely(err)) { 942 if (!is_rollback) 943 ntfs_error(vol->sb, 944 "Failed to clear first run (error %i), aborting.", 945 err); 946 goto err_out; 947 } 948 /* We have freed @to_free real clusters. */ 949 real_freed = to_free; 950 } 951 /* Go to the next run and adjust the number of clusters left to free. */ 952 ++rl; 953 if (count >= 0) 954 count -= to_free; 955 956 /* Keep track of the total "freed" clusters, including sparse ones. */ 957 total_freed = to_free; 958 /* 959 * Loop over the remaining runs, using @count as a capping value, and 960 * free them. 961 */ 962 for (; rl->length && count != 0; ++rl) { 963 if (unlikely(rl->lcn < LCN_HOLE)) { 964 s64 vcn; 965 966 /* Attempt to map runlist. */ 967 vcn = rl->vcn; 968 rl = ntfs_attr_find_vcn_nolock(ni, vcn, ctx); 969 if (IS_ERR(rl)) { 970 err = PTR_ERR(rl); 971 if (!is_rollback) 972 ntfs_error(vol->sb, 973 "Failed to map runlist fragment or failed to find subsequent runlist element."); 974 goto err_out; 975 } 976 if (unlikely(rl->lcn < LCN_HOLE)) { 977 if (!is_rollback) 978 ntfs_error(vol->sb, 979 "Runlist element has invalid lcn (0x%llx).", 980 rl->lcn); 981 err = -EIO; 982 goto err_out; 983 } 984 } 985 /* The number of clusters in this run that need freeing. */ 986 to_free = rl->length; 987 if (count >= 0 && to_free > count) 988 to_free = count; 989 990 if (likely(rl->lcn >= 0)) { 991 /* Do the actual freeing of the clusters in the run. */ 992 err = ntfs_bitmap_set_bits_in_run(lcnbmp_vi, rl->lcn, 993 to_free, likely(!is_rollback) ? 0 : 1); 994 if (unlikely(err)) { 995 if (!is_rollback) 996 ntfs_error(vol->sb, "Failed to clear subsequent run."); 997 goto err_out; 998 } 999 /* We have freed @to_free real clusters. */ 1000 real_freed += to_free; 1001 } 1002 /* Adjust the number of clusters left to free. */ 1003 if (count >= 0) 1004 count -= to_free; 1005 1006 /* Update the total done clusters. */ 1007 total_freed += to_free; 1008 } 1009 ntfs_inc_free_clusters(vol, real_freed); 1010 if (likely(!is_rollback)) { 1011 up_write(&vol->lcnbmp_lock); 1012 memalloc_nofs_restore(memalloc_flags); 1013 } 1014 1015 WARN_ON(count > 0); 1016 1017 if (NVolDiscard(vol) && !is_rollback) { 1018 s64 total_discarded = 0, rl_off; 1019 u32 gran = bdev_discard_granularity(vol->sb->s_bdev); 1020 1021 rl = ntfs_attr_find_vcn_nolock(ni, start_vcn, ctx); 1022 if (IS_ERR(rl)) 1023 return real_freed; 1024 rl_off = start_vcn - rl->vcn; 1025 while (rl->length && total_discarded < total_freed) { 1026 s64 to_discard = rl->length - rl_off; 1027 1028 if (to_discard + total_discarded > total_freed) 1029 to_discard = total_freed - total_discarded; 1030 if (rl->lcn >= 0) { 1031 sector_t start_sector, end_sector; 1032 int ret; 1033 1034 start_sector = ALIGN(NTFS_CLU_TO_B(vol, rl->lcn + rl_off), 1035 gran) >> SECTOR_SHIFT; 1036 end_sector = ALIGN_DOWN(NTFS_CLU_TO_B(vol, 1037 rl->lcn + rl_off + to_discard), 1038 gran) >> SECTOR_SHIFT; 1039 if (start_sector < end_sector) { 1040 ret = blkdev_issue_discard(vol->sb->s_bdev, start_sector, 1041 end_sector - start_sector, 1042 GFP_NOFS); 1043 if (ret) 1044 break; 1045 } 1046 } 1047 1048 total_discarded += to_discard; 1049 ++rl; 1050 rl_off = 0; 1051 } 1052 } 1053 1054 /* We are done. Return the number of actually freed clusters. */ 1055 ntfs_debug("Done."); 1056 return real_freed; 1057 err_out: 1058 if (is_rollback) 1059 return err; 1060 /* If no real clusters were freed, no need to rollback. */ 1061 if (!real_freed) { 1062 up_write(&vol->lcnbmp_lock); 1063 memalloc_nofs_restore(memalloc_flags); 1064 return err; 1065 } 1066 /* 1067 * Attempt to rollback and if that succeeds just return the error code. 1068 * If rollback fails, set the volume errors flag, emit an error 1069 * message, and return the error code. 1070 */ 1071 delta = __ntfs_cluster_free(ni, start_vcn, total_freed, ctx, true); 1072 if (delta < 0) { 1073 ntfs_error(vol->sb, 1074 "Failed to rollback (error %i). Leaving inconsistent metadata! Unmount and run chkdsk.", 1075 (int)delta); 1076 NVolSetErrors(vol); 1077 } else { 1078 ntfs_dec_free_clusters(vol, delta); 1079 } 1080 up_write(&vol->lcnbmp_lock); 1081 memalloc_nofs_restore(memalloc_flags); 1082 ntfs_error(vol->sb, "Aborting (error %i).", err); 1083 return err; 1084 } 1085