| blob | eda9972e61599ab29849c47ccba5b188db79d57a |
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3 * lcnalloc.c - Cluster (de)allocation code. Part of the Linux-NTFS project.
4 *
5 * Copyright (c) 2004-2005 Anton Altaparmakov
6 */
8 #ifdef NTFS_RW
10 #include <linux/pagemap.h>
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 */
38 {
53 }
56 }
58 /**
59 * ntfs_cluster_alloc - allocate clusters on an ntfs volume
60 * @vol: mounted ntfs volume on which to allocate the clusters
61 * @start_vcn: vcn to use for the first allocated cluster
62 * @count: number of clusters to allocate
63 * @start_lcn: starting lcn at which to allocate the clusters (or -1 if none)
64 * @zone: zone from which to allocate the clusters
65 * @is_extension: if 'true', this is an attribute extension
66 *
67 * Allocate @count clusters preferably starting at cluster @start_lcn or at the
68 * current allocator position if @start_lcn is -1, on the mounted ntfs volume
69 * @vol. @zone is either DATA_ZONE for allocation of normal clusters or
70 * MFT_ZONE for allocation of clusters for the master file table, i.e. the
71 * $MFT/$DATA attribute.
72 *
73 * @start_vcn specifies the vcn of the first allocated cluster. This makes
74 * merging the resulting runlist with the old runlist easier.
75 *
76 * If @is_extension is 'true', the caller is allocating clusters to extend an
77 * attribute and if it is 'false', the caller is allocating clusters to fill a
78 * hole in an attribute. Practically the difference is that if @is_extension
79 * is 'true' the returned runlist will be terminated with LCN_ENOENT and if
80 * @is_extension is 'false' the runlist will be terminated with
81 * LCN_RL_NOT_MAPPED.
82 *
83 * You need to check the return value with IS_ERR(). If this is false, the
84 * function was successful and the return value is a runlist describing the
85 * allocated cluster(s). If IS_ERR() is true, the function failed and
86 * PTR_ERR() gives you the error code.
87 *
88 * Notes on the allocation algorithm
89 * =================================
90 *
91 * There are two data zones. First is the area between the end of the mft zone
92 * and the end of the volume, and second is the area between the start of the
93 * volume and the start of the mft zone. On unmodified/standard NTFS 1.x
94 * volumes, the second data zone does not exist due to the mft zone being
95 * expanded to cover the start of the volume in order to reserve space for the
96 * mft bitmap attribute.
97 *
98 * This is not the prettiest function but the complexity stems from the need of
99 * implementing the mft vs data zoned approach and from the fact that we have
100 * access to the lcn bitmap in portions of up to 8192 bytes at a time, so we
101 * need to cope with crossing over boundaries of two buffers. Further, the
102 * fact that the allocator allows for caller supplied hints as to the location
103 * of where allocation should begin and the fact that the allocator keeps track
104 * of where in the data zones the next natural allocation should occur,
105 * contribute to the complexity of the function. But it should all be
106 * worthwhile, because this allocator should: 1) be a full implementation of
107 * the MFT zone approach used by Windows NT, 2) cause reduction in
108 * fragmentation, and 3) be speedy in allocations (the code is not optimized
109 * for speed, but the algorithm is, so further speed improvements are probably
110 * possible).
111 *
112 * FIXME: We should be monitoring cluster allocation and increment the MFT zone
113 * size dynamically but this is something for the future. We will just cause
114 * heavier fragmentation by not doing it and I am not even sure Windows would
115 * grow the MFT zone dynamically, so it might even be correct not to do this.
116 * The overhead in doing dynamic MFT zone expansion would be very large and
117 * unlikely worth the effort. (AIA)
118 *
119 * TODO: I have added in double the required zone position pointer wrap around
120 * logic which can be optimized to having only one of the two logic sets.
121 * However, having the double logic will work fine, but if we have only one of
122 * the sets and we get it wrong somewhere, then we get into trouble, so
123 * removing the duplicate logic requires _very_ careful consideration of _all_
124 * possible code paths. So at least for now, I am leaving the double logic -
125 * better safe than sorry... (AIA)
126 *
127 * Locking: - The volume lcn bitmap must be unlocked on entry and is unlocked
128 * on return.
129 * - This function takes the volume lcn bitmap lock for writing and
130 * modifies the bitmap contents.
131 */
136 {
139 s64 clusters;
140 loff_t i_size;
163 /* Return NULL if @count is zero. */
166 /* Take the lcnbmp lock for writing. */
168 /*
169 * If no specific @start_lcn was requested, use the current data zone
170 * position, otherwise use the requested @start_lcn but make sure it
171 * lies outside the mft zone. Also set done_zones to 0 (no zones done)
172 * and pass depending on whether we are starting inside a zone (1) or
173 * at the beginning of a zone (2). If requesting from the MFT_ZONE,
174 * we either start at the current position within the mft zone or at
175 * the specified position. If the latter is out of bounds then we start
176 * at the beginning of the MFT_ZONE.
177 */
180 /*
181 * zone_start and zone_end are the current search range. search_zone
182 * is 1 for mft zone, 2 for data zone 1 (end of mft zone till end of
183 * volume) and 4 for data zone 2 (start of volume till start of mft
184 * zone).
185 */
190 else
193 /*
194 * Zone starts at beginning of volume which means a
195 * single pass is sufficient.
196 */
198 }
202 /*
203 * Starting at beginning of data1_zone which means a single
204 * pass in this zone is sufficient.
205 */
212 /*
213 * Starting at beginning of volume which means a single pass
214 * is sufficient.
215 */
217 }
222 /* Skip searching the mft zone. */
230 }
231 }
232 /*
233 * bmp_pos is the current bit position inside the bitmap. We use
234 * bmp_initial_pos to determine whether or not to do a zone switch.
235 */
238 /* Loop until all clusters are allocated, i.e. clusters == 0. */
245 "search_zone %i, pass %i, zone_start 0x%llx, "
246 "zone_end 0x%llx, bmp_initial_pos 0x%llx, "
253 /* Loop until we run out of free clusters. */
261 }
268 }
270 }
272 PAGE_SHIFT);
277 }
293 "lcn 0x%llx, bmp_pos 0x%llx, "
294 "need_writeback %i, byte ofs 0x%x, "
298 need_writeback,
301 /* Skip full bytes. */
306 }
309 /* If the bit is already set, go onto the next one. */
311 lcn++;
314 }
315 /*
316 * Allocate more memory if needed, including space for
317 * the terminator element.
318 * ntfs_malloc_nofs() operates on whole pages only.
319 */
335 }
341 rlsize);
342 }
343 /* Allocate the bitmap bit. */
345 /* We need to write this bitmap page to disk. */
349 /*
350 * Coalesce with previous run if adjacent LCNs.
351 * Otherwise, append a new run.
352 */
354 "prev_lcn 0x%llx, lcn 0x%llx, "
355 "bmp_pos 0x%llx, prev_run_len 0x%llx, "
362 rlpos);
378 prev_run_len);
382 "run lcn 0x%llx, "
389 prev_run_len;
394 }
397 rlpos++;
398 }
399 /* Done? */
401 LCN tc;
402 /*
403 * Update the current zone position. Positions
404 * of already scanned zones have been updated
405 * during the respective zone switches.
406 */
409 "position, tc 0x%llx, "
412 search_zone);
416 "vol->mft_zone_pos "
431 "vol->mft_zone_pos "
438 "vol->data1_zone_pos "
451 "vol->data1_zone_pos "
458 "vol->data2_zone_pos "
469 "vol->data2_zone_pos "
476 }
479 }
480 lcn++;
481 }
493 }
497 /*
498 * Now do pass 2, scanning the first part of the zone
499 * we omitted in pass 1.
500 */
515 }
516 /* Sanity check. */
521 "zone_start 0x%llx, zone_end 0x%llx, "
528 done_zones_check:
536 /* Now switch to the next zone we haven't done yet. */
542 /* Update mft zone position. */
544 LCN tc;
547 "vol->mft_zone_pos "
564 "vol->mft_zone_pos "
568 }
569 /* Switch from mft zone to data1 zone. */
580 }
585 /* Update data1 zone position. */
587 LCN tc;
590 "vol->data1_zone_pos "
605 "vol->data1_zone_pos "
609 }
610 /* Switch from data1 zone to data2 zone. */
621 }
626 /* Update data2 zone position. */
628 LCN tc;
631 "vol->data2_zone_pos "
644 "vol->data2_zone_pos "
648 }
649 /* Switch from data2 zone to data1 zone. */
653 }
655 "pass %i, bmp_initial_pos 0x%llx, "
665 /* Empty zone. Don't bother searching it. */
667 }
672 /*
673 * All zones are finished! If DATA_ZONE, shrink mft zone. If
674 * MFT_ZONE, we have really run out of space.
675 */
684 /* Really no more space left on device. */
700 }
707 "vol->mft_zone_start 0x%llx, "
708 "vol->mft_zone_end 0x%llx, "
709 "vol->mft_zone_pos 0x%llx, search_zone 2, "
710 "pass 2, dones_zones 0x%x, zone_start 0x%llx, "
711 "zone_end 0x%llx, vol->data1_zone_pos 0x%llx, "
720 }
722 out:
724 /* Add runlist terminator element. */
729 }
736 }
738 }
743 }
751 "err -ENOSPC, first free lcn 0x%llx, "
752 "could allocate up to 0x%llx "
756 /* Deallocate all allocated clusters. */
761 "Leaving inconsistent metadata! "
764 }
765 /* Free the runlist. */
773 }
775 /**
776 * __ntfs_cluster_free - free clusters on an ntfs volume
777 * @ni: ntfs inode whose runlist describes the clusters to free
778 * @start_vcn: vcn in the runlist of @ni at which to start freeing clusters
779 * @count: number of clusters to free or -1 for all clusters
780 * @ctx: active attribute search context if present or NULL if not
781 * @is_rollback: true if this is a rollback operation
782 *
783 * Free @count clusters starting at the cluster @start_vcn in the runlist
784 * described by the vfs inode @ni.
785 *
786 * If @count is -1, all clusters from @start_vcn to the end of the runlist are
787 * deallocated. Thus, to completely free all clusters in a runlist, use
788 * @start_vcn = 0 and @count = -1.
789 *
790 * If @ctx is specified, it is an active search context of @ni and its base mft
791 * record. This is needed when __ntfs_cluster_free() encounters unmapped
792 * runlist fragments and allows their mapping. If you do not have the mft
793 * record mapped, you can specify @ctx as NULL and __ntfs_cluster_free() will
794 * perform the necessary mapping and unmapping.
795 *
796 * Note, __ntfs_cluster_free() saves the state of @ctx on entry and restores it
797 * before returning. Thus, @ctx will be left pointing to the same attribute on
798 * return as on entry. However, the actual pointers in @ctx may point to
799 * different memory locations on return, so you must remember to reset any
800 * cached pointers from the @ctx, i.e. after the call to __ntfs_cluster_free(),
801 * you will probably want to do:
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 *.
806 *
807 * @is_rollback should always be 'false', it is for internal use to rollback
808 * errors. You probably want to use ntfs_cluster_free() instead.
809 *
810 * Note, __ntfs_cluster_free() does not modify the runlist, so you have to
811 * remove from the runlist or mark sparse the freed runs later.
812 *
813 * Return the number of deallocated clusters (not counting sparse ones) on
814 * success and -errno on error.
815 *
816 * WARNING: If @ctx is supplied, regardless of whether success or failure is
817 * returned, you need to check IS_ERR(@ctx->mrec) and if 'true' the @ctx
818 * is no longer valid, i.e. you need to either call
819 * ntfs_attr_reinit_search_ctx() or ntfs_attr_put_search_ctx() on it.
820 * In that case PTR_ERR(@ctx->mrec) will give you the error code for
821 * why the mapping of the old inode failed.
822 *
823 * Locking: - The runlist described by @ni must be locked for writing on entry
824 * and is locked on return. Note the runlist may be modified when
825 * needed runlist fragments need to be mapped.
826 * - The volume lcn bitmap must be unlocked on entry and is unlocked
827 * on return.
828 * - This function takes the volume lcn bitmap lock for writing and
829 * modifies the bitmap contents.
830 * - If @ctx is NULL, the base mft record of @ni must not be mapped on
831 * entry and it will be left unmapped on return.
832 * - If @ctx is not NULL, the base mft record must be mapped on entry
833 * and it will be left mapped on return.
834 */
837 {
854 /*
855 * Lock the lcn bitmap for writing but only if not rolling back. We
856 * must hold the lock all the way including through rollback otherwise
857 * rollback is not possible because once we have cleared a bit and
858 * dropped the lock, anyone could have set the bit again, thus
859 * allocating the cluster for another use.
860 */
874 }
881 }
882 /* Find the starting cluster inside the run that needs freeing. */
885 /* The number of clusters in this run that need freeing. */
891 /* Do the actual freeing of the clusters in this run. */
899 }
900 /* We have freed @to_free real clusters. */
902 };
903 /* Go to the next run and adjust the number of clusters left to free. */
908 /* Keep track of the total "freed" clusters, including sparse ones. */
910 /*
911 * Loop over the remaining runs, using @count as a capping value, and
912 * free them.
913 */
916 VCN vcn;
918 /* Attempt to map runlist. */
925 "runlist fragment or "
926 "failed to find "
927 "subsequent runlist "
930 }
934 "has invalid lcn "
940 }
941 }
942 /* The number of clusters in this run that need freeing. */
948 /* Do the actual freeing of the clusters in the run. */
956 }
957 /* We have freed @to_free real clusters. */
959 }
960 /* Adjust the number of clusters left to free. */
964 /* Update the total done clusters. */
966 }
972 /* We are done. Return the number of actually freed clusters. */
975 err_out:
978 /* If no real clusters were freed, no need to rollback. */
982 }
983 /*
984 * Attempt to rollback and if that succeeds just return the error code.
985 * If rollback fails, set the volume errors flag, emit an error
986 * message, and return the error code.
987 */
991 "inconsistent metadata! Unmount and run "
994 }
998 }