Lines Matching +full:runs +full:- +full:on
1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * runlist.c - NTFS runlist handling code. Part of the Linux-NTFS project.
5 * Copyright (c) 2001-2007 Anton Altaparmakov
6 * Copyright (c) 2002-2005 Richard Russon
16 * ntfs_rl_mm - runlist memmove
28 * ntfs_rl_mc - runlist memory copy
41 * ntfs_rl_realloc - Reallocate memory for runlists
55 * On success, return a pointer to the newly allocated, or recycled, memory.
56 * On error, return -errno. The following error codes are defined:
57 * -ENOMEM - Not enough memory to allocate runlist array.
58 * -EINVAL - Invalid parameters were passed in.
72 return ERR_PTR(-ENOMEM); in ntfs_rl_realloc()
84 * ntfs_rl_realloc_nofail - Reallocate memory for runlists
101 * On success, return a pointer to the newly allocated, or recycled, memory.
102 * On error, return -errno. The following error codes are defined:
103 * -ENOMEM - Not enough memory to allocate runlist array.
104 * -EINVAL - Invalid parameters were passed in.
129 * ntfs_are_rl_mergeable - test if two runlists can be joined together
148 if ((dst->lcn == LCN_RL_NOT_MAPPED) && (src->lcn == LCN_RL_NOT_MAPPED)) in ntfs_are_rl_mergeable()
150 /* If the runs are misaligned, we cannot merge them. */ in ntfs_are_rl_mergeable()
151 if ((dst->vcn + dst->length) != src->vcn) in ntfs_are_rl_mergeable()
153 /* If both runs are non-sparse and contiguous, we can merge them. */ in ntfs_are_rl_mergeable()
154 if ((dst->lcn >= 0) && (src->lcn >= 0) && in ntfs_are_rl_mergeable()
155 ((dst->lcn + dst->length) == src->lcn)) in ntfs_are_rl_mergeable()
158 if ((dst->lcn == LCN_HOLE) && (src->lcn == LCN_HOLE)) in ntfs_are_rl_mergeable()
165 * __ntfs_rl_merge - merge two runlists without testing if they can be merged
177 dst->length += src->length; in __ntfs_rl_merge()
181 * ntfs_rl_append - append a runlist after a given element
182 * @dst: original runlist to be worked on
194 * On success, return a pointer to the new, combined, runlist. Note, both
199 * On error, return -errno. Both runlists are left unmodified. The following
201 * -ENOMEM - Not enough memory to allocate runlist array.
202 * -EINVAL - Invalid parameters were passed in.
208 int marker; /* End of the inserted runs. */ in ntfs_rl_append()
215 right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1); in ntfs_rl_append()
218 dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - right); in ntfs_rl_append()
228 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1); in ntfs_rl_append()
230 /* First run after the @src runs that have been inserted. */ in ntfs_rl_append()
234 ntfs_rl_mm(dst, marker, loc + 1 + right, dsize - (loc + 1 + right)); in ntfs_rl_append()
238 dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn; in ntfs_rl_append()
242 dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length; in ntfs_rl_append()
248 * ntfs_rl_insert - insert a runlist into another
249 * @dst: original runlist to be worked on
261 * On success, return a pointer to the new, combined, runlist. Note, both
266 * On error, return -errno. Both runlists are left unmodified. The following
268 * -ENOMEM - Not enough memory to allocate runlist array.
269 * -EINVAL - Invalid parameters were passed in.
276 int marker; /* End of the inserted runs. */ in ntfs_rl_insert()
290 left = ntfs_are_rl_mergeable(dst + loc - 1, src); in ntfs_rl_insert()
292 merged_length = dst[loc - 1].length; in ntfs_rl_insert()
294 merged_length += src->length; in ntfs_rl_insert()
296 disc = (src[0].vcn > dst[loc - 1].vcn + merged_length); in ntfs_rl_insert()
302 dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left + disc); in ntfs_rl_insert()
310 __ntfs_rl_merge(dst + loc - 1, src); in ntfs_rl_insert()
312 * First run after the @src runs that have been inserted. in ntfs_rl_insert()
314 * runs in @src. However, if @left, then the first run in @src has in ntfs_rl_insert()
318 marker = loc + ssize - left + disc; in ntfs_rl_insert()
321 ntfs_rl_mm(dst, marker, loc, dsize - loc); in ntfs_rl_insert()
322 ntfs_rl_mc(dst, loc + disc, src, left, ssize - left); in ntfs_rl_insert()
325 dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length; in ntfs_rl_insert()
328 dst[marker].length = dst[marker + 1].vcn - dst[marker].vcn; in ntfs_rl_insert()
333 dst[loc].vcn = dst[loc - 1].vcn + dst[loc - 1].length; in ntfs_rl_insert()
334 dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn; in ntfs_rl_insert()
345 * ntfs_rl_replace - overwrite a runlist element with another runlist
346 * @dst: original runlist to be worked on
357 * On success, return a pointer to the new, combined, runlist. Note, both
362 * On error, return -errno. Both runlists are left unmodified. The following
364 * -ENOMEM - Not enough memory to allocate runlist array.
365 * -EINVAL - Invalid parameters were passed in.
374 int marker; /* End of the inserted runs. */ in ntfs_rl_replace()
381 right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1); in ntfs_rl_replace()
383 left = ntfs_are_rl_mergeable(dst + loc - 1, src); in ntfs_rl_replace()
386 * ends get merged. The -1 accounts for the run being replaced. in ntfs_rl_replace()
388 delta = ssize - 1 - left - right; in ntfs_rl_replace()
401 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1); in ntfs_rl_replace()
403 __ntfs_rl_merge(dst + loc - 1, src); in ntfs_rl_replace()
406 * to make space for the runs to be copied from @src, i.e. the first in ntfs_rl_replace()
409 * replaced run. However, if @right, then one of @dst's runs is in ntfs_rl_replace()
414 * First run after the @src runs that have been inserted, i.e. where in ntfs_rl_replace()
417 * runs in @src. However, if @left, then the first run in @src has in ntfs_rl_replace()
420 marker = loc + ssize - left; in ntfs_rl_replace()
423 ntfs_rl_mm(dst, marker, tail, dsize - tail); in ntfs_rl_replace()
424 ntfs_rl_mc(dst, loc, src, left, ssize - left); in ntfs_rl_replace()
427 if (dsize - tail > 0 && dst[marker].lcn == LCN_ENOENT) in ntfs_rl_replace()
428 dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length; in ntfs_rl_replace()
433 * ntfs_rl_split - insert a runlist into the centre of a hole
434 * @dst: original runlist to be worked on
446 * On success, return a pointer to the new, combined, runlist. Note, both
451 * On error, return -errno. Both runlists are left unmodified. The following
453 * -ENOMEM - Not enough memory to allocate runlist array.
454 * -EINVAL - Invalid parameters were passed in.
472 ntfs_rl_mm(dst, loc + 1 + ssize, loc, dsize - loc); in ntfs_rl_split()
476 dst[loc].length = dst[loc+1].vcn - dst[loc].vcn; in ntfs_rl_split()
478 dst[loc+ssize+1].length = dst[loc+ssize+2].vcn - dst[loc+ssize+1].vcn; in ntfs_rl_split()
484 * ntfs_runlists_merge - merge two runlists into one
485 * @drl: original runlist to be worked on
499 * - be inserted at the beginning of a hole,
500 * - split the hole in two and be inserted between the two fragments,
501 * - be appended at the end of a hole, or it can
502 * - replace the whole hole.
506 * On success, return a pointer to the new, combined, runlist. Note, both
511 * On error, return -errno. Both runlists are left unmodified. The following
513 * -ENOMEM - Not enough memory to allocate runlist array.
514 * -EINVAL - Invalid parameters were passed in.
515 * -ERANGE - The runlists overlap and cannot be merged.
540 return ERR_PTR(-EINVAL); in ntfs_runlists_merge()
590 return ERR_PTR(-ERANGE); in ntfs_runlists_merge()
603 for (sfinal = send; sfinal >= 0 && srl[sfinal].lcn < LCN_HOLE; sfinal--) in ntfs_runlists_merge()
605 for (dfinal = dend; dfinal >= 0 && drl[dfinal].lcn < LCN_HOLE; dfinal--) in ntfs_runlists_merge()
612 int ss = sfinal - sstart + 1; in ntfs_runlists_merge()
618 (srl[send - 1].vcn + srl[send - 1].length))); in ntfs_runlists_merge()
623 if (marker && (drl[dins].vcn + drl[dins].length > srl[send - 1].vcn)) in ntfs_runlists_merge()
669 ds--; in ntfs_runlists_merge()
682 drl[ds].vcn = drl[ds - 1].vcn + in ntfs_runlists_merge()
683 drl[ds - 1].length; in ntfs_runlists_merge()
686 slots--; in ntfs_runlists_merge()
688 drl[ds].length = marker_vcn - drl[ds].vcn; in ntfs_runlists_merge()
708 * ntfs_mapping_pairs_decompress - convert mapping pairs array to runlist
709 * @vol: ntfs volume on which the attribute resides
715 * Decompress the attribute @attr's mapping pairs array into a runlist. On
722 * On error, return -errno. @old_rl is left unmodified in that case.
725 * -ENOMEM - Not enough memory to allocate runlist array.
726 * -EIO - Corrupt runlist.
727 * -EINVAL - Invalid parameters were passed in.
728 * -ERANGE - The two runlists overlap.
733 * runlist if overlap present before returning ERR_PTR(-ERANGE)).
750 /* Make sure attr exists and is non-resident. */ in ntfs_mapping_pairs_decompress()
751 if (!attr || !attr->non_resident || sle64_to_cpu( in ntfs_mapping_pairs_decompress()
752 attr->data.non_resident.lowest_vcn) < (VCN)0) { in ntfs_mapping_pairs_decompress()
753 ntfs_error(vol->sb, "Invalid arguments."); in ntfs_mapping_pairs_decompress()
754 return ERR_PTR(-EINVAL); in ntfs_mapping_pairs_decompress()
758 vcn = sle64_to_cpu(attr->data.non_resident.lowest_vcn); in ntfs_mapping_pairs_decompress()
762 attr->data.non_resident.mapping_pairs_offset); in ntfs_mapping_pairs_decompress()
763 attr_end = (u8*)attr + le32_to_cpu(attr->length); in ntfs_mapping_pairs_decompress()
765 ntfs_error(vol->sb, "Corrupt attribute."); in ntfs_mapping_pairs_decompress()
766 return ERR_PTR(-EIO); in ntfs_mapping_pairs_decompress()
776 return ERR_PTR(-ENOMEM); in ntfs_mapping_pairs_decompress()
779 rl->vcn = 0; in ntfs_mapping_pairs_decompress()
780 rl->lcn = LCN_RL_NOT_MAPPED; in ntfs_mapping_pairs_decompress()
781 rl->length = vcn; in ntfs_mapping_pairs_decompress()
787 * not-mapped and terminator elements. ntfs_malloc_nofs() in ntfs_mapping_pairs_decompress()
788 * operates on whole pages only. in ntfs_mapping_pairs_decompress()
796 return ERR_PTR(-ENOMEM); in ntfs_mapping_pairs_decompress()
816 for (deltaxcn = (s8)buf[b--]; b; b--) in ntfs_mapping_pairs_decompress()
819 ntfs_error(vol->sb, "Missing length entry in mapping " in ntfs_mapping_pairs_decompress()
821 deltaxcn = (s64)-1; in ntfs_mapping_pairs_decompress()
825 * hence clean-up and return NULL. in ntfs_mapping_pairs_decompress()
828 ntfs_error(vol->sb, "Invalid length in mapping pairs " in ntfs_mapping_pairs_decompress()
841 * sparse clusters on NTFS 3.0+, in which case we set the lcn in ntfs_mapping_pairs_decompress()
852 for (deltaxcn = (s8)buf[b--]; b > b2; b--) in ntfs_mapping_pairs_decompress()
858 * On NTFS 1.2-, apparently can have lcn == -1 to in ntfs_mapping_pairs_decompress()
861 * -1. So if either is found give us a message so we in ntfs_mapping_pairs_decompress()
864 if (vol->major_ver < 3) { in ntfs_mapping_pairs_decompress()
865 if (unlikely(deltaxcn == (LCN)-1)) in ntfs_mapping_pairs_decompress()
866 ntfs_error(vol->sb, "lcn delta == -1"); in ntfs_mapping_pairs_decompress()
867 if (unlikely(lcn == (LCN)-1)) in ntfs_mapping_pairs_decompress()
868 ntfs_error(vol->sb, "lcn == -1"); in ntfs_mapping_pairs_decompress()
871 /* Check lcn is not below -1. */ in ntfs_mapping_pairs_decompress()
872 if (unlikely(lcn < (LCN)-1)) { in ntfs_mapping_pairs_decompress()
873 ntfs_error(vol->sb, "Invalid LCN < -1 in " in ntfs_mapping_pairs_decompress()
889 * vcn in the runlist - 1, or something has gone badly wrong. in ntfs_mapping_pairs_decompress()
891 deltaxcn = sle64_to_cpu(attr->data.non_resident.highest_vcn); in ntfs_mapping_pairs_decompress()
892 if (unlikely(deltaxcn && vcn - 1 != deltaxcn)) { in ntfs_mapping_pairs_decompress()
894 ntfs_error(vol->sb, "Corrupt mapping pairs array in " in ntfs_mapping_pairs_decompress()
895 "non-resident attribute."); in ntfs_mapping_pairs_decompress()
899 if (!attr->data.non_resident.lowest_vcn) { in ntfs_mapping_pairs_decompress()
903 attr->data.non_resident.allocated_size) + in ntfs_mapping_pairs_decompress()
904 vol->cluster_size - 1) >> in ntfs_mapping_pairs_decompress()
905 vol->cluster_size_bits) - 1; in ntfs_mapping_pairs_decompress()
925 vcn += rl[rlpos].length = max_cluster - in ntfs_mapping_pairs_decompress()
930 ntfs_error(vol->sb, "Corrupt attribute. " in ntfs_mapping_pairs_decompress()
957 ntfs_error(vol->sb, "Failed to merge runlists."); in ntfs_mapping_pairs_decompress()
960 ntfs_error(vol->sb, "Corrupt attribute."); in ntfs_mapping_pairs_decompress()
963 return ERR_PTR(-EIO); in ntfs_mapping_pairs_decompress()
967 * ntfs_rl_vcn_to_lcn - convert a vcn into a lcn given a runlist
981 * LCN_HOLE Hole / not allocated on disk.
986 * Locking: - The caller must have locked the runlist (for reading or writing).
987 * - This function does not touch the lock, nor does it modify the
1010 return rl[i].lcn + (vcn - rl[i].vcn); in ntfs_rl_vcn_to_lcn()
1027 * ntfs_rl_find_vcn_nolock - find a vcn in a runlist
1032 * address of the runlist element containing the @vcn on success.
1037 * Locking: The runlist must be locked on entry.
1044 while (likely(rl->length)) { in ntfs_rl_find_vcn_nolock()
1046 if (likely(rl->lcn >= LCN_HOLE)) in ntfs_rl_find_vcn_nolock()
1052 if (likely(rl->lcn == LCN_ENOENT)) in ntfs_rl_find_vcn_nolock()
1058 * ntfs_get_nr_significant_bytes - get number of bytes needed to store a number
1080 } while (l != 0 && l != -1); in ntfs_get_nr_significant_bytes()
1081 j = (n >> 8 * (i - 1)) & 0xff; in ntfs_get_nr_significant_bytes()
1089 * ntfs_get_size_for_mapping_pairs - get bytes needed for mapping pairs array
1099 * A @last_vcn of -1 means end of runlist and in that case the size of the
1108 * Return the calculated size in bytes on success. On error, return -errno.
1110 * -EINVAL - Run list contains unmapped elements. Make sure to only pass
1112 * -EIO - The runlist is corrupt.
1114 * Locking: @rl must be locked on entry (either for reading or writing), it
1126 BUG_ON(last_vcn < -1); in ntfs_get_size_for_mapping_pairs()
1134 while (rl->length && first_vcn >= rl[1].vcn) in ntfs_get_size_for_mapping_pairs()
1136 if (unlikely((!rl->length && first_vcn > rl->vcn) || in ntfs_get_size_for_mapping_pairs()
1137 first_vcn < rl->vcn)) in ntfs_get_size_for_mapping_pairs()
1138 return -EINVAL; in ntfs_get_size_for_mapping_pairs()
1143 if (first_vcn > rl->vcn) { in ntfs_get_size_for_mapping_pairs()
1144 s64 delta, length = rl->length; in ntfs_get_size_for_mapping_pairs()
1146 /* We know rl->length != 0 already. */ in ntfs_get_size_for_mapping_pairs()
1147 if (unlikely(length < 0 || rl->lcn < LCN_HOLE)) in ntfs_get_size_for_mapping_pairs()
1156 length = s1 - rl->vcn; in ntfs_get_size_for_mapping_pairs()
1159 delta = first_vcn - rl->vcn; in ntfs_get_size_for_mapping_pairs()
1161 rls += 1 + ntfs_get_nr_significant_bytes(length - delta); in ntfs_get_size_for_mapping_pairs()
1164 * are on NTFS 3.0+, we don't store it at all, i.e. we need in ntfs_get_size_for_mapping_pairs()
1165 * zero space. On earlier NTFS versions we just store the lcn. in ntfs_get_size_for_mapping_pairs()
1166 * Note: this assumes that on NTFS 1.2-, holes are stored with in ntfs_get_size_for_mapping_pairs()
1167 * an lcn of -1 and not a delta_lcn of -1 (unless both are -1). in ntfs_get_size_for_mapping_pairs()
1169 if (likely(rl->lcn >= 0 || vol->major_ver < 3)) { in ntfs_get_size_for_mapping_pairs()
1170 prev_lcn = rl->lcn; in ntfs_get_size_for_mapping_pairs()
1171 if (likely(rl->lcn >= 0)) in ntfs_get_size_for_mapping_pairs()
1179 /* Do the full runs. */ in ntfs_get_size_for_mapping_pairs()
1180 for (; rl->length && !the_end; rl++) { in ntfs_get_size_for_mapping_pairs()
1181 s64 length = rl->length; in ntfs_get_size_for_mapping_pairs()
1183 if (unlikely(length < 0 || rl->lcn < LCN_HOLE)) in ntfs_get_size_for_mapping_pairs()
1192 length = s1 - rl->vcn; in ntfs_get_size_for_mapping_pairs()
1199 * are on NTFS 3.0+, we don't store it at all, i.e. we need in ntfs_get_size_for_mapping_pairs()
1200 * zero space. On earlier NTFS versions we just store the lcn. in ntfs_get_size_for_mapping_pairs()
1201 * Note: this assumes that on NTFS 1.2-, holes are stored with in ntfs_get_size_for_mapping_pairs()
1202 * an lcn of -1 and not a delta_lcn of -1 (unless both are -1). in ntfs_get_size_for_mapping_pairs()
1204 if (likely(rl->lcn >= 0 || vol->major_ver < 3)) { in ntfs_get_size_for_mapping_pairs()
1206 rls += ntfs_get_nr_significant_bytes(rl->lcn - in ntfs_get_size_for_mapping_pairs()
1208 prev_lcn = rl->lcn; in ntfs_get_size_for_mapping_pairs()
1213 if (rl->lcn == LCN_RL_NOT_MAPPED) in ntfs_get_size_for_mapping_pairs()
1214 rls = -EINVAL; in ntfs_get_size_for_mapping_pairs()
1216 rls = -EIO; in ntfs_get_size_for_mapping_pairs()
1221 * ntfs_write_significant_bytes - write the significant bytes of a number
1235 * Return the number of bytes written on success. On error, i.e. the
1236 * destination buffer @dst is too small, return -ENOSPC.
1252 } while (l != 0 && l != -1); in ntfs_write_significant_bytes()
1253 j = (n >> 8 * (i - 1)) & 0xff; in ntfs_write_significant_bytes()
1259 *dst = (s8)-1; in ntfs_write_significant_bytes()
1268 return -ENOSPC; in ntfs_write_significant_bytes()
1272 * ntfs_mapping_pairs_build - build the mapping pairs array from a runlist
1279 * @stop_vcn: first vcn outside destination buffer on success or -ENOSPC
1286 * A @last_vcn of -1 means end of runlist and in that case the mapping pairs
1292 * On success or -ENOSPC error, if @stop_vcn is not NULL, *@stop_vcn is set to
1293 * the first vcn outside the destination buffer. Note that on error, @dst has
1299 * Return 0 on success and -errno on error. The following error codes are
1301 * -EINVAL - Run list contains unmapped elements. Make sure to only pass
1303 * -EIO - The runlist is corrupt.
1304 * -ENOSPC - The destination buffer is too small.
1306 * Locking: @rl must be locked on entry (either for reading or writing), it
1315 int err = -ENOSPC; in ntfs_mapping_pairs_build()
1320 BUG_ON(last_vcn < -1); in ntfs_mapping_pairs_build()
1333 while (rl->length && first_vcn >= rl[1].vcn) in ntfs_mapping_pairs_build()
1335 if (unlikely((!rl->length && first_vcn > rl->vcn) || in ntfs_mapping_pairs_build()
1336 first_vcn < rl->vcn)) in ntfs_mapping_pairs_build()
1337 return -EINVAL; in ntfs_mapping_pairs_build()
1342 dst_max = dst + dst_len - 1; in ntfs_mapping_pairs_build()
1345 if (first_vcn > rl->vcn) { in ntfs_mapping_pairs_build()
1346 s64 delta, length = rl->length; in ntfs_mapping_pairs_build()
1348 /* We know rl->length != 0 already. */ in ntfs_mapping_pairs_build()
1349 if (unlikely(length < 0 || rl->lcn < LCN_HOLE)) in ntfs_mapping_pairs_build()
1358 length = s1 - rl->vcn; in ntfs_mapping_pairs_build()
1361 delta = first_vcn - rl->vcn; in ntfs_mapping_pairs_build()
1364 length - delta); in ntfs_mapping_pairs_build()
1369 * are on NTFS 3.0+, we don't store it at all, i.e. we need in ntfs_mapping_pairs_build()
1370 * zero space. On earlier NTFS versions we just write the lcn in ntfs_mapping_pairs_build()
1373 * case on NT4. - We assume that we just need to write the lcn in ntfs_mapping_pairs_build()
1376 if (likely(rl->lcn >= 0 || vol->major_ver < 3)) { in ntfs_mapping_pairs_build()
1377 prev_lcn = rl->lcn; in ntfs_mapping_pairs_build()
1378 if (likely(rl->lcn >= 0)) in ntfs_mapping_pairs_build()
1397 /* Do the full runs. */ in ntfs_mapping_pairs_build()
1398 for (; rl->length && !the_end; rl++) { in ntfs_mapping_pairs_build()
1399 s64 length = rl->length; in ntfs_mapping_pairs_build()
1401 if (unlikely(length < 0 || rl->lcn < LCN_HOLE)) in ntfs_mapping_pairs_build()
1410 length = s1 - rl->vcn; in ntfs_mapping_pairs_build()
1420 * are on NTFS 3.0+, we don't store it at all, i.e. we need in ntfs_mapping_pairs_build()
1421 * zero space. On earlier NTFS versions we just write the lcn in ntfs_mapping_pairs_build()
1424 * case on NT4. - We assume that we just need to write the lcn in ntfs_mapping_pairs_build()
1427 if (likely(rl->lcn >= 0 || vol->major_ver < 3)) { in ntfs_mapping_pairs_build()
1430 len_len, dst_max, rl->lcn - prev_lcn); in ntfs_mapping_pairs_build()
1433 prev_lcn = rl->lcn; in ntfs_mapping_pairs_build()
1449 *stop_vcn = rl->vcn; in ntfs_mapping_pairs_build()
1454 if (rl->lcn == LCN_RL_NOT_MAPPED) in ntfs_mapping_pairs_build()
1455 err = -EINVAL; in ntfs_mapping_pairs_build()
1457 err = -EIO; in ntfs_mapping_pairs_build()
1462 * ntfs_rl_truncate_nolock - truncate a runlist starting at a specified vcn
1481 * Return 0 on success and -errno on error.
1483 * Locking: The caller must hold @runlist->lock for writing.
1494 rl = runlist->rl; in ntfs_rl_truncate_nolock()
1497 runlist->rl = NULL; in ntfs_rl_truncate_nolock()
1509 ntfs_error(vol->sb, "Not enough memory to allocate " in ntfs_rl_truncate_nolock()
1511 return -ENOMEM; in ntfs_rl_truncate_nolock()
1513 runlist->rl = rl; in ntfs_rl_truncate_nolock()
1514 rl[1].length = rl->vcn = 0; in ntfs_rl_truncate_nolock()
1515 rl->lcn = LCN_HOLE; in ntfs_rl_truncate_nolock()
1516 rl[1].vcn = rl->length = new_length; in ntfs_rl_truncate_nolock()
1520 BUG_ON(new_length < rl->vcn); in ntfs_rl_truncate_nolock()
1522 while (likely(rl->length && new_length >= rl[1].vcn)) in ntfs_rl_truncate_nolock()
1528 if (rl->length) { in ntfs_rl_truncate_nolock()
1535 while (likely(trl->length)) in ntfs_rl_truncate_nolock()
1537 old_size = trl - runlist->rl + 1; in ntfs_rl_truncate_nolock()
1539 rl->length = new_length - rl->vcn; in ntfs_rl_truncate_nolock()
1545 if (rl->length) { in ntfs_rl_truncate_nolock()
1547 if (!rl->length) in ntfs_rl_truncate_nolock()
1549 rl->vcn = new_length; in ntfs_rl_truncate_nolock()
1550 rl->length = 0; in ntfs_rl_truncate_nolock()
1552 rl->lcn = LCN_ENOENT; in ntfs_rl_truncate_nolock()
1555 int new_size = rl - runlist->rl + 1; in ntfs_rl_truncate_nolock()
1556 rl = ntfs_rl_realloc(runlist->rl, old_size, new_size); in ntfs_rl_truncate_nolock()
1558 ntfs_warning(vol->sb, "Failed to shrink " in ntfs_rl_truncate_nolock()
1564 runlist->rl = rl; in ntfs_rl_truncate_nolock()
1566 } else if (likely(/* !rl->length && */ new_length > rl->vcn)) { in ntfs_rl_truncate_nolock()
1573 if ((rl > runlist->rl) && ((rl - 1)->lcn == LCN_HOLE)) in ntfs_rl_truncate_nolock()
1574 (rl - 1)->length = new_length - (rl - 1)->vcn; in ntfs_rl_truncate_nolock()
1577 old_size = rl - runlist->rl + 1; in ntfs_rl_truncate_nolock()
1579 rl = ntfs_rl_realloc(runlist->rl, old_size, in ntfs_rl_truncate_nolock()
1582 ntfs_error(vol->sb, "Failed to expand runlist " in ntfs_rl_truncate_nolock()
1586 runlist->rl = rl; in ntfs_rl_truncate_nolock()
1591 rl += old_size - 1; in ntfs_rl_truncate_nolock()
1593 rl->lcn = LCN_HOLE; in ntfs_rl_truncate_nolock()
1594 rl->length = new_length - rl->vcn; in ntfs_rl_truncate_nolock()
1597 rl->length = 0; in ntfs_rl_truncate_nolock()
1599 rl->vcn = new_length; in ntfs_rl_truncate_nolock()
1600 rl->lcn = LCN_ENOENT; in ntfs_rl_truncate_nolock()
1601 } else /* if (unlikely(!rl->length && new_length == rl->vcn)) */ { in ntfs_rl_truncate_nolock()
1603 rl->lcn = LCN_ENOENT; in ntfs_rl_truncate_nolock()
1610 * ntfs_rl_punch_nolock - punch a hole into a runlist
1619 * Return 0 on success and -errno on error, in which case @runlist has not been
1623 * -ENOENT.
1626 * + @length return error code -EINVAL.
1628 * Locking: The caller must hold @runlist->lock for writing.
1645 rl = runlist->rl; in ntfs_rl_punch_nolock()
1649 return -ENOENT; in ntfs_rl_punch_nolock()
1652 while (likely(rl->length && start >= rl[1].vcn)) in ntfs_rl_punch_nolock()
1656 while (likely(rl_end->length && end >= rl_end[1].vcn)) { in ntfs_rl_punch_nolock()
1658 if (unlikely(rl_end->lcn < LCN_HOLE)) in ntfs_rl_punch_nolock()
1659 return -EINVAL; in ntfs_rl_punch_nolock()
1663 if (unlikely(rl_end->length && rl_end->lcn < LCN_HOLE)) in ntfs_rl_punch_nolock()
1664 return -EINVAL; in ntfs_rl_punch_nolock()
1666 if (!rl_end->length && end > rl_end->vcn) in ntfs_rl_punch_nolock()
1667 return -ENOENT; in ntfs_rl_punch_nolock()
1670 if (!rl->length) in ntfs_rl_punch_nolock()
1671 return -ENOENT; in ntfs_rl_punch_nolock()
1674 while (likely(rl_real_end->length)) in ntfs_rl_punch_nolock()
1676 old_size = rl_real_end - runlist->rl + 1; in ntfs_rl_punch_nolock()
1678 if (rl->lcn == LCN_HOLE) { in ntfs_rl_punch_nolock()
1689 rl->length = end - rl->vcn; in ntfs_rl_punch_nolock()
1691 if (rl_end->lcn == LCN_HOLE) { in ntfs_rl_punch_nolock()
1693 rl->length = rl_end->vcn - rl->vcn; in ntfs_rl_punch_nolock()
1699 memmove(rl, rl_end, (rl_real_end - rl_end + 1) * in ntfs_rl_punch_nolock()
1702 if (end > rl->vcn) { in ntfs_rl_punch_nolock()
1703 delta = end - rl->vcn; in ntfs_rl_punch_nolock()
1704 rl->vcn = end; in ntfs_rl_punch_nolock()
1705 rl->length -= delta; in ntfs_rl_punch_nolock()
1707 if (rl->lcn >= 0) in ntfs_rl_punch_nolock()
1708 rl->lcn += delta; in ntfs_rl_punch_nolock()
1713 rl = ntfs_rl_realloc(runlist->rl, old_size, in ntfs_rl_punch_nolock()
1714 old_size - (rl_end - rl)); in ntfs_rl_punch_nolock()
1716 ntfs_warning(vol->sb, "Failed to shrink " in ntfs_rl_punch_nolock()
1722 runlist->rl = rl; in ntfs_rl_punch_nolock()
1731 if (start == rl->vcn) { in ntfs_rl_punch_nolock()
1743 if (rl > runlist->rl && (rl - 1)->lcn == LCN_HOLE) { in ntfs_rl_punch_nolock()
1744 rl--; in ntfs_rl_punch_nolock()
1748 rl->lcn = LCN_HOLE; in ntfs_rl_punch_nolock()
1755 * @start, and @end and one for the remaining non-sparse in ntfs_rl_punch_nolock()
1758 trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1); in ntfs_rl_punch_nolock()
1762 if (runlist->rl != trl) { in ntfs_rl_punch_nolock()
1763 rl = trl + (rl - runlist->rl); in ntfs_rl_punch_nolock()
1764 rl_end = trl + (rl_end - runlist->rl); in ntfs_rl_punch_nolock()
1765 rl_real_end = trl + (rl_real_end - runlist->rl); in ntfs_rl_punch_nolock()
1766 runlist->rl = trl; in ntfs_rl_punch_nolock()
1769 /* Shift all the runs up by one. */ in ntfs_rl_punch_nolock()
1770 memmove(rl + 1, rl, (rl_real_end - rl + 1) * sizeof(*rl)); in ntfs_rl_punch_nolock()
1771 /* Finally, setup the two split runs. */ in ntfs_rl_punch_nolock()
1772 rl->lcn = LCN_HOLE; in ntfs_rl_punch_nolock()
1773 rl->length = length; in ntfs_rl_punch_nolock()
1775 rl->vcn += length; in ntfs_rl_punch_nolock()
1777 if (rl->lcn >= 0 || lcn_fixup) in ntfs_rl_punch_nolock()
1778 rl->lcn += length; in ntfs_rl_punch_nolock()
1779 rl->length -= length; in ntfs_rl_punch_nolock()
1787 * @start is in to end at @start - 1, deleting all runs after that up in ntfs_rl_punch_nolock()
1791 if (rl_end->lcn == LCN_HOLE) { in ntfs_rl_punch_nolock()
1793 rl->length = start - rl->vcn; in ntfs_rl_punch_nolock()
1797 memmove(rl, rl_end, (rl_real_end - rl_end + 1) * in ntfs_rl_punch_nolock()
1800 rl->vcn = start; in ntfs_rl_punch_nolock()
1801 rl->length = rl[1].vcn - start; in ntfs_rl_punch_nolock()
1809 * problem by truncating the run @start is in to end at @start - 1. in ntfs_rl_punch_nolock()
1811 * run followed by a non-sparse run (already covered above) and if @end in ntfs_rl_punch_nolock()
1822 rl->length = start - rl->vcn; in ntfs_rl_punch_nolock()
1824 rl->vcn = start; in ntfs_rl_punch_nolock()
1825 rl->lcn = LCN_HOLE; in ntfs_rl_punch_nolock()
1828 trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1); in ntfs_rl_punch_nolock()
1832 if (runlist->rl != trl) { in ntfs_rl_punch_nolock()
1833 rl = trl + (rl - runlist->rl); in ntfs_rl_punch_nolock()
1834 rl_end = trl + (rl_end - runlist->rl); in ntfs_rl_punch_nolock()
1835 rl_real_end = trl + (rl_real_end - runlist->rl); in ntfs_rl_punch_nolock()
1836 runlist->rl = trl; in ntfs_rl_punch_nolock()
1839 rl->length = start - rl->vcn; in ntfs_rl_punch_nolock()
1846 delta = rl->vcn - start; in ntfs_rl_punch_nolock()
1847 rl->vcn = start; in ntfs_rl_punch_nolock()
1848 if (rl->lcn >= 0) { in ntfs_rl_punch_nolock()
1849 rl->lcn -= delta; in ntfs_rl_punch_nolock()
1853 rl->length += delta; in ntfs_rl_punch_nolock()
1858 * We need to split the run into three. One run for the non-sparse in ntfs_rl_punch_nolock()
1861 * non-sparse region, i.e. between @end and the end of the old run. in ntfs_rl_punch_nolock()
1863 trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 2); in ntfs_rl_punch_nolock()
1867 if (runlist->rl != trl) { in ntfs_rl_punch_nolock()
1868 rl = trl + (rl - runlist->rl); in ntfs_rl_punch_nolock()
1869 rl_end = trl + (rl_end - runlist->rl); in ntfs_rl_punch_nolock()
1870 rl_real_end = trl + (rl_real_end - runlist->rl); in ntfs_rl_punch_nolock()
1871 runlist->rl = trl; in ntfs_rl_punch_nolock()
1873 /* Shift all the runs up by two. */ in ntfs_rl_punch_nolock()
1874 memmove(rl + 2, rl, (rl_real_end - rl + 1) * sizeof(*rl)); in ntfs_rl_punch_nolock()
1875 /* Finally, setup the three split runs. */ in ntfs_rl_punch_nolock()
1876 rl->length = start - rl->vcn; in ntfs_rl_punch_nolock()
1878 rl->vcn = start; in ntfs_rl_punch_nolock()
1879 rl->lcn = LCN_HOLE; in ntfs_rl_punch_nolock()
1880 rl->length = length; in ntfs_rl_punch_nolock()
1882 delta = end - rl->vcn; in ntfs_rl_punch_nolock()
1883 rl->vcn = end; in ntfs_rl_punch_nolock()
1884 rl->lcn += delta; in ntfs_rl_punch_nolock()
1885 rl->length -= delta; in ntfs_rl_punch_nolock()
1889 ntfs_error(vol->sb, "Not enough memory to extend runlist buffer."); in ntfs_rl_punch_nolock()
1890 return -ENOMEM; in ntfs_rl_punch_nolock()