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 (unlikely(err && (!ret || ret == -ENOMEM) && ret != err)) 57 ret = err; 58 else 59 nr_freed += rl->length; 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 * Allocate more memory if needed, including space for 380 * the terminator element. 381 * kvzalloc() operates on whole pages only. 382 */ 383 if ((rlpos + 2) * sizeof(*rl) > rlsize) { 384 struct runlist_element *rl2; 385 386 ntfs_debug("Reallocating memory."); 387 if (!rl) 388 ntfs_debug("First free bit is at s64 0x%llx.", 389 lcn + bmp_pos); 390 rl2 = kvzalloc(rlsize + PAGE_SIZE, GFP_NOFS); 391 if (unlikely(!rl2)) { 392 err = -ENOMEM; 393 ntfs_error(vol->sb, "Failed to allocate memory."); 394 goto out; 395 } 396 memcpy(rl2, rl, rlsize); 397 kvfree(rl); 398 rl = rl2; 399 rlsize += PAGE_SIZE; 400 ntfs_debug("Reallocated memory, rlsize 0x%x.", 401 rlsize); 402 } 403 /* Allocate the bitmap bit. */ 404 *byte |= bit; 405 /* We need to write this bitmap page to disk. */ 406 need_writeback = 1; 407 ntfs_debug("*byte 0x%x, need_writeback is set.", 408 (unsigned int)*byte); 409 ntfs_dec_free_clusters(vol, 1); 410 ntfs_set_lcn_empty_bits(vol, index, 1, 1); 411 412 /* 413 * Coalesce with previous run if adjacent LCNs. 414 * Otherwise, append a new run. 415 */ 416 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.", 417 lcn + bmp_pos, 1ULL, prev_lcn, 418 lcn, bmp_pos, prev_run_len, rlpos); 419 if (prev_lcn == lcn + bmp_pos - prev_run_len && rlpos) { 420 ntfs_debug("Coalescing to run (lcn 0x%llx, len 0x%llx).", 421 rl[rlpos - 1].lcn, 422 rl[rlpos - 1].length); 423 rl[rlpos - 1].length = ++prev_run_len; 424 ntfs_debug("Run now (lcn 0x%llx, len 0x%llx), prev_run_len 0x%llx.", 425 rl[rlpos - 1].lcn, 426 rl[rlpos - 1].length, 427 prev_run_len); 428 } else { 429 if (likely(rlpos)) { 430 ntfs_debug("Adding new run, (previous run lcn 0x%llx, len 0x%llx).", 431 rl[rlpos - 1].lcn, rl[rlpos - 1].length); 432 rl[rlpos].vcn = rl[rlpos - 1].vcn + 433 prev_run_len; 434 } else { 435 ntfs_debug("Adding new run, is first run."); 436 rl[rlpos].vcn = start_vcn; 437 } 438 rl[rlpos].lcn = prev_lcn = lcn + bmp_pos; 439 rl[rlpos].length = prev_run_len = 1; 440 rlpos++; 441 } 442 /* Done? */ 443 if (!--clusters) { 444 s64 tc; 445 done: 446 if (!used_zone_pos) 447 goto out; 448 /* 449 * Update the current zone position. Positions 450 * of already scanned zones have been updated 451 * during the respective zone switches. 452 */ 453 tc = lcn + bmp_pos + 1; 454 ntfs_debug("Done. Updating current zone position, tc 0x%llx, search_zone %i.", 455 tc, search_zone); 456 switch (search_zone) { 457 case 1: 458 ntfs_debug("Before checks, vol->mft_zone_pos 0x%llx.", 459 vol->mft_zone_pos); 460 if (tc >= vol->mft_zone_end) { 461 vol->mft_zone_pos = 462 vol->mft_lcn; 463 if (!vol->mft_zone_end) 464 vol->mft_zone_pos = 0; 465 } else if ((bmp_initial_pos >= 466 vol->mft_zone_pos || 467 tc > vol->mft_zone_pos) 468 && tc >= vol->mft_lcn) 469 vol->mft_zone_pos = tc; 470 ntfs_debug("After checks, vol->mft_zone_pos 0x%llx.", 471 vol->mft_zone_pos); 472 break; 473 case 2: 474 ntfs_debug("Before checks, vol->data1_zone_pos 0x%llx.", 475 vol->data1_zone_pos); 476 if (tc >= vol->nr_clusters) 477 vol->data1_zone_pos = 478 vol->mft_zone_end; 479 else if ((bmp_initial_pos >= 480 vol->data1_zone_pos || 481 tc > vol->data1_zone_pos) 482 && tc >= vol->mft_zone_end) 483 vol->data1_zone_pos = tc; 484 ntfs_debug("After checks, vol->data1_zone_pos 0x%llx.", 485 vol->data1_zone_pos); 486 break; 487 case 4: 488 ntfs_debug("Before checks, vol->data2_zone_pos 0x%llx.", 489 vol->data2_zone_pos); 490 if (tc >= vol->mft_zone_start) 491 vol->data2_zone_pos = 0; 492 else if (bmp_initial_pos >= 493 vol->data2_zone_pos || 494 tc > vol->data2_zone_pos) 495 vol->data2_zone_pos = tc; 496 ntfs_debug("After checks, vol->data2_zone_pos 0x%llx.", 497 vol->data2_zone_pos); 498 break; 499 default: 500 WARN_ON(1); 501 } 502 ntfs_debug("Finished. Going to out."); 503 goto out; 504 } 505 lcn++; 506 } 507 508 if (!used_zone_pos) { 509 used_zone_pos = 1; 510 if (search_zone == 1) 511 zone_start = vol->mft_zone_pos; 512 else if (search_zone == 2) 513 zone_start = vol->data1_zone_pos; 514 else 515 zone_start = vol->data2_zone_pos; 516 517 if (!zone_start || zone_start == vol->mft_zone_start || 518 zone_start == vol->mft_zone_end) 519 pass = 2; 520 bmp_pos = zone_start; 521 } else { 522 next_bmp_pos: 523 bmp_pos += buf_size; 524 } 525 526 ntfs_debug("After inner while loop: buf_size 0x%x, lcn 0x%llx, bmp_pos 0x%llx, need_writeback %i.", 527 buf_size, lcn, bmp_pos, need_writeback); 528 if (bmp_pos < zone_end) { 529 ntfs_debug("Continuing outer while loop, bmp_pos 0x%llx, zone_end 0x%llx.", 530 bmp_pos, zone_end); 531 continue; 532 } 533 zone_pass_done: /* Finished with the current zone pass. */ 534 ntfs_debug("At zone_pass_done, pass %i.", pass); 535 if (pass == 1) { 536 /* 537 * Now do pass 2, scanning the first part of the zone 538 * we omitted in pass 1. 539 */ 540 pass = 2; 541 zone_end = zone_start; 542 switch (search_zone) { 543 case 1: /* mft_zone */ 544 zone_start = vol->mft_zone_start; 545 break; 546 case 2: /* data1_zone */ 547 zone_start = vol->mft_zone_end; 548 break; 549 case 4: /* data2_zone */ 550 zone_start = 0; 551 break; 552 default: 553 WARN_ON(1); 554 } 555 /* Sanity check. */ 556 if (zone_end < zone_start) 557 zone_end = zone_start; 558 bmp_pos = zone_start; 559 ntfs_debug("Continuing outer while loop, pass 2, zone_start 0x%llx, zone_end 0x%llx, bmp_pos 0x%llx.", 560 zone_start, zone_end, bmp_pos); 561 continue; 562 } /* pass == 2 */ 563 done_zones_check: 564 ntfs_debug("At done_zones_check, search_zone %i, done_zones before 0x%x, done_zones after 0x%x.", 565 search_zone, done_zones, 566 done_zones | search_zone); 567 done_zones |= search_zone; 568 if (done_zones < 7) { 569 ntfs_debug("Switching zone."); 570 /* Now switch to the next zone we haven't done yet. */ 571 pass = 1; 572 switch (search_zone) { 573 case 1: 574 ntfs_debug("Switching from mft zone to data1 zone."); 575 /* Update mft zone position. */ 576 if (rlpos && used_zone_pos) { 577 s64 tc; 578 579 ntfs_debug("Before checks, vol->mft_zone_pos 0x%llx.", 580 vol->mft_zone_pos); 581 tc = rl[rlpos - 1].lcn + 582 rl[rlpos - 1].length; 583 if (tc >= vol->mft_zone_end) { 584 vol->mft_zone_pos = 585 vol->mft_lcn; 586 if (!vol->mft_zone_end) 587 vol->mft_zone_pos = 0; 588 } else if ((bmp_initial_pos >= 589 vol->mft_zone_pos || 590 tc > vol->mft_zone_pos) 591 && tc >= vol->mft_lcn) 592 vol->mft_zone_pos = tc; 593 ntfs_debug("After checks, vol->mft_zone_pos 0x%llx.", 594 vol->mft_zone_pos); 595 } 596 /* Switch from mft zone to data1 zone. */ 597 switch_to_data1_zone: search_zone = 2; 598 zone_start = bmp_initial_pos = 599 vol->data1_zone_pos; 600 zone_end = vol->nr_clusters; 601 if (zone_start == vol->mft_zone_end) 602 pass = 2; 603 if (zone_start >= zone_end) { 604 vol->data1_zone_pos = zone_start = 605 vol->mft_zone_end; 606 pass = 2; 607 } 608 break; 609 case 2: 610 ntfs_debug("Switching from data1 zone to data2 zone."); 611 /* Update data1 zone position. */ 612 if (rlpos && used_zone_pos) { 613 s64 tc; 614 615 ntfs_debug("Before checks, vol->data1_zone_pos 0x%llx.", 616 vol->data1_zone_pos); 617 tc = rl[rlpos - 1].lcn + 618 rl[rlpos - 1].length; 619 if (tc >= vol->nr_clusters) 620 vol->data1_zone_pos = 621 vol->mft_zone_end; 622 else if ((bmp_initial_pos >= 623 vol->data1_zone_pos || 624 tc > vol->data1_zone_pos) 625 && tc >= vol->mft_zone_end) 626 vol->data1_zone_pos = tc; 627 ntfs_debug("After checks, vol->data1_zone_pos 0x%llx.", 628 vol->data1_zone_pos); 629 } 630 /* Switch from data1 zone to data2 zone. */ 631 search_zone = 4; 632 zone_start = bmp_initial_pos = 633 vol->data2_zone_pos; 634 zone_end = vol->mft_zone_start; 635 if (!zone_start) 636 pass = 2; 637 if (zone_start >= zone_end) { 638 vol->data2_zone_pos = zone_start = 639 bmp_initial_pos = 0; 640 pass = 2; 641 } 642 break; 643 case 4: 644 ntfs_debug("Switching from data2 zone to data1 zone."); 645 /* Update data2 zone position. */ 646 if (rlpos && used_zone_pos) { 647 s64 tc; 648 649 ntfs_debug("Before checks, vol->data2_zone_pos 0x%llx.", 650 vol->data2_zone_pos); 651 tc = rl[rlpos - 1].lcn + 652 rl[rlpos - 1].length; 653 if (tc >= vol->mft_zone_start) 654 vol->data2_zone_pos = 0; 655 else if (bmp_initial_pos >= 656 vol->data2_zone_pos || 657 tc > vol->data2_zone_pos) 658 vol->data2_zone_pos = tc; 659 ntfs_debug("After checks, vol->data2_zone_pos 0x%llx.", 660 vol->data2_zone_pos); 661 } 662 /* Switch from data2 zone to data1 zone. */ 663 goto switch_to_data1_zone; 664 default: 665 WARN_ON(1); 666 } 667 ntfs_debug("After zone switch, search_zone %i, pass %i, bmp_initial_pos 0x%llx, zone_start 0x%llx, zone_end 0x%llx.", 668 search_zone, pass, 669 bmp_initial_pos, 670 zone_start, 671 zone_end); 672 bmp_pos = zone_start; 673 if (zone_start == zone_end) { 674 ntfs_debug("Empty zone, going to done_zones_check."); 675 /* Empty zone. Don't bother searching it. */ 676 goto done_zones_check; 677 } 678 ntfs_debug("Continuing outer while loop."); 679 continue; 680 } /* done_zones == 7 */ 681 ntfs_debug("All zones are finished."); 682 /* 683 * All zones are finished! If DATA_ZONE, shrink mft zone. If 684 * MFT_ZONE, we have really run out of space. 685 */ 686 mft_zone_size = vol->mft_zone_end - vol->mft_zone_start; 687 ntfs_debug("vol->mft_zone_start 0x%llx, vol->mft_zone_end 0x%llx, mft_zone_size 0x%llx.", 688 vol->mft_zone_start, vol->mft_zone_end, 689 mft_zone_size); 690 if (zone == MFT_ZONE || mft_zone_size <= 0) { 691 ntfs_debug("No free clusters left, going to out."); 692 /* Really no more space left on device. */ 693 err = -ENOSPC; 694 goto out; 695 } /* zone == DATA_ZONE && mft_zone_size > 0 */ 696 ntfs_debug("Shrinking mft zone."); 697 zone_end = vol->mft_zone_end; 698 mft_zone_size >>= 1; 699 if (mft_zone_size > 0) 700 vol->mft_zone_end = vol->mft_zone_start + mft_zone_size; 701 else /* mft zone and data2 zone no longer exist. */ 702 vol->data2_zone_pos = vol->mft_zone_start = 703 vol->mft_zone_end = 0; 704 if (vol->mft_zone_pos >= vol->mft_zone_end) { 705 vol->mft_zone_pos = vol->mft_lcn; 706 if (!vol->mft_zone_end) 707 vol->mft_zone_pos = 0; 708 } 709 bmp_pos = zone_start = bmp_initial_pos = 710 vol->data1_zone_pos = vol->mft_zone_end; 711 search_zone = 2; 712 pass = 2; 713 done_zones &= ~2; 714 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.", 715 mft_zone_size, vol->mft_zone_start, 716 vol->mft_zone_end, vol->mft_zone_pos, 717 done_zones, zone_start, zone_end, 718 vol->data1_zone_pos); 719 } 720 ntfs_debug("After outer while loop."); 721 out: 722 ntfs_debug("At out."); 723 /* Add runlist terminator element. */ 724 if (likely(rl)) { 725 rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length; 726 rl[rlpos].lcn = is_extension ? LCN_ENOENT : LCN_RL_NOT_MAPPED; 727 rl[rlpos].length = 0; 728 } 729 if (!IS_ERR_OR_NULL(folio)) { 730 if (need_writeback) { 731 ntfs_debug("Marking page dirty."); 732 folio_mark_dirty(folio); 733 need_writeback = 0; 734 } 735 folio_unlock(folio); 736 kunmap_local(buf); 737 folio_put(folio); 738 } 739 if (likely(!err)) { 740 if (!rl) { 741 err = -EIO; 742 goto out_restore; 743 } 744 if (is_dealloc == true) 745 ntfs_release_dirty_clusters(vol, rl->length); 746 ntfs_debug("Done."); 747 goto out_restore; 748 } 749 if (err != -ENOSPC) 750 ntfs_error(vol->sb, 751 "Failed to allocate clusters, aborting (error %i).", 752 err); 753 if (rl) { 754 int err2; 755 756 if (err == -ENOSPC) 757 ntfs_debug("Not enough space to complete allocation, err -ENOSPC, first free lcn 0x%llx, could allocate up to 0x%llx clusters.", 758 rl[0].lcn, count - clusters); 759 /* Deallocate all allocated clusters. */ 760 ntfs_debug("Attempting rollback..."); 761 err2 = ntfs_cluster_free_from_rl_nolock(vol, rl); 762 if (err2) { 763 ntfs_error(vol->sb, 764 "Failed to rollback (error %i). Leaving inconsistent metadata! Unmount and run chkdsk.", 765 err2); 766 NVolSetErrors(vol); 767 } 768 /* Free the runlist. */ 769 kvfree(rl); 770 } else if (err == -ENOSPC) 771 ntfs_debug("No space left at all, err = -ENOSPC, first free lcn = 0x%llx.", 772 vol->data1_zone_pos); 773 atomic64_set(&vol->dirty_clusters, 0); 774 775 out_restore: 776 up_write(&vol->lcnbmp_lock); 777 memalloc_nofs_restore(memalloc_flags); 778 779 return err < 0 ? ERR_PTR(err) : rl; 780 } 781 782 /* 783 * __ntfs_cluster_free - free clusters on an ntfs volume 784 * @ni: ntfs inode whose runlist describes the clusters to free 785 * @start_vcn: vcn in the runlist of @ni at which to start freeing clusters 786 * @count: number of clusters to free or -1 for all clusters 787 * @ctx: active attribute search context if present or NULL if not 788 * @is_rollback: true if this is a rollback operation 789 * 790 * Free @count clusters starting at the cluster @start_vcn in the runlist 791 * described by the vfs inode @ni. 792 * 793 * If @count is -1, all clusters from @start_vcn to the end of the runlist are 794 * deallocated. Thus, to completely free all clusters in a runlist, use 795 * @start_vcn = 0 and @count = -1. 796 * 797 * If @ctx is specified, it is an active search context of @ni and its base mft 798 * record. This is needed when __ntfs_cluster_free() encounters unmapped 799 * runlist fragments and allows their mapping. If you do not have the mft 800 * record mapped, you can specify @ctx as NULL and __ntfs_cluster_free() will 801 * perform the necessary mapping and unmapping. 802 * 803 * Note, __ntfs_cluster_free() saves the state of @ctx on entry and restores it 804 * before returning. Thus, @ctx will be left pointing to the same attribute on 805 * return as on entry. However, the actual pointers in @ctx may point to 806 * different memory locations on return, so you must remember to reset any 807 * cached pointers from the @ctx, i.e. after the call to __ntfs_cluster_free(), 808 * you will probably want to do: 809 * m = ctx->mrec; 810 * a = ctx->attr; 811 * Assuming you cache ctx->attr in a variable @a of type attr_record * and that 812 * you cache ctx->mrec in a variable @m of type struct mft_record *. 813 * 814 * @is_rollback should always be 'false', it is for internal use to rollback 815 * errors. You probably want to use ntfs_cluster_free() instead. 816 * 817 * Note, __ntfs_cluster_free() does not modify the runlist, so you have to 818 * remove from the runlist or mark sparse the freed runs later. 819 * 820 * Return the number of deallocated clusters (not counting sparse ones) on 821 * success and -errno on error. 822 * 823 * WARNING: If @ctx is supplied, regardless of whether success or failure is 824 * returned, you need to check IS_ERR(@ctx->mrec) and if 'true' the @ctx 825 * is no longer valid, i.e. you need to either call 826 * ntfs_attr_reinit_search_ctx() or ntfs_attr_put_search_ctx() on it. 827 * In that case PTR_ERR(@ctx->mrec) will give you the error code for 828 * why the mapping of the old inode failed. 829 * 830 * Locking: - The runlist described by @ni must be locked for writing on entry 831 * and is locked on return. Note the runlist may be modified when 832 * needed runlist fragments need to be mapped. 833 * - The volume lcn bitmap must be unlocked on entry and is unlocked 834 * on return. 835 * - This function takes the volume lcn bitmap lock for writing and 836 * modifies the bitmap contents. 837 * - If @ctx is NULL, the base mft record of @ni must not be mapped on 838 * entry and it will be left unmapped on return. 839 * - If @ctx is not NULL, the base mft record must be mapped on entry 840 * and it will be left mapped on return. 841 */ 842 s64 __ntfs_cluster_free(struct ntfs_inode *ni, const s64 start_vcn, s64 count, 843 struct ntfs_attr_search_ctx *ctx, const bool is_rollback) 844 { 845 s64 delta, to_free, total_freed, real_freed; 846 struct ntfs_volume *vol; 847 struct inode *lcnbmp_vi; 848 struct runlist_element *rl; 849 int err; 850 unsigned int memalloc_flags; 851 852 ntfs_debug("Entering for i_ino 0x%llx, start_vcn 0x%llx, count 0x%llx.%s", 853 ni->mft_no, start_vcn, count, 854 is_rollback ? " (rollback)" : ""); 855 vol = ni->vol; 856 lcnbmp_vi = vol->lcnbmp_ino; 857 if (start_vcn < 0 || count < -1) 858 return -EINVAL; 859 860 if (!NVolFreeClusterKnown(vol)) 861 wait_event(vol->free_waitq, NVolFreeClusterKnown(vol)); 862 863 /* 864 * Lock the lcn bitmap for writing but only if not rolling back. We 865 * must hold the lock all the way including through rollback otherwise 866 * rollback is not possible because once we have cleared a bit and 867 * dropped the lock, anyone could have set the bit again, thus 868 * allocating the cluster for another use. 869 */ 870 if (likely(!is_rollback)) { 871 memalloc_flags = memalloc_nofs_save(); 872 down_write(&vol->lcnbmp_lock); 873 } 874 875 total_freed = real_freed = 0; 876 877 rl = ntfs_attr_find_vcn_nolock(ni, start_vcn, ctx); 878 if (IS_ERR(rl)) { 879 err = PTR_ERR(rl); 880 if (err == -ENOENT) { 881 if (likely(!is_rollback)) { 882 up_write(&vol->lcnbmp_lock); 883 memalloc_nofs_restore(memalloc_flags); 884 } 885 return 0; 886 } 887 888 if (!is_rollback) 889 ntfs_error(vol->sb, 890 "Failed to find first runlist element (error %d), aborting.", 891 err); 892 goto err_out; 893 } 894 if (unlikely(rl->lcn < LCN_HOLE)) { 895 if (!is_rollback) 896 ntfs_error(vol->sb, "First runlist element has invalid lcn, aborting."); 897 err = -EIO; 898 goto err_out; 899 } 900 /* Find the starting cluster inside the run that needs freeing. */ 901 delta = start_vcn - rl->vcn; 902 903 /* The number of clusters in this run that need freeing. */ 904 to_free = rl->length - delta; 905 if (count >= 0 && to_free > count) 906 to_free = count; 907 908 if (likely(rl->lcn >= 0)) { 909 /* Do the actual freeing of the clusters in this run. */ 910 err = ntfs_bitmap_set_bits_in_run(lcnbmp_vi, rl->lcn + delta, 911 to_free, likely(!is_rollback) ? 0 : 1); 912 if (unlikely(err)) { 913 if (!is_rollback) 914 ntfs_error(vol->sb, 915 "Failed to clear first run (error %i), aborting.", 916 err); 917 goto err_out; 918 } 919 /* We have freed @to_free real clusters. */ 920 real_freed = to_free; 921 } 922 /* Go to the next run and adjust the number of clusters left to free. */ 923 ++rl; 924 if (count >= 0) 925 count -= to_free; 926 927 /* Keep track of the total "freed" clusters, including sparse ones. */ 928 total_freed = to_free; 929 /* 930 * Loop over the remaining runs, using @count as a capping value, and 931 * free them. 932 */ 933 for (; rl->length && count != 0; ++rl) { 934 if (unlikely(rl->lcn < LCN_HOLE)) { 935 s64 vcn; 936 937 /* Attempt to map runlist. */ 938 vcn = rl->vcn; 939 rl = ntfs_attr_find_vcn_nolock(ni, vcn, ctx); 940 if (IS_ERR(rl)) { 941 err = PTR_ERR(rl); 942 if (!is_rollback) 943 ntfs_error(vol->sb, 944 "Failed to map runlist fragment or failed to find subsequent runlist element."); 945 goto err_out; 946 } 947 if (unlikely(rl->lcn < LCN_HOLE)) { 948 if (!is_rollback) 949 ntfs_error(vol->sb, 950 "Runlist element has invalid lcn (0x%llx).", 951 rl->lcn); 952 err = -EIO; 953 goto err_out; 954 } 955 } 956 /* The number of clusters in this run that need freeing. */ 957 to_free = rl->length; 958 if (count >= 0 && to_free > count) 959 to_free = count; 960 961 if (likely(rl->lcn >= 0)) { 962 /* Do the actual freeing of the clusters in the run. */ 963 err = ntfs_bitmap_set_bits_in_run(lcnbmp_vi, rl->lcn, 964 to_free, likely(!is_rollback) ? 0 : 1); 965 if (unlikely(err)) { 966 if (!is_rollback) 967 ntfs_error(vol->sb, "Failed to clear subsequent run."); 968 goto err_out; 969 } 970 /* We have freed @to_free real clusters. */ 971 real_freed += to_free; 972 } 973 /* Adjust the number of clusters left to free. */ 974 if (count >= 0) 975 count -= to_free; 976 977 /* Update the total done clusters. */ 978 total_freed += to_free; 979 } 980 ntfs_inc_free_clusters(vol, real_freed); 981 if (likely(!is_rollback)) { 982 up_write(&vol->lcnbmp_lock); 983 memalloc_nofs_restore(memalloc_flags); 984 } 985 986 WARN_ON(count > 0); 987 988 if (NVolDiscard(vol) && !is_rollback) { 989 s64 total_discarded = 0, rl_off; 990 u32 gran = bdev_discard_granularity(vol->sb->s_bdev); 991 992 rl = ntfs_attr_find_vcn_nolock(ni, start_vcn, ctx); 993 if (IS_ERR(rl)) 994 return real_freed; 995 rl_off = start_vcn - rl->vcn; 996 while (rl->length && total_discarded < total_freed) { 997 s64 to_discard = rl->length - rl_off; 998 999 if (to_discard + total_discarded > total_freed) 1000 to_discard = total_freed - total_discarded; 1001 if (rl->lcn >= 0) { 1002 sector_t start_sector, end_sector; 1003 int ret; 1004 1005 start_sector = ALIGN(NTFS_CLU_TO_B(vol, rl->lcn + rl_off), 1006 gran) >> SECTOR_SHIFT; 1007 end_sector = ALIGN_DOWN(NTFS_CLU_TO_B(vol, 1008 rl->lcn + rl_off + to_discard), 1009 gran) >> SECTOR_SHIFT; 1010 if (start_sector < end_sector) { 1011 ret = blkdev_issue_discard(vol->sb->s_bdev, start_sector, 1012 end_sector - start_sector, 1013 GFP_NOFS); 1014 if (ret) 1015 break; 1016 } 1017 } 1018 1019 total_discarded += to_discard; 1020 ++rl; 1021 rl_off = 0; 1022 } 1023 } 1024 1025 /* We are done. Return the number of actually freed clusters. */ 1026 ntfs_debug("Done."); 1027 return real_freed; 1028 err_out: 1029 if (is_rollback) 1030 return err; 1031 /* If no real clusters were freed, no need to rollback. */ 1032 if (!real_freed) { 1033 up_write(&vol->lcnbmp_lock); 1034 memalloc_nofs_restore(memalloc_flags); 1035 return err; 1036 } 1037 /* 1038 * Attempt to rollback and if that succeeds just return the error code. 1039 * If rollback fails, set the volume errors flag, emit an error 1040 * message, and return the error code. 1041 */ 1042 delta = __ntfs_cluster_free(ni, start_vcn, total_freed, ctx, true); 1043 if (delta < 0) { 1044 ntfs_error(vol->sb, 1045 "Failed to rollback (error %i). Leaving inconsistent metadata! Unmount and run chkdsk.", 1046 (int)delta); 1047 NVolSetErrors(vol); 1048 } 1049 ntfs_dec_free_clusters(vol, delta); 1050 up_write(&vol->lcnbmp_lock); 1051 memalloc_nofs_restore(memalloc_flags); 1052 ntfs_error(vol->sb, "Aborting (error %i).", err); 1053 return err; 1054 } 1055