Lines Matching +full:pass +full:- +full:1
1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * lcnalloc.c - Cluster (de)allocation code. Part of the Linux-NTFS project.
5 * Copyright (c) 2004-2005 Anton Altaparmakov
23 * ntfs_cluster_free_from_rl_nolock - free clusters from runlist
31 * Return 0 on success and -errno on error.
33 * Locking: - The volume lcn bitmap must be locked for writing on entry and is
39 struct inode *lcnbmp_vi = vol->lcnbmp_ino; in ntfs_cluster_free_from_rl_nolock()
45 for (; rl->length; rl++) { in ntfs_cluster_free_from_rl_nolock()
48 if (rl->lcn < 0) in ntfs_cluster_free_from_rl_nolock()
50 err = ntfs_bitmap_clear_run(lcnbmp_vi, rl->lcn, rl->length); in ntfs_cluster_free_from_rl_nolock()
51 if (unlikely(err && (!ret || ret == -ENOMEM) && ret != err)) in ntfs_cluster_free_from_rl_nolock()
59 * ntfs_cluster_alloc - allocate clusters on an ntfs volume
63 * @start_lcn: starting lcn at which to allocate the clusters (or -1 if none)
68 * current allocator position if @start_lcn is -1, on the mounted ntfs volume
93 * volume and the start of the mft zone. On unmodified/standard NTFS 1.x
106 * worthwhile, because this allocator should: 1) be a full implementation of
124 * possible code paths. So at least for now, I am leaving the double logic -
127 * Locking: - The volume lcn bitmap must be unlocked on entry and is unlocked
129 * - This function takes the volume lcn bitmap lock for writing and
147 u8 pass, done_zones, search_zone, need_writeback = 0, bit; in ntfs_cluster_alloc() local
155 lcnbmp_vi = vol->lcnbmp_ino; in ntfs_cluster_alloc()
159 BUG_ON(start_lcn < -1); in ntfs_cluster_alloc()
167 down_write(&vol->lcnbmp_lock); in ntfs_cluster_alloc()
172 * and pass depending on whether we are starting inside a zone (1) or in ntfs_cluster_alloc()
179 pass = 1; in ntfs_cluster_alloc()
182 * is 1 for mft zone, 2 for data zone 1 (end of mft zone till end of in ntfs_cluster_alloc()
189 zone_start = vol->data1_zone_pos; in ntfs_cluster_alloc()
191 zone_start = vol->mft_zone_pos; in ntfs_cluster_alloc()
195 * single pass is sufficient. in ntfs_cluster_alloc()
197 pass = 2; in ntfs_cluster_alloc()
199 } else if (zone == DATA_ZONE && zone_start >= vol->mft_zone_start && in ntfs_cluster_alloc()
200 zone_start < vol->mft_zone_end) { in ntfs_cluster_alloc()
201 zone_start = vol->mft_zone_end; in ntfs_cluster_alloc()
204 * pass in this zone is sufficient. in ntfs_cluster_alloc()
206 pass = 2; in ntfs_cluster_alloc()
207 } else if (zone == MFT_ZONE && (zone_start < vol->mft_zone_start || in ntfs_cluster_alloc()
208 zone_start >= vol->mft_zone_end)) { in ntfs_cluster_alloc()
209 zone_start = vol->mft_lcn; in ntfs_cluster_alloc()
210 if (!vol->mft_zone_end) in ntfs_cluster_alloc()
213 * Starting at beginning of volume which means a single pass in ntfs_cluster_alloc()
216 pass = 2; in ntfs_cluster_alloc()
219 zone_end = vol->mft_zone_end; in ntfs_cluster_alloc()
220 search_zone = 1; in ntfs_cluster_alloc()
223 done_zones |= 1; in ntfs_cluster_alloc()
224 if (zone_start >= vol->mft_zone_end) { in ntfs_cluster_alloc()
225 zone_end = vol->nr_clusters; in ntfs_cluster_alloc()
228 zone_end = vol->mft_zone_start; in ntfs_cluster_alloc()
241 mapping = lcnbmp_vi->i_mapping; in ntfs_cluster_alloc()
243 while (1) { in ntfs_cluster_alloc()
245 "search_zone %i, pass %i, zone_start 0x%llx, " in ntfs_cluster_alloc()
248 done_zones, search_zone, pass, in ntfs_cluster_alloc()
275 ntfs_error(vol->sb, "Failed to map page."); in ntfs_cluster_alloc()
280 buf_size = PAGE_SIZE - buf_size; in ntfs_cluster_alloc()
282 buf_size = i_size - last_read_pos; in ntfs_cluster_alloc()
304 ntfs_debug("Continuing while loop 1."); in ntfs_cluster_alloc()
307 bit = 1 << (lcn & 7); in ntfs_cluster_alloc()
331 err = -ENOMEM; in ntfs_cluster_alloc()
332 ntfs_error(vol->sb, "Failed to " in ntfs_cluster_alloc()
346 need_writeback = 1; in ntfs_cluster_alloc()
358 1ULL, (unsigned long long)prev_lcn, in ntfs_cluster_alloc()
363 if (prev_lcn == lcn + bmp_pos - prev_run_len && rlpos) { in ntfs_cluster_alloc()
367 rl[rlpos - 1].lcn, in ntfs_cluster_alloc()
369 rl[rlpos - 1].length); in ntfs_cluster_alloc()
370 rl[rlpos - 1].length = ++prev_run_len; in ntfs_cluster_alloc()
374 rl[rlpos - 1].lcn, in ntfs_cluster_alloc()
376 rl[rlpos - 1].length, in ntfs_cluster_alloc()
385 rl[rlpos - 1].lcn, in ntfs_cluster_alloc()
387 rl[rlpos - 1].length); in ntfs_cluster_alloc()
388 rl[rlpos].vcn = rl[rlpos - 1].vcn + in ntfs_cluster_alloc()
396 rl[rlpos].length = prev_run_len = 1; in ntfs_cluster_alloc()
400 if (!--clusters) { in ntfs_cluster_alloc()
407 tc = lcn + bmp_pos + 1; in ntfs_cluster_alloc()
414 case 1: in ntfs_cluster_alloc()
416 "vol->mft_zone_pos " in ntfs_cluster_alloc()
419 vol->mft_zone_pos); in ntfs_cluster_alloc()
420 if (tc >= vol->mft_zone_end) { in ntfs_cluster_alloc()
421 vol->mft_zone_pos = in ntfs_cluster_alloc()
422 vol->mft_lcn; in ntfs_cluster_alloc()
423 if (!vol->mft_zone_end) in ntfs_cluster_alloc()
424 vol->mft_zone_pos = 0; in ntfs_cluster_alloc()
426 vol->mft_zone_pos || in ntfs_cluster_alloc()
427 tc > vol->mft_zone_pos) in ntfs_cluster_alloc()
428 && tc >= vol->mft_lcn) in ntfs_cluster_alloc()
429 vol->mft_zone_pos = tc; in ntfs_cluster_alloc()
431 "vol->mft_zone_pos " in ntfs_cluster_alloc()
434 vol->mft_zone_pos); in ntfs_cluster_alloc()
438 "vol->data1_zone_pos " in ntfs_cluster_alloc()
441 vol->data1_zone_pos); in ntfs_cluster_alloc()
442 if (tc >= vol->nr_clusters) in ntfs_cluster_alloc()
443 vol->data1_zone_pos = in ntfs_cluster_alloc()
444 vol->mft_zone_end; in ntfs_cluster_alloc()
446 vol->data1_zone_pos || in ntfs_cluster_alloc()
447 tc > vol->data1_zone_pos) in ntfs_cluster_alloc()
448 && tc >= vol->mft_zone_end) in ntfs_cluster_alloc()
449 vol->data1_zone_pos = tc; in ntfs_cluster_alloc()
451 "vol->data1_zone_pos " in ntfs_cluster_alloc()
454 vol->data1_zone_pos); in ntfs_cluster_alloc()
458 "vol->data2_zone_pos " in ntfs_cluster_alloc()
461 vol->data2_zone_pos); in ntfs_cluster_alloc()
462 if (tc >= vol->mft_zone_start) in ntfs_cluster_alloc()
463 vol->data2_zone_pos = 0; in ntfs_cluster_alloc()
465 vol->data2_zone_pos || in ntfs_cluster_alloc()
466 tc > vol->data2_zone_pos) in ntfs_cluster_alloc()
467 vol->data2_zone_pos = tc; in ntfs_cluster_alloc()
469 "vol->data2_zone_pos " in ntfs_cluster_alloc()
472 vol->data2_zone_pos); in ntfs_cluster_alloc()
494 zone_pass_done: /* Finished with the current zone pass. */ in ntfs_cluster_alloc()
495 ntfs_debug("At zone_pass_done, pass %i.", pass); in ntfs_cluster_alloc()
496 if (pass == 1) { in ntfs_cluster_alloc()
498 * Now do pass 2, scanning the first part of the zone in ntfs_cluster_alloc()
499 * we omitted in pass 1. in ntfs_cluster_alloc()
501 pass = 2; in ntfs_cluster_alloc()
504 case 1: /* mft_zone */ in ntfs_cluster_alloc()
505 zone_start = vol->mft_zone_start; in ntfs_cluster_alloc()
508 zone_start = vol->mft_zone_end; in ntfs_cluster_alloc()
520 ntfs_debug("Continuing outer while loop, pass 2, " in ntfs_cluster_alloc()
527 } /* pass == 2 */ in ntfs_cluster_alloc()
537 pass = 1; in ntfs_cluster_alloc()
539 case 1: in ntfs_cluster_alloc()
547 "vol->mft_zone_pos " in ntfs_cluster_alloc()
550 vol->mft_zone_pos); in ntfs_cluster_alloc()
551 tc = rl[rlpos - 1].lcn + in ntfs_cluster_alloc()
552 rl[rlpos - 1].length; in ntfs_cluster_alloc()
553 if (tc >= vol->mft_zone_end) { in ntfs_cluster_alloc()
554 vol->mft_zone_pos = in ntfs_cluster_alloc()
555 vol->mft_lcn; in ntfs_cluster_alloc()
556 if (!vol->mft_zone_end) in ntfs_cluster_alloc()
557 vol->mft_zone_pos = 0; in ntfs_cluster_alloc()
559 vol->mft_zone_pos || in ntfs_cluster_alloc()
560 tc > vol->mft_zone_pos) in ntfs_cluster_alloc()
561 && tc >= vol->mft_lcn) in ntfs_cluster_alloc()
562 vol->mft_zone_pos = tc; in ntfs_cluster_alloc()
564 "vol->mft_zone_pos " in ntfs_cluster_alloc()
567 vol->mft_zone_pos); in ntfs_cluster_alloc()
572 vol->data1_zone_pos; in ntfs_cluster_alloc()
573 zone_end = vol->nr_clusters; in ntfs_cluster_alloc()
574 if (zone_start == vol->mft_zone_end) in ntfs_cluster_alloc()
575 pass = 2; in ntfs_cluster_alloc()
577 vol->data1_zone_pos = zone_start = in ntfs_cluster_alloc()
578 vol->mft_zone_end; in ntfs_cluster_alloc()
579 pass = 2; in ntfs_cluster_alloc()
590 "vol->data1_zone_pos " in ntfs_cluster_alloc()
593 vol->data1_zone_pos); in ntfs_cluster_alloc()
594 tc = rl[rlpos - 1].lcn + in ntfs_cluster_alloc()
595 rl[rlpos - 1].length; in ntfs_cluster_alloc()
596 if (tc >= vol->nr_clusters) in ntfs_cluster_alloc()
597 vol->data1_zone_pos = in ntfs_cluster_alloc()
598 vol->mft_zone_end; in ntfs_cluster_alloc()
600 vol->data1_zone_pos || in ntfs_cluster_alloc()
601 tc > vol->data1_zone_pos) in ntfs_cluster_alloc()
602 && tc >= vol->mft_zone_end) in ntfs_cluster_alloc()
603 vol->data1_zone_pos = tc; in ntfs_cluster_alloc()
605 "vol->data1_zone_pos " in ntfs_cluster_alloc()
608 vol->data1_zone_pos); in ntfs_cluster_alloc()
613 vol->data2_zone_pos; in ntfs_cluster_alloc()
614 zone_end = vol->mft_zone_start; in ntfs_cluster_alloc()
616 pass = 2; in ntfs_cluster_alloc()
618 vol->data2_zone_pos = zone_start = in ntfs_cluster_alloc()
620 pass = 2; in ntfs_cluster_alloc()
631 "vol->data2_zone_pos " in ntfs_cluster_alloc()
634 vol->data2_zone_pos); in ntfs_cluster_alloc()
635 tc = rl[rlpos - 1].lcn + in ntfs_cluster_alloc()
636 rl[rlpos - 1].length; in ntfs_cluster_alloc()
637 if (tc >= vol->mft_zone_start) in ntfs_cluster_alloc()
638 vol->data2_zone_pos = 0; in ntfs_cluster_alloc()
640 vol->data2_zone_pos || in ntfs_cluster_alloc()
641 tc > vol->data2_zone_pos) in ntfs_cluster_alloc()
642 vol->data2_zone_pos = tc; in ntfs_cluster_alloc()
644 "vol->data2_zone_pos " in ntfs_cluster_alloc()
647 vol->data2_zone_pos); in ntfs_cluster_alloc()
655 "pass %i, bmp_initial_pos 0x%llx, " in ntfs_cluster_alloc()
657 search_zone, pass, in ntfs_cluster_alloc()
676 mft_zone_size = vol->mft_zone_end - vol->mft_zone_start; in ntfs_cluster_alloc()
677 ntfs_debug("vol->mft_zone_start 0x%llx, vol->mft_zone_end " in ntfs_cluster_alloc()
679 (unsigned long long)vol->mft_zone_start, in ntfs_cluster_alloc()
680 (unsigned long long)vol->mft_zone_end, in ntfs_cluster_alloc()
685 err = -ENOSPC; in ntfs_cluster_alloc()
689 zone_end = vol->mft_zone_end; in ntfs_cluster_alloc()
690 mft_zone_size >>= 1; in ntfs_cluster_alloc()
692 vol->mft_zone_end = vol->mft_zone_start + mft_zone_size; in ntfs_cluster_alloc()
694 vol->data2_zone_pos = vol->mft_zone_start = in ntfs_cluster_alloc()
695 vol->mft_zone_end = 0; in ntfs_cluster_alloc()
696 if (vol->mft_zone_pos >= vol->mft_zone_end) { in ntfs_cluster_alloc()
697 vol->mft_zone_pos = vol->mft_lcn; in ntfs_cluster_alloc()
698 if (!vol->mft_zone_end) in ntfs_cluster_alloc()
699 vol->mft_zone_pos = 0; in ntfs_cluster_alloc()
702 vol->data1_zone_pos = vol->mft_zone_end; in ntfs_cluster_alloc()
704 pass = 2; in ntfs_cluster_alloc()
707 "vol->mft_zone_start 0x%llx, " in ntfs_cluster_alloc()
708 "vol->mft_zone_end 0x%llx, " in ntfs_cluster_alloc()
709 "vol->mft_zone_pos 0x%llx, search_zone 2, " in ntfs_cluster_alloc()
710 "pass 2, dones_zones 0x%x, zone_start 0x%llx, " in ntfs_cluster_alloc()
711 "zone_end 0x%llx, vol->data1_zone_pos 0x%llx, " in ntfs_cluster_alloc()
714 (unsigned long long)vol->mft_zone_start, in ntfs_cluster_alloc()
715 (unsigned long long)vol->mft_zone_end, in ntfs_cluster_alloc()
716 (unsigned long long)vol->mft_zone_pos, in ntfs_cluster_alloc()
719 (unsigned long long)vol->data1_zone_pos); in ntfs_cluster_alloc()
726 rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length; in ntfs_cluster_alloc()
740 up_write(&vol->lcnbmp_lock); in ntfs_cluster_alloc()
744 ntfs_error(vol->sb, "Failed to allocate clusters, aborting " in ntfs_cluster_alloc()
749 if (err == -ENOSPC) in ntfs_cluster_alloc()
751 "err -ENOSPC, first free lcn 0x%llx, " in ntfs_cluster_alloc()
755 (unsigned long long)(count - clusters)); in ntfs_cluster_alloc()
760 ntfs_error(vol->sb, "Failed to rollback (error %i). " in ntfs_cluster_alloc()
767 } else if (err == -ENOSPC) in ntfs_cluster_alloc()
768 ntfs_debug("No space left at all, err = -ENOSPC, first free " in ntfs_cluster_alloc()
770 (long long)vol->data1_zone_pos); in ntfs_cluster_alloc()
771 up_write(&vol->lcnbmp_lock); in ntfs_cluster_alloc()
776 * __ntfs_cluster_free - free clusters on an ntfs volume
779 * @count: number of clusters to free or -1 for all clusters
786 * If @count is -1, all clusters from @start_vcn to the end of the runlist are
788 * @start_vcn = 0 and @count = -1.
802 * m = ctx->mrec;
803 * a = ctx->attr;
804 * Assuming you cache ctx->attr in a variable @a of type ATTR_RECORD * and that
805 * you cache ctx->mrec in a variable @m of type MFT_RECORD *.
814 * success and -errno on error.
817 * returned, you need to check IS_ERR(@ctx->mrec) and if 'true' the @ctx
820 * In that case PTR_ERR(@ctx->mrec) will give you the error code for
823 * Locking: - The runlist described by @ni must be locked for writing on entry
826 * - The volume lcn bitmap must be unlocked on entry and is unlocked
828 * - This function takes the volume lcn bitmap lock for writing and
830 * - If @ctx is NULL, the base mft record of @ni must not be mapped on
832 * - If @ctx is not NULL, the base mft record must be mapped on entry
846 "0x%llx.%s", ni->mft_no, (unsigned long long)start_vcn, in __ntfs_cluster_free()
849 vol = ni->vol; in __ntfs_cluster_free()
850 lcnbmp_vi = vol->lcnbmp_ino; in __ntfs_cluster_free()
853 BUG_ON(count < -1); in __ntfs_cluster_free()
862 down_write(&vol->lcnbmp_lock); in __ntfs_cluster_free()
869 ntfs_error(vol->sb, "Failed to find first runlist " in __ntfs_cluster_free()
875 if (unlikely(rl->lcn < LCN_HOLE)) { in __ntfs_cluster_free()
877 ntfs_error(vol->sb, "First runlist element has " in __ntfs_cluster_free()
879 err = -EIO; in __ntfs_cluster_free()
883 delta = start_vcn - rl->vcn; in __ntfs_cluster_free()
886 to_free = rl->length - delta; in __ntfs_cluster_free()
890 if (likely(rl->lcn >= 0)) { in __ntfs_cluster_free()
892 err = ntfs_bitmap_set_bits_in_run(lcnbmp_vi, rl->lcn + delta, in __ntfs_cluster_free()
893 to_free, likely(!is_rollback) ? 0 : 1); in __ntfs_cluster_free()
896 ntfs_error(vol->sb, "Failed to clear first run " in __ntfs_cluster_free()
906 count -= to_free; in __ntfs_cluster_free()
914 for (; rl->length && count != 0; ++rl) { in __ntfs_cluster_free()
915 if (unlikely(rl->lcn < LCN_HOLE)) { in __ntfs_cluster_free()
919 vcn = rl->vcn; in __ntfs_cluster_free()
924 ntfs_error(vol->sb, "Failed to map " in __ntfs_cluster_free()
931 if (unlikely(rl->lcn < LCN_HOLE)) { in __ntfs_cluster_free()
933 ntfs_error(vol->sb, "Runlist element " in __ntfs_cluster_free()
937 rl->lcn); in __ntfs_cluster_free()
938 err = -EIO; in __ntfs_cluster_free()
943 to_free = rl->length; in __ntfs_cluster_free()
947 if (likely(rl->lcn >= 0)) { in __ntfs_cluster_free()
949 err = ntfs_bitmap_set_bits_in_run(lcnbmp_vi, rl->lcn, in __ntfs_cluster_free()
950 to_free, likely(!is_rollback) ? 0 : 1); in __ntfs_cluster_free()
953 ntfs_error(vol->sb, "Failed to clear " in __ntfs_cluster_free()
962 count -= to_free; in __ntfs_cluster_free()
968 up_write(&vol->lcnbmp_lock); in __ntfs_cluster_free()
980 up_write(&vol->lcnbmp_lock); in __ntfs_cluster_free()
990 ntfs_error(vol->sb, "Failed to rollback (error %i). Leaving " in __ntfs_cluster_free()
995 up_write(&vol->lcnbmp_lock); in __ntfs_cluster_free()
996 ntfs_error(vol->sb, "Aborting (error %i).", err); in __ntfs_cluster_free()