^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0-or-later
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * runlist.c - NTFS runlist handling code. Part of the Linux-NTFS project.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Copyright (c) 2001-2007 Anton Altaparmakov
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * Copyright (c) 2002-2005 Richard Russon
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #include "debug.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) #include "dir.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) #include "endian.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) #include "malloc.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) #include "ntfs.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * ntfs_rl_mm - runlist memmove
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) * It is up to the caller to serialize access to the runlist @base.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) static inline void ntfs_rl_mm(runlist_element *base, int dst, int src,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) int size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) if (likely((dst != src) && (size > 0)))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) memmove(base + dst, base + src, size * sizeof(*base));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) * ntfs_rl_mc - runlist memory copy
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) * It is up to the caller to serialize access to the runlists @dstbase and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) * @srcbase.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) static inline void ntfs_rl_mc(runlist_element *dstbase, int dst,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) runlist_element *srcbase, int src, int size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) if (likely(size > 0))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) memcpy(dstbase + dst, srcbase + src, size * sizeof(*dstbase));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) * ntfs_rl_realloc - Reallocate memory for runlists
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) * @rl: original runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) * @old_size: number of runlist elements in the original runlist @rl
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) * @new_size: number of runlist elements we need space for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) * As the runlists grow, more memory will be required. To prevent the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) * kernel having to allocate and reallocate large numbers of small bits of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) * memory, this function returns an entire page of memory.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) * It is up to the caller to serialize access to the runlist @rl.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) * N.B. If the new allocation doesn't require a different number of pages in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) * memory, the function will return the original pointer.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) * On success, return a pointer to the newly allocated, or recycled, memory.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) * On error, return -errno. The following error codes are defined:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) * -ENOMEM - Not enough memory to allocate runlist array.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) * -EINVAL - Invalid parameters were passed in.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) static inline runlist_element *ntfs_rl_realloc(runlist_element *rl,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) int old_size, int new_size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) runlist_element *new_rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) old_size = PAGE_ALIGN(old_size * sizeof(*rl));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) new_size = PAGE_ALIGN(new_size * sizeof(*rl));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) if (old_size == new_size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) return rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) new_rl = ntfs_malloc_nofs(new_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) if (unlikely(!new_rl))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) return ERR_PTR(-ENOMEM);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) if (likely(rl != NULL)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) if (unlikely(old_size > new_size))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) old_size = new_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) memcpy(new_rl, rl, old_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) ntfs_free(rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) return new_rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) * ntfs_rl_realloc_nofail - Reallocate memory for runlists
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) * @rl: original runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) * @old_size: number of runlist elements in the original runlist @rl
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) * @new_size: number of runlist elements we need space for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) * As the runlists grow, more memory will be required. To prevent the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) * kernel having to allocate and reallocate large numbers of small bits of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) * memory, this function returns an entire page of memory.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) * This function guarantees that the allocation will succeed. It will sleep
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) * for as long as it takes to complete the allocation.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) * It is up to the caller to serialize access to the runlist @rl.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) * N.B. If the new allocation doesn't require a different number of pages in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) * memory, the function will return the original pointer.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) * On success, return a pointer to the newly allocated, or recycled, memory.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) * On error, return -errno. The following error codes are defined:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) * -ENOMEM - Not enough memory to allocate runlist array.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) * -EINVAL - Invalid parameters were passed in.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) static inline runlist_element *ntfs_rl_realloc_nofail(runlist_element *rl,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) int old_size, int new_size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) runlist_element *new_rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) old_size = PAGE_ALIGN(old_size * sizeof(*rl));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) new_size = PAGE_ALIGN(new_size * sizeof(*rl));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) if (old_size == new_size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) return rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) new_rl = ntfs_malloc_nofs_nofail(new_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) BUG_ON(!new_rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) if (likely(rl != NULL)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) if (unlikely(old_size > new_size))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) old_size = new_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) memcpy(new_rl, rl, old_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) ntfs_free(rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) return new_rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) * ntfs_are_rl_mergeable - test if two runlists can be joined together
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) * @dst: original runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) * @src: new runlist to test for mergeability with @dst
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) * Test if two runlists can be joined together. For this, their VCNs and LCNs
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) * must be adjacent.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) * It is up to the caller to serialize access to the runlists @dst and @src.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) * Return: true Success, the runlists can be merged.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) * false Failure, the runlists cannot be merged.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) static inline bool ntfs_are_rl_mergeable(runlist_element *dst,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) runlist_element *src)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) BUG_ON(!dst);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) BUG_ON(!src);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) /* We can merge unmapped regions even if they are misaligned. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) if ((dst->lcn == LCN_RL_NOT_MAPPED) && (src->lcn == LCN_RL_NOT_MAPPED))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) /* If the runs are misaligned, we cannot merge them. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) if ((dst->vcn + dst->length) != src->vcn)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) /* If both runs are non-sparse and contiguous, we can merge them. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) if ((dst->lcn >= 0) && (src->lcn >= 0) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) ((dst->lcn + dst->length) == src->lcn))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) /* If we are merging two holes, we can merge them. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) if ((dst->lcn == LCN_HOLE) && (src->lcn == LCN_HOLE))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) /* Cannot merge. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) * __ntfs_rl_merge - merge two runlists without testing if they can be merged
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) * @dst: original, destination runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) * @src: new runlist to merge with @dst
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) * Merge the two runlists, writing into the destination runlist @dst. The
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) * caller must make sure the runlists can be merged or this will corrupt the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) * destination runlist.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) * It is up to the caller to serialize access to the runlists @dst and @src.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) static inline void __ntfs_rl_merge(runlist_element *dst, runlist_element *src)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) dst->length += src->length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) * ntfs_rl_append - append a runlist after a given element
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) * @dst: original runlist to be worked on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) * @dsize: number of elements in @dst (including end marker)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) * @src: runlist to be inserted into @dst
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) * @ssize: number of elements in @src (excluding end marker)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) * @loc: append the new runlist @src after this element in @dst
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) * Append the runlist @src after element @loc in @dst. Merge the right end of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) * the new runlist, if necessary. Adjust the size of the hole before the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) * appended runlist.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) * It is up to the caller to serialize access to the runlists @dst and @src.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) * On success, return a pointer to the new, combined, runlist. Note, both
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) * runlists @dst and @src are deallocated before returning so you cannot use
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) * the pointers for anything any more. (Strictly speaking the returned runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) * may be the same as @dst but this is irrelevant.)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) * On error, return -errno. Both runlists are left unmodified. The following
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) * error codes are defined:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) * -ENOMEM - Not enough memory to allocate runlist array.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) * -EINVAL - Invalid parameters were passed in.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) static inline runlist_element *ntfs_rl_append(runlist_element *dst,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) int dsize, runlist_element *src, int ssize, int loc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) bool right = false; /* Right end of @src needs merging. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) int marker; /* End of the inserted runs. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) BUG_ON(!dst);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) BUG_ON(!src);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) /* First, check if the right hand end needs merging. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) if ((loc + 1) < dsize)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) /* Space required: @dst size + @src size, less one if we merged. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - right);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) if (IS_ERR(dst))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) return dst;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) * We are guaranteed to succeed from here so can start modifying the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) * original runlists.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) /* First, merge the right hand end, if necessary. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) if (right)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) /* First run after the @src runs that have been inserted. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) marker = loc + ssize + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) /* Move the tail of @dst out of the way, then copy in @src. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) ntfs_rl_mm(dst, marker, loc + 1 + right, dsize - (loc + 1 + right));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) /* Adjust the size of the preceding hole. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) /* We may have changed the length of the file, so fix the end marker */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) if (dst[marker].lcn == LCN_ENOENT)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) return dst;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) * ntfs_rl_insert - insert a runlist into another
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) * @dst: original runlist to be worked on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) * @dsize: number of elements in @dst (including end marker)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) * @src: new runlist to be inserted
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) * @ssize: number of elements in @src (excluding end marker)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) * @loc: insert the new runlist @src before this element in @dst
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) * Insert the runlist @src before element @loc in the runlist @dst. Merge the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) * left end of the new runlist, if necessary. Adjust the size of the hole
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) * after the inserted runlist.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) * It is up to the caller to serialize access to the runlists @dst and @src.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) * On success, return a pointer to the new, combined, runlist. Note, both
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) * runlists @dst and @src are deallocated before returning so you cannot use
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) * the pointers for anything any more. (Strictly speaking the returned runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) * may be the same as @dst but this is irrelevant.)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) * On error, return -errno. Both runlists are left unmodified. The following
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) * error codes are defined:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) * -ENOMEM - Not enough memory to allocate runlist array.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) * -EINVAL - Invalid parameters were passed in.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) static inline runlist_element *ntfs_rl_insert(runlist_element *dst,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) int dsize, runlist_element *src, int ssize, int loc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) bool left = false; /* Left end of @src needs merging. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) bool disc = false; /* Discontinuity between @dst and @src. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) int marker; /* End of the inserted runs. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) BUG_ON(!dst);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) BUG_ON(!src);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) * disc => Discontinuity between the end of @dst and the start of @src.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) * This means we might need to insert a "not mapped" run.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) if (loc == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) disc = (src[0].vcn > 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) s64 merged_length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) left = ntfs_are_rl_mergeable(dst + loc - 1, src);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) merged_length = dst[loc - 1].length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) if (left)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) merged_length += src->length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) disc = (src[0].vcn > dst[loc - 1].vcn + merged_length);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) * Space required: @dst size + @src size, less one if we merged, plus
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) * one if there was a discontinuity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left + disc);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) if (IS_ERR(dst))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) return dst;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) * We are guaranteed to succeed from here so can start modifying the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) * original runlist.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) if (left)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) __ntfs_rl_merge(dst + loc - 1, src);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) * First run after the @src runs that have been inserted.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) * Nominally, @marker equals @loc + @ssize, i.e. location + number of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) * runs in @src. However, if @left, then the first run in @src has
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) * been merged with one in @dst. And if @disc, then @dst and @src do
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) * not meet and we need an extra run to fill the gap.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) marker = loc + ssize - left + disc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) /* Move the tail of @dst out of the way, then copy in @src. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) ntfs_rl_mm(dst, marker, loc, dsize - loc);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) ntfs_rl_mc(dst, loc + disc, src, left, ssize - left);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) /* Adjust the VCN of the first run after the insertion... */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) /* ... and the length. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) if (dst[marker].lcn == LCN_HOLE || dst[marker].lcn == LCN_RL_NOT_MAPPED)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) dst[marker].length = dst[marker + 1].vcn - dst[marker].vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) /* Writing beyond the end of the file and there is a discontinuity. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) if (disc) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) if (loc > 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) dst[loc].vcn = dst[loc - 1].vcn + dst[loc - 1].length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) dst[loc].vcn = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) dst[loc].length = dst[loc + 1].vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) dst[loc].lcn = LCN_RL_NOT_MAPPED;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) return dst;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) * ntfs_rl_replace - overwrite a runlist element with another runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) * @dst: original runlist to be worked on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) * @dsize: number of elements in @dst (including end marker)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) * @src: new runlist to be inserted
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) * @ssize: number of elements in @src (excluding end marker)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) * @loc: index in runlist @dst to overwrite with @src
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) * Replace the runlist element @dst at @loc with @src. Merge the left and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) * right ends of the inserted runlist, if necessary.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) * It is up to the caller to serialize access to the runlists @dst and @src.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) * On success, return a pointer to the new, combined, runlist. Note, both
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) * runlists @dst and @src are deallocated before returning so you cannot use
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) * the pointers for anything any more. (Strictly speaking the returned runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) * may be the same as @dst but this is irrelevant.)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) * On error, return -errno. Both runlists are left unmodified. The following
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) * error codes are defined:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) * -ENOMEM - Not enough memory to allocate runlist array.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) * -EINVAL - Invalid parameters were passed in.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) static inline runlist_element *ntfs_rl_replace(runlist_element *dst,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) int dsize, runlist_element *src, int ssize, int loc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) signed delta;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) bool left = false; /* Left end of @src needs merging. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) bool right = false; /* Right end of @src needs merging. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) int tail; /* Start of tail of @dst. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) int marker; /* End of the inserted runs. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) BUG_ON(!dst);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) BUG_ON(!src);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) /* First, see if the left and right ends need merging. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) if ((loc + 1) < dsize)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) if (loc > 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383) left = ntfs_are_rl_mergeable(dst + loc - 1, src);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) * Allocate some space. We will need less if the left, right, or both
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) * ends get merged. The -1 accounts for the run being replaced.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) delta = ssize - 1 - left - right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) if (delta > 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) dst = ntfs_rl_realloc(dst, dsize, dsize + delta);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) if (IS_ERR(dst))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392) return dst;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) * We are guaranteed to succeed from here so can start modifying the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) * original runlists.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) /* First, merge the left and right ends, if necessary. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) if (right)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) if (left)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) __ntfs_rl_merge(dst + loc - 1, src);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) * Offset of the tail of @dst. This needs to be moved out of the way
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) * to make space for the runs to be copied from @src, i.e. the first
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) * run of the tail of @dst.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) * Nominally, @tail equals @loc + 1, i.e. location, skipping the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) * replaced run. However, if @right, then one of @dst's runs is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) * already merged into @src.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) tail = loc + right + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) * First run after the @src runs that have been inserted, i.e. where
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) * the tail of @dst needs to be moved to.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) * Nominally, @marker equals @loc + @ssize, i.e. location + number of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) * runs in @src. However, if @left, then the first run in @src has
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) * been merged with one in @dst.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) marker = loc + ssize - left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) /* Move the tail of @dst out of the way, then copy in @src. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) ntfs_rl_mm(dst, marker, tail, dsize - tail);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) ntfs_rl_mc(dst, loc, src, left, ssize - left);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) /* We may have changed the length of the file, so fix the end marker. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) if (dsize - tail > 0 && dst[marker].lcn == LCN_ENOENT)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) return dst;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) * ntfs_rl_split - insert a runlist into the centre of a hole
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434) * @dst: original runlist to be worked on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) * @dsize: number of elements in @dst (including end marker)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) * @src: new runlist to be inserted
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) * @ssize: number of elements in @src (excluding end marker)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) * @loc: index in runlist @dst at which to split and insert @src
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) * Split the runlist @dst at @loc into two and insert @new in between the two
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441) * fragments. No merging of runlists is necessary. Adjust the size of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) * holes either side.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) * It is up to the caller to serialize access to the runlists @dst and @src.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) * On success, return a pointer to the new, combined, runlist. Note, both
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) * runlists @dst and @src are deallocated before returning so you cannot use
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) * the pointers for anything any more. (Strictly speaking the returned runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) * may be the same as @dst but this is irrelevant.)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451) * On error, return -errno. Both runlists are left unmodified. The following
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) * error codes are defined:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) * -ENOMEM - Not enough memory to allocate runlist array.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) * -EINVAL - Invalid parameters were passed in.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) static inline runlist_element *ntfs_rl_split(runlist_element *dst, int dsize,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) runlist_element *src, int ssize, int loc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) BUG_ON(!dst);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460) BUG_ON(!src);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) /* Space required: @dst size + @src size + one new hole. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) dst = ntfs_rl_realloc(dst, dsize, dsize + ssize + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) if (IS_ERR(dst))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) return dst;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) * We are guaranteed to succeed from here so can start modifying the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) * original runlists.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) /* Move the tail of @dst out of the way, then copy in @src. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) ntfs_rl_mm(dst, loc + 1 + ssize, loc, dsize - loc);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473) ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) /* Adjust the size of the holes either size of @src. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) dst[loc].length = dst[loc+1].vcn - dst[loc].vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) dst[loc+ssize+1].vcn = dst[loc+ssize].vcn + dst[loc+ssize].length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478) dst[loc+ssize+1].length = dst[loc+ssize+2].vcn - dst[loc+ssize+1].vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) return dst;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) * ntfs_runlists_merge - merge two runlists into one
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) * @drl: original runlist to be worked on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) * @srl: new runlist to be merged into @drl
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) * First we sanity check the two runlists @srl and @drl to make sure that they
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) * are sensible and can be merged. The runlist @srl must be either after the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490) * runlist @drl or completely within a hole (or unmapped region) in @drl.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) * It is up to the caller to serialize access to the runlists @drl and @srl.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) * Merging of runlists is necessary in two cases:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) * 1. When attribute lists are used and a further extent is being mapped.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) * 2. When new clusters are allocated to fill a hole or extend a file.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) * There are four possible ways @srl can be merged. It can:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499) * - be inserted at the beginning of a hole,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) * - split the hole in two and be inserted between the two fragments,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501) * - be appended at the end of a hole, or it can
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) * - replace the whole hole.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) * It can also be appended to the end of the runlist, which is just a variant
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504) * of the insert case.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506) * On success, return a pointer to the new, combined, runlist. Note, both
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) * runlists @drl and @srl are deallocated before returning so you cannot use
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508) * the pointers for anything any more. (Strictly speaking the returned runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509) * may be the same as @dst but this is irrelevant.)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511) * On error, return -errno. Both runlists are left unmodified. The following
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) * error codes are defined:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513) * -ENOMEM - Not enough memory to allocate runlist array.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514) * -EINVAL - Invalid parameters were passed in.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) * -ERANGE - The runlists overlap and cannot be merged.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) runlist_element *ntfs_runlists_merge(runlist_element *drl,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518) runlist_element *srl)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) int di, si; /* Current index into @[ds]rl. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521) int sstart; /* First index with lcn > LCN_RL_NOT_MAPPED. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522) int dins; /* Index into @drl at which to insert @srl. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) int dend, send; /* Last index into @[ds]rl. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) int dfinal, sfinal; /* The last index into @[ds]rl with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) lcn >= LCN_HOLE. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526) int marker = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527) VCN marker_vcn = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529) #ifdef DEBUG
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) ntfs_debug("dst:");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531) ntfs_debug_dump_runlist(drl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532) ntfs_debug("src:");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533) ntfs_debug_dump_runlist(srl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) /* Check for silly calling... */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537) if (unlikely(!srl))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538) return drl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539) if (IS_ERR(srl) || IS_ERR(drl))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540) return ERR_PTR(-EINVAL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) /* Check for the case where the first mapping is being done now. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) if (unlikely(!drl)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) drl = srl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545) /* Complete the source runlist if necessary. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) if (unlikely(drl[0].vcn)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547) /* Scan to the end of the source runlist. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) for (dend = 0; likely(drl[dend].length); dend++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549) ;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550) dend++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551) drl = ntfs_rl_realloc(drl, dend, dend + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552) if (IS_ERR(drl))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553) return drl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) /* Insert start element at the front of the runlist. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555) ntfs_rl_mm(drl, 1, 0, dend);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) drl[0].vcn = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) drl[0].lcn = LCN_RL_NOT_MAPPED;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558) drl[0].length = drl[1].vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) goto finished;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563) si = di = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565) /* Skip any unmapped start element(s) in the source runlist. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566) while (srl[si].length && srl[si].lcn < LCN_HOLE)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) si++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569) /* Can't have an entirely unmapped source runlist. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570) BUG_ON(!srl[si].length);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572) /* Record the starting points. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573) sstart = si;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) * Skip forward in @drl until we reach the position where @srl needs to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577) * be inserted. If we reach the end of @drl, @srl just needs to be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578) * appended to @drl.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580) for (; drl[di].length; di++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581) if (drl[di].vcn + drl[di].length > srl[sstart].vcn)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584) dins = di;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586) /* Sanity check for illegal overlaps. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587) if ((drl[di].vcn == srl[si].vcn) && (drl[di].lcn >= 0) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588) (srl[si].lcn >= 0)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) ntfs_error(NULL, "Run lists overlap. Cannot merge!");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590) return ERR_PTR(-ERANGE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593) /* Scan to the end of both runlists in order to know their sizes. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 594) for (send = si; srl[send].length; send++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 595) ;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 596) for (dend = di; drl[dend].length; dend++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 597) ;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 598)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 599) if (srl[send].lcn == LCN_ENOENT)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 600) marker_vcn = srl[marker = send].vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 601)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 602) /* Scan to the last element with lcn >= LCN_HOLE. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 603) for (sfinal = send; sfinal >= 0 && srl[sfinal].lcn < LCN_HOLE; sfinal--)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 604) ;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 605) for (dfinal = dend; dfinal >= 0 && drl[dfinal].lcn < LCN_HOLE; dfinal--)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 606) ;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 607)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 608) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 609) bool start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 610) bool finish;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 611) int ds = dend + 1; /* Number of elements in drl & srl */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 612) int ss = sfinal - sstart + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 613)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 614) start = ((drl[dins].lcn < LCN_RL_NOT_MAPPED) || /* End of file */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 615) (drl[dins].vcn == srl[sstart].vcn)); /* Start of hole */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 616) finish = ((drl[dins].lcn >= LCN_RL_NOT_MAPPED) && /* End of file */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 617) ((drl[dins].vcn + drl[dins].length) <= /* End of hole */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 618) (srl[send - 1].vcn + srl[send - 1].length)));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 619)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 620) /* Or we will lose an end marker. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 621) if (finish && !drl[dins].length)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 622) ss++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 623) if (marker && (drl[dins].vcn + drl[dins].length > srl[send - 1].vcn))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 624) finish = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 625) #if 0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 626) ntfs_debug("dfinal = %i, dend = %i", dfinal, dend);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 627) ntfs_debug("sstart = %i, sfinal = %i, send = %i", sstart, sfinal, send);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 628) ntfs_debug("start = %i, finish = %i", start, finish);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 629) ntfs_debug("ds = %i, ss = %i, dins = %i", ds, ss, dins);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 630) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 631) if (start) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 632) if (finish)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 633) drl = ntfs_rl_replace(drl, ds, srl + sstart, ss, dins);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 634) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 635) drl = ntfs_rl_insert(drl, ds, srl + sstart, ss, dins);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 636) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 637) if (finish)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 638) drl = ntfs_rl_append(drl, ds, srl + sstart, ss, dins);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 639) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 640) drl = ntfs_rl_split(drl, ds, srl + sstart, ss, dins);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 641) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 642) if (IS_ERR(drl)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 643) ntfs_error(NULL, "Merge failed.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 644) return drl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 645) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 646) ntfs_free(srl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 647) if (marker) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 648) ntfs_debug("Triggering marker code.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 649) for (ds = dend; drl[ds].length; ds++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 650) ;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 651) /* We only need to care if @srl ended after @drl. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 652) if (drl[ds].vcn <= marker_vcn) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 653) int slots = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 654)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 655) if (drl[ds].vcn == marker_vcn) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 656) ntfs_debug("Old marker = 0x%llx, replacing "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 657) "with LCN_ENOENT.",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 658) (unsigned long long)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 659) drl[ds].lcn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 660) drl[ds].lcn = LCN_ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 661) goto finished;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 662) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 663) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 664) * We need to create an unmapped runlist element in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 665) * @drl or extend an existing one before adding the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 666) * ENOENT terminator.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 667) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 668) if (drl[ds].lcn == LCN_ENOENT) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 669) ds--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 670) slots = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 671) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 672) if (drl[ds].lcn != LCN_RL_NOT_MAPPED) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 673) /* Add an unmapped runlist element. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 674) if (!slots) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 675) drl = ntfs_rl_realloc_nofail(drl, ds,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 676) ds + 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 677) slots = 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 678) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 679) ds++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 680) /* Need to set vcn if it isn't set already. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 681) if (slots != 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 682) drl[ds].vcn = drl[ds - 1].vcn +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 683) drl[ds - 1].length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 684) drl[ds].lcn = LCN_RL_NOT_MAPPED;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 685) /* We now used up a slot. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 686) slots--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 687) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 688) drl[ds].length = marker_vcn - drl[ds].vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 689) /* Finally add the ENOENT terminator. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 690) ds++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 691) if (!slots)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 692) drl = ntfs_rl_realloc_nofail(drl, ds, ds + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 693) drl[ds].vcn = marker_vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 694) drl[ds].lcn = LCN_ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 695) drl[ds].length = (s64)0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 696) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 697) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 698) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 699)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 700) finished:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 701) /* The merge was completed successfully. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 702) ntfs_debug("Merged runlist:");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 703) ntfs_debug_dump_runlist(drl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 704) return drl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 705) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 706)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 707) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 708) * ntfs_mapping_pairs_decompress - convert mapping pairs array to runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 709) * @vol: ntfs volume on which the attribute resides
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 710) * @attr: attribute record whose mapping pairs array to decompress
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 711) * @old_rl: optional runlist in which to insert @attr's runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 712) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 713) * It is up to the caller to serialize access to the runlist @old_rl.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 714) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 715) * Decompress the attribute @attr's mapping pairs array into a runlist. On
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 716) * success, return the decompressed runlist.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 717) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 718) * If @old_rl is not NULL, decompressed runlist is inserted into the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 719) * appropriate place in @old_rl and the resultant, combined runlist is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 720) * returned. The original @old_rl is deallocated.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 721) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 722) * On error, return -errno. @old_rl is left unmodified in that case.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 723) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 724) * The following error codes are defined:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 725) * -ENOMEM - Not enough memory to allocate runlist array.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 726) * -EIO - Corrupt runlist.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 727) * -EINVAL - Invalid parameters were passed in.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 728) * -ERANGE - The two runlists overlap.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 729) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 730) * FIXME: For now we take the conceptionally simplest approach of creating the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 731) * new runlist disregarding the already existing one and then splicing the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 732) * two into one, if that is possible (we check for overlap and discard the new
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 733) * runlist if overlap present before returning ERR_PTR(-ERANGE)).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 734) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 735) runlist_element *ntfs_mapping_pairs_decompress(const ntfs_volume *vol,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 736) const ATTR_RECORD *attr, runlist_element *old_rl)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 737) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 738) VCN vcn; /* Current vcn. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 739) LCN lcn; /* Current lcn. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 740) s64 deltaxcn; /* Change in [vl]cn. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 741) runlist_element *rl; /* The output runlist. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 742) u8 *buf; /* Current position in mapping pairs array. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 743) u8 *attr_end; /* End of attribute. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 744) int rlsize; /* Size of runlist buffer. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 745) u16 rlpos; /* Current runlist position in units of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 746) runlist_elements. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 747) u8 b; /* Current byte offset in buf. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 748)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 749) #ifdef DEBUG
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 750) /* Make sure attr exists and is non-resident. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 751) if (!attr || !attr->non_resident || sle64_to_cpu(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 752) attr->data.non_resident.lowest_vcn) < (VCN)0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 753) ntfs_error(vol->sb, "Invalid arguments.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 754) return ERR_PTR(-EINVAL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 755) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 756) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 757) /* Start at vcn = lowest_vcn and lcn 0. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 758) vcn = sle64_to_cpu(attr->data.non_resident.lowest_vcn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 759) lcn = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 760) /* Get start of the mapping pairs array. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 761) buf = (u8*)attr + le16_to_cpu(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 762) attr->data.non_resident.mapping_pairs_offset);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 763) attr_end = (u8*)attr + le32_to_cpu(attr->length);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 764) if (unlikely(buf < (u8*)attr || buf > attr_end)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 765) ntfs_error(vol->sb, "Corrupt attribute.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 766) return ERR_PTR(-EIO);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 767) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 768) /* If the mapping pairs array is valid but empty, nothing to do. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 769) if (!vcn && !*buf)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 770) return old_rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 771) /* Current position in runlist array. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 772) rlpos = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 773) /* Allocate first page and set current runlist size to one page. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 774) rl = ntfs_malloc_nofs(rlsize = PAGE_SIZE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 775) if (unlikely(!rl))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 776) return ERR_PTR(-ENOMEM);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 777) /* Insert unmapped starting element if necessary. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 778) if (vcn) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 779) rl->vcn = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 780) rl->lcn = LCN_RL_NOT_MAPPED;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 781) rl->length = vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 782) rlpos++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 783) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 784) while (buf < attr_end && *buf) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 785) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 786) * Allocate more memory if needed, including space for the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 787) * not-mapped and terminator elements. ntfs_malloc_nofs()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 788) * operates on whole pages only.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 789) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 790) if (((rlpos + 3) * sizeof(*old_rl)) > rlsize) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 791) runlist_element *rl2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 792)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 793) rl2 = ntfs_malloc_nofs(rlsize + (int)PAGE_SIZE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 794) if (unlikely(!rl2)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 795) ntfs_free(rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 796) return ERR_PTR(-ENOMEM);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 797) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 798) memcpy(rl2, rl, rlsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 799) ntfs_free(rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 800) rl = rl2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 801) rlsize += PAGE_SIZE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 802) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 803) /* Enter the current vcn into the current runlist element. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 804) rl[rlpos].vcn = vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 805) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 806) * Get the change in vcn, i.e. the run length in clusters.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 807) * Doing it this way ensures that we signextend negative values.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 808) * A negative run length doesn't make any sense, but hey, I
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 809) * didn't make up the NTFS specs and Windows NT4 treats the run
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 810) * length as a signed value so that's how it is...
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 811) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 812) b = *buf & 0xf;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 813) if (b) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 814) if (unlikely(buf + b > attr_end))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 815) goto io_error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 816) for (deltaxcn = (s8)buf[b--]; b; b--)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 817) deltaxcn = (deltaxcn << 8) + buf[b];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 818) } else { /* The length entry is compulsory. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 819) ntfs_error(vol->sb, "Missing length entry in mapping "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 820) "pairs array.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 821) deltaxcn = (s64)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 822) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 823) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 824) * Assume a negative length to indicate data corruption and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 825) * hence clean-up and return NULL.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 826) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 827) if (unlikely(deltaxcn < 0)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 828) ntfs_error(vol->sb, "Invalid length in mapping pairs "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 829) "array.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 830) goto err_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 831) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 832) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 833) * Enter the current run length into the current runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 834) * element.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 835) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 836) rl[rlpos].length = deltaxcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 837) /* Increment the current vcn by the current run length. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 838) vcn += deltaxcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 839) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 840) * There might be no lcn change at all, as is the case for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 841) * sparse clusters on NTFS 3.0+, in which case we set the lcn
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 842) * to LCN_HOLE.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 843) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 844) if (!(*buf & 0xf0))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 845) rl[rlpos].lcn = LCN_HOLE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 846) else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 847) /* Get the lcn change which really can be negative. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 848) u8 b2 = *buf & 0xf;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 849) b = b2 + ((*buf >> 4) & 0xf);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 850) if (buf + b > attr_end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 851) goto io_error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 852) for (deltaxcn = (s8)buf[b--]; b > b2; b--)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 853) deltaxcn = (deltaxcn << 8) + buf[b];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 854) /* Change the current lcn to its new value. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 855) lcn += deltaxcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 856) #ifdef DEBUG
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 857) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 858) * On NTFS 1.2-, apparently can have lcn == -1 to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 859) * indicate a hole. But we haven't verified ourselves
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 860) * whether it is really the lcn or the deltaxcn that is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 861) * -1. So if either is found give us a message so we
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 862) * can investigate it further!
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 863) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 864) if (vol->major_ver < 3) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 865) if (unlikely(deltaxcn == (LCN)-1))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 866) ntfs_error(vol->sb, "lcn delta == -1");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 867) if (unlikely(lcn == (LCN)-1))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 868) ntfs_error(vol->sb, "lcn == -1");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 869) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 870) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 871) /* Check lcn is not below -1. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 872) if (unlikely(lcn < (LCN)-1)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 873) ntfs_error(vol->sb, "Invalid LCN < -1 in "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 874) "mapping pairs array.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 875) goto err_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 876) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 877) /* Enter the current lcn into the runlist element. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 878) rl[rlpos].lcn = lcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 879) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 880) /* Get to the next runlist element. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 881) rlpos++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 882) /* Increment the buffer position to the next mapping pair. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 883) buf += (*buf & 0xf) + ((*buf >> 4) & 0xf) + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 884) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 885) if (unlikely(buf >= attr_end))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 886) goto io_error;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 887) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 888) * If there is a highest_vcn specified, it must be equal to the final
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 889) * vcn in the runlist - 1, or something has gone badly wrong.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 890) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 891) deltaxcn = sle64_to_cpu(attr->data.non_resident.highest_vcn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 892) if (unlikely(deltaxcn && vcn - 1 != deltaxcn)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 893) mpa_err:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 894) ntfs_error(vol->sb, "Corrupt mapping pairs array in "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 895) "non-resident attribute.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 896) goto err_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 897) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 898) /* Setup not mapped runlist element if this is the base extent. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 899) if (!attr->data.non_resident.lowest_vcn) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 900) VCN max_cluster;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 901)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 902) max_cluster = ((sle64_to_cpu(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 903) attr->data.non_resident.allocated_size) +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 904) vol->cluster_size - 1) >>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 905) vol->cluster_size_bits) - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 906) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 907) * A highest_vcn of zero means this is a single extent
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 908) * attribute so simply terminate the runlist with LCN_ENOENT).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 909) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 910) if (deltaxcn) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 911) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 912) * If there is a difference between the highest_vcn and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 913) * the highest cluster, the runlist is either corrupt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 914) * or, more likely, there are more extents following
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 915) * this one.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 916) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 917) if (deltaxcn < max_cluster) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 918) ntfs_debug("More extents to follow; deltaxcn "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 919) "= 0x%llx, max_cluster = "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 920) "0x%llx",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 921) (unsigned long long)deltaxcn,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 922) (unsigned long long)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 923) max_cluster);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 924) rl[rlpos].vcn = vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 925) vcn += rl[rlpos].length = max_cluster -
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 926) deltaxcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 927) rl[rlpos].lcn = LCN_RL_NOT_MAPPED;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 928) rlpos++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 929) } else if (unlikely(deltaxcn > max_cluster)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 930) ntfs_error(vol->sb, "Corrupt attribute. "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 931) "deltaxcn = 0x%llx, "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 932) "max_cluster = 0x%llx",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 933) (unsigned long long)deltaxcn,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 934) (unsigned long long)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 935) max_cluster);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 936) goto mpa_err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 937) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 938) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 939) rl[rlpos].lcn = LCN_ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 940) } else /* Not the base extent. There may be more extents to follow. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 941) rl[rlpos].lcn = LCN_RL_NOT_MAPPED;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 942)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 943) /* Setup terminating runlist element. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 944) rl[rlpos].vcn = vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 945) rl[rlpos].length = (s64)0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 946) /* If no existing runlist was specified, we are done. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 947) if (!old_rl) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 948) ntfs_debug("Mapping pairs array successfully decompressed:");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 949) ntfs_debug_dump_runlist(rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 950) return rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 951) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 952) /* Now combine the new and old runlists checking for overlaps. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 953) old_rl = ntfs_runlists_merge(old_rl, rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 954) if (!IS_ERR(old_rl))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 955) return old_rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 956) ntfs_free(rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 957) ntfs_error(vol->sb, "Failed to merge runlists.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 958) return old_rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 959) io_error:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 960) ntfs_error(vol->sb, "Corrupt attribute.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 961) err_out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 962) ntfs_free(rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 963) return ERR_PTR(-EIO);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 964) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 965)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 966) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 967) * ntfs_rl_vcn_to_lcn - convert a vcn into a lcn given a runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 968) * @rl: runlist to use for conversion
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 969) * @vcn: vcn to convert
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 970) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 971) * Convert the virtual cluster number @vcn of an attribute into a logical
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 972) * cluster number (lcn) of a device using the runlist @rl to map vcns to their
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 973) * corresponding lcns.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 974) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 975) * It is up to the caller to serialize access to the runlist @rl.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 976) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 977) * Since lcns must be >= 0, we use negative return codes with special meaning:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 978) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 979) * Return code Meaning / Description
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 980) * ==================================================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 981) * LCN_HOLE Hole / not allocated on disk.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 982) * LCN_RL_NOT_MAPPED This is part of the runlist which has not been
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 983) * inserted into the runlist yet.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 984) * LCN_ENOENT There is no such vcn in the attribute.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 985) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 986) * Locking: - The caller must have locked the runlist (for reading or writing).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 987) * - This function does not touch the lock, nor does it modify the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 988) * runlist.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 989) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 990) LCN ntfs_rl_vcn_to_lcn(const runlist_element *rl, const VCN vcn)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 991) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 992) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 993)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 994) BUG_ON(vcn < 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 995) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 996) * If rl is NULL, assume that we have found an unmapped runlist. The
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 997) * caller can then attempt to map it and fail appropriately if
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 998) * necessary.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 999) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1000) if (unlikely(!rl))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1001) return LCN_RL_NOT_MAPPED;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1002)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1003) /* Catch out of lower bounds vcn. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1004) if (unlikely(vcn < rl[0].vcn))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1005) return LCN_ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1006)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1007) for (i = 0; likely(rl[i].length); i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1008) if (unlikely(vcn < rl[i+1].vcn)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1009) if (likely(rl[i].lcn >= (LCN)0))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1010) return rl[i].lcn + (vcn - rl[i].vcn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1011) return rl[i].lcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1012) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1013) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1014) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1015) * The terminator element is setup to the correct value, i.e. one of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1016) * LCN_HOLE, LCN_RL_NOT_MAPPED, or LCN_ENOENT.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1017) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1018) if (likely(rl[i].lcn < (LCN)0))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1019) return rl[i].lcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1020) /* Just in case... We could replace this with BUG() some day. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1021) return LCN_ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1022) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1023)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1024) #ifdef NTFS_RW
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1025)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1026) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1027) * ntfs_rl_find_vcn_nolock - find a vcn in a runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1028) * @rl: runlist to search
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1029) * @vcn: vcn to find
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1030) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1031) * Find the virtual cluster number @vcn in the runlist @rl and return the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1032) * address of the runlist element containing the @vcn on success.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1033) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1034) * Return NULL if @rl is NULL or @vcn is in an unmapped part/out of bounds of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1035) * the runlist.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1036) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1037) * Locking: The runlist must be locked on entry.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1038) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1039) runlist_element *ntfs_rl_find_vcn_nolock(runlist_element *rl, const VCN vcn)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1040) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1041) BUG_ON(vcn < 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1042) if (unlikely(!rl || vcn < rl[0].vcn))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1043) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1044) while (likely(rl->length)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1045) if (unlikely(vcn < rl[1].vcn)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1046) if (likely(rl->lcn >= LCN_HOLE))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1047) return rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1048) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1049) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1050) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1051) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1052) if (likely(rl->lcn == LCN_ENOENT))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1053) return rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1054) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1055) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1056)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1057) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1058) * ntfs_get_nr_significant_bytes - get number of bytes needed to store a number
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1059) * @n: number for which to get the number of bytes for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1060) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1061) * Return the number of bytes required to store @n unambiguously as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1062) * a signed number.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1063) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1064) * This is used in the context of the mapping pairs array to determine how
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1065) * many bytes will be needed in the array to store a given logical cluster
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1066) * number (lcn) or a specific run length.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1067) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1068) * Return the number of bytes written. This function cannot fail.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1069) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1070) static inline int ntfs_get_nr_significant_bytes(const s64 n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1071) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1072) s64 l = n;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1073) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1074) s8 j;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1075)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1076) i = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1077) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1078) l >>= 8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1079) i++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1080) } while (l != 0 && l != -1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1081) j = (n >> 8 * (i - 1)) & 0xff;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1082) /* If the sign bit is wrong, we need an extra byte. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1083) if ((n < 0 && j >= 0) || (n > 0 && j < 0))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1084) i++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1085) return i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1086) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1087)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1088) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1089) * ntfs_get_size_for_mapping_pairs - get bytes needed for mapping pairs array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1090) * @vol: ntfs volume (needed for the ntfs version)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1091) * @rl: locked runlist to determine the size of the mapping pairs of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1092) * @first_vcn: first vcn which to include in the mapping pairs array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1093) * @last_vcn: last vcn which to include in the mapping pairs array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1094) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1095) * Walk the locked runlist @rl and calculate the size in bytes of the mapping
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1096) * pairs array corresponding to the runlist @rl, starting at vcn @first_vcn and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1097) * finishing with vcn @last_vcn.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1098) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1099) * A @last_vcn of -1 means end of runlist and in that case the size of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1100) * mapping pairs array corresponding to the runlist starting at vcn @first_vcn
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1101) * and finishing at the end of the runlist is determined.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1102) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1103) * This for example allows us to allocate a buffer of the right size when
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1104) * building the mapping pairs array.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1105) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1106) * If @rl is NULL, just return 1 (for the single terminator byte).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1107) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1108) * Return the calculated size in bytes on success. On error, return -errno.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1109) * The following error codes are defined:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1110) * -EINVAL - Run list contains unmapped elements. Make sure to only pass
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1111) * fully mapped runlists to this function.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1112) * -EIO - The runlist is corrupt.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1113) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1114) * Locking: @rl must be locked on entry (either for reading or writing), it
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1115) * remains locked throughout, and is left locked upon return.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1116) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1117) int ntfs_get_size_for_mapping_pairs(const ntfs_volume *vol,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1118) const runlist_element *rl, const VCN first_vcn,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1119) const VCN last_vcn)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1120) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1121) LCN prev_lcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1122) int rls;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1123) bool the_end = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1124)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1125) BUG_ON(first_vcn < 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1126) BUG_ON(last_vcn < -1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1127) BUG_ON(last_vcn >= 0 && first_vcn > last_vcn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1128) if (!rl) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1129) BUG_ON(first_vcn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1130) BUG_ON(last_vcn > 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1131) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1132) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1133) /* Skip to runlist element containing @first_vcn. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1134) while (rl->length && first_vcn >= rl[1].vcn)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1135) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1136) if (unlikely((!rl->length && first_vcn > rl->vcn) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1137) first_vcn < rl->vcn))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1138) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1139) prev_lcn = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1140) /* Always need the termining zero byte. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1141) rls = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1142) /* Do the first partial run if present. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1143) if (first_vcn > rl->vcn) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1144) s64 delta, length = rl->length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1145)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1146) /* We know rl->length != 0 already. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1147) if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1148) goto err_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1149) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1150) * If @stop_vcn is given and finishes inside this run, cap the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1151) * run length.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1152) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1153) if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1154) s64 s1 = last_vcn + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1155) if (unlikely(rl[1].vcn > s1))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1156) length = s1 - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1157) the_end = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1158) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1159) delta = first_vcn - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1160) /* Header byte + length. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1161) rls += 1 + ntfs_get_nr_significant_bytes(length - delta);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1162) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1163) * If the logical cluster number (lcn) denotes a hole and we
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1164) * are on NTFS 3.0+, we don't store it at all, i.e. we need
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1165) * zero space. On earlier NTFS versions we just store the lcn.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1166) * Note: this assumes that on NTFS 1.2-, holes are stored with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1167) * an lcn of -1 and not a delta_lcn of -1 (unless both are -1).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1168) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1169) if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1170) prev_lcn = rl->lcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1171) if (likely(rl->lcn >= 0))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1172) prev_lcn += delta;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1173) /* Change in lcn. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1174) rls += ntfs_get_nr_significant_bytes(prev_lcn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1175) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1176) /* Go to next runlist element. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1177) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1178) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1179) /* Do the full runs. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1180) for (; rl->length && !the_end; rl++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1181) s64 length = rl->length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1182)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1183) if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1184) goto err_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1185) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1186) * If @stop_vcn is given and finishes inside this run, cap the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1187) * run length.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1188) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1189) if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1190) s64 s1 = last_vcn + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1191) if (unlikely(rl[1].vcn > s1))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1192) length = s1 - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1193) the_end = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1194) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1195) /* Header byte + length. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1196) rls += 1 + ntfs_get_nr_significant_bytes(length);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1197) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1198) * If the logical cluster number (lcn) denotes a hole and we
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1199) * are on NTFS 3.0+, we don't store it at all, i.e. we need
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1200) * zero space. On earlier NTFS versions we just store the lcn.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1201) * Note: this assumes that on NTFS 1.2-, holes are stored with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1202) * an lcn of -1 and not a delta_lcn of -1 (unless both are -1).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1203) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1204) if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1205) /* Change in lcn. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1206) rls += ntfs_get_nr_significant_bytes(rl->lcn -
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1207) prev_lcn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1208) prev_lcn = rl->lcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1209) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1210) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1211) return rls;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1212) err_out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1213) if (rl->lcn == LCN_RL_NOT_MAPPED)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1214) rls = -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1215) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1216) rls = -EIO;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1217) return rls;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1218) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1219)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1220) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1221) * ntfs_write_significant_bytes - write the significant bytes of a number
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1222) * @dst: destination buffer to write to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1223) * @dst_max: pointer to last byte of destination buffer for bounds checking
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1224) * @n: number whose significant bytes to write
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1225) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1226) * Store in @dst, the minimum bytes of the number @n which are required to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1227) * identify @n unambiguously as a signed number, taking care not to exceed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1228) * @dest_max, the maximum position within @dst to which we are allowed to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1229) * write.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1230) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1231) * This is used when building the mapping pairs array of a runlist to compress
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1232) * a given logical cluster number (lcn) or a specific run length to the minimum
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1233) * size possible.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1234) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1235) * Return the number of bytes written on success. On error, i.e. the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1236) * destination buffer @dst is too small, return -ENOSPC.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1237) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1238) static inline int ntfs_write_significant_bytes(s8 *dst, const s8 *dst_max,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1239) const s64 n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1240) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1241) s64 l = n;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1242) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1243) s8 j;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1244)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1245) i = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1246) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1247) if (unlikely(dst > dst_max))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1248) goto err_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1249) *dst++ = l & 0xffll;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1250) l >>= 8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1251) i++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1252) } while (l != 0 && l != -1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1253) j = (n >> 8 * (i - 1)) & 0xff;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1254) /* If the sign bit is wrong, we need an extra byte. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1255) if (n < 0 && j >= 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1256) if (unlikely(dst > dst_max))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1257) goto err_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1258) i++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1259) *dst = (s8)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1260) } else if (n > 0 && j < 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1261) if (unlikely(dst > dst_max))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1262) goto err_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1263) i++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1264) *dst = (s8)0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1265) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1266) return i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1267) err_out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1268) return -ENOSPC;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1269) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1270)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1271) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1272) * ntfs_mapping_pairs_build - build the mapping pairs array from a runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1273) * @vol: ntfs volume (needed for the ntfs version)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1274) * @dst: destination buffer to which to write the mapping pairs array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1275) * @dst_len: size of destination buffer @dst in bytes
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1276) * @rl: locked runlist for which to build the mapping pairs array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1277) * @first_vcn: first vcn which to include in the mapping pairs array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1278) * @last_vcn: last vcn which to include in the mapping pairs array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1279) * @stop_vcn: first vcn outside destination buffer on success or -ENOSPC
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1280) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1281) * Create the mapping pairs array from the locked runlist @rl, starting at vcn
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1282) * @first_vcn and finishing with vcn @last_vcn and save the array in @dst.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1283) * @dst_len is the size of @dst in bytes and it should be at least equal to the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1284) * value obtained by calling ntfs_get_size_for_mapping_pairs().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1285) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1286) * A @last_vcn of -1 means end of runlist and in that case the mapping pairs
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1287) * array corresponding to the runlist starting at vcn @first_vcn and finishing
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1288) * at the end of the runlist is created.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1289) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1290) * If @rl is NULL, just write a single terminator byte to @dst.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1291) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1292) * On success or -ENOSPC error, if @stop_vcn is not NULL, *@stop_vcn is set to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1293) * the first vcn outside the destination buffer. Note that on error, @dst has
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1294) * been filled with all the mapping pairs that will fit, thus it can be treated
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1295) * as partial success, in that a new attribute extent needs to be created or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1296) * the next extent has to be used and the mapping pairs build has to be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1297) * continued with @first_vcn set to *@stop_vcn.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1298) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1299) * Return 0 on success and -errno on error. The following error codes are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1300) * defined:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1301) * -EINVAL - Run list contains unmapped elements. Make sure to only pass
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1302) * fully mapped runlists to this function.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1303) * -EIO - The runlist is corrupt.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1304) * -ENOSPC - The destination buffer is too small.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1305) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1306) * Locking: @rl must be locked on entry (either for reading or writing), it
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1307) * remains locked throughout, and is left locked upon return.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1308) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1309) int ntfs_mapping_pairs_build(const ntfs_volume *vol, s8 *dst,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1310) const int dst_len, const runlist_element *rl,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1311) const VCN first_vcn, const VCN last_vcn, VCN *const stop_vcn)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1312) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1313) LCN prev_lcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1314) s8 *dst_max, *dst_next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1315) int err = -ENOSPC;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1316) bool the_end = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1317) s8 len_len, lcn_len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1318)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1319) BUG_ON(first_vcn < 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1320) BUG_ON(last_vcn < -1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1321) BUG_ON(last_vcn >= 0 && first_vcn > last_vcn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1322) BUG_ON(dst_len < 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1323) if (!rl) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1324) BUG_ON(first_vcn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1325) BUG_ON(last_vcn > 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1326) if (stop_vcn)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1327) *stop_vcn = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1328) /* Terminator byte. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1329) *dst = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1330) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1331) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1332) /* Skip to runlist element containing @first_vcn. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1333) while (rl->length && first_vcn >= rl[1].vcn)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1334) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1335) if (unlikely((!rl->length && first_vcn > rl->vcn) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1336) first_vcn < rl->vcn))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1337) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1338) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1339) * @dst_max is used for bounds checking in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1340) * ntfs_write_significant_bytes().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1341) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1342) dst_max = dst + dst_len - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1343) prev_lcn = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1344) /* Do the first partial run if present. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1345) if (first_vcn > rl->vcn) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1346) s64 delta, length = rl->length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1347)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1348) /* We know rl->length != 0 already. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1349) if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1350) goto err_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1351) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1352) * If @stop_vcn is given and finishes inside this run, cap the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1353) * run length.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1354) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1355) if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1356) s64 s1 = last_vcn + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1357) if (unlikely(rl[1].vcn > s1))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1358) length = s1 - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1359) the_end = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1360) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1361) delta = first_vcn - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1362) /* Write length. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1363) len_len = ntfs_write_significant_bytes(dst + 1, dst_max,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1364) length - delta);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1365) if (unlikely(len_len < 0))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1366) goto size_err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1367) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1368) * If the logical cluster number (lcn) denotes a hole and we
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1369) * are on NTFS 3.0+, we don't store it at all, i.e. we need
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1370) * zero space. On earlier NTFS versions we just write the lcn
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1371) * change. FIXME: Do we need to write the lcn change or just
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1372) * the lcn in that case? Not sure as I have never seen this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1373) * case on NT4. - We assume that we just need to write the lcn
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1374) * change until someone tells us otherwise... (AIA)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1375) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1376) if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1377) prev_lcn = rl->lcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1378) if (likely(rl->lcn >= 0))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1379) prev_lcn += delta;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1380) /* Write change in lcn. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1381) lcn_len = ntfs_write_significant_bytes(dst + 1 +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1382) len_len, dst_max, prev_lcn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1383) if (unlikely(lcn_len < 0))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1384) goto size_err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1385) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1386) lcn_len = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1387) dst_next = dst + len_len + lcn_len + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1388) if (unlikely(dst_next > dst_max))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1389) goto size_err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1390) /* Update header byte. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1391) *dst = lcn_len << 4 | len_len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1392) /* Position at next mapping pairs array element. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1393) dst = dst_next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1394) /* Go to next runlist element. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1395) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1396) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1397) /* Do the full runs. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1398) for (; rl->length && !the_end; rl++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1399) s64 length = rl->length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1400)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1401) if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1402) goto err_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1403) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1404) * If @stop_vcn is given and finishes inside this run, cap the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1405) * run length.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1406) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1407) if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1408) s64 s1 = last_vcn + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1409) if (unlikely(rl[1].vcn > s1))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1410) length = s1 - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1411) the_end = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1412) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1413) /* Write length. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1414) len_len = ntfs_write_significant_bytes(dst + 1, dst_max,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1415) length);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1416) if (unlikely(len_len < 0))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1417) goto size_err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1418) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1419) * If the logical cluster number (lcn) denotes a hole and we
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1420) * are on NTFS 3.0+, we don't store it at all, i.e. we need
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1421) * zero space. On earlier NTFS versions we just write the lcn
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1422) * change. FIXME: Do we need to write the lcn change or just
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1423) * the lcn in that case? Not sure as I have never seen this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1424) * case on NT4. - We assume that we just need to write the lcn
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1425) * change until someone tells us otherwise... (AIA)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1426) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1427) if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1428) /* Write change in lcn. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1429) lcn_len = ntfs_write_significant_bytes(dst + 1 +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1430) len_len, dst_max, rl->lcn - prev_lcn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1431) if (unlikely(lcn_len < 0))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1432) goto size_err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1433) prev_lcn = rl->lcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1434) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1435) lcn_len = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1436) dst_next = dst + len_len + lcn_len + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1437) if (unlikely(dst_next > dst_max))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1438) goto size_err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1439) /* Update header byte. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1440) *dst = lcn_len << 4 | len_len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1441) /* Position at next mapping pairs array element. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1442) dst = dst_next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1443) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1444) /* Success. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1445) err = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1446) size_err:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1447) /* Set stop vcn. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1448) if (stop_vcn)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1449) *stop_vcn = rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1450) /* Add terminator byte. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1451) *dst = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1452) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1453) err_out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1454) if (rl->lcn == LCN_RL_NOT_MAPPED)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1455) err = -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1456) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1457) err = -EIO;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1458) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1459) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1460)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1461) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1462) * ntfs_rl_truncate_nolock - truncate a runlist starting at a specified vcn
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1463) * @vol: ntfs volume (needed for error output)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1464) * @runlist: runlist to truncate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1465) * @new_length: the new length of the runlist in VCNs
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1466) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1467) * Truncate the runlist described by @runlist as well as the memory buffer
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1468) * holding the runlist elements to a length of @new_length VCNs.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1469) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1470) * If @new_length lies within the runlist, the runlist elements with VCNs of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1471) * @new_length and above are discarded. As a special case if @new_length is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1472) * zero, the runlist is discarded and set to NULL.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1473) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1474) * If @new_length lies beyond the runlist, a sparse runlist element is added to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1475) * the end of the runlist @runlist or if the last runlist element is a sparse
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1476) * one already, this is extended.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1477) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1478) * Note, no checking is done for unmapped runlist elements. It is assumed that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1479) * the caller has mapped any elements that need to be mapped already.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1480) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1481) * Return 0 on success and -errno on error.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1482) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1483) * Locking: The caller must hold @runlist->lock for writing.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1484) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1485) int ntfs_rl_truncate_nolock(const ntfs_volume *vol, runlist *const runlist,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1486) const s64 new_length)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1487) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1488) runlist_element *rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1489) int old_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1490)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1491) ntfs_debug("Entering for new_length 0x%llx.", (long long)new_length);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1492) BUG_ON(!runlist);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1493) BUG_ON(new_length < 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1494) rl = runlist->rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1495) if (!new_length) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1496) ntfs_debug("Freeing runlist.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1497) runlist->rl = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1498) if (rl)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1499) ntfs_free(rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1500) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1501) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1502) if (unlikely(!rl)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1503) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1504) * Create a runlist consisting of a sparse runlist element of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1505) * length @new_length followed by a terminator runlist element.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1506) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1507) rl = ntfs_malloc_nofs(PAGE_SIZE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1508) if (unlikely(!rl)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1509) ntfs_error(vol->sb, "Not enough memory to allocate "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1510) "runlist element buffer.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1511) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1512) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1513) runlist->rl = rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1514) rl[1].length = rl->vcn = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1515) rl->lcn = LCN_HOLE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1516) rl[1].vcn = rl->length = new_length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1517) rl[1].lcn = LCN_ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1518) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1519) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1520) BUG_ON(new_length < rl->vcn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1521) /* Find @new_length in the runlist. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1522) while (likely(rl->length && new_length >= rl[1].vcn))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1523) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1524) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1525) * If not at the end of the runlist we need to shrink it.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1526) * If at the end of the runlist we need to expand it.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1527) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1528) if (rl->length) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1529) runlist_element *trl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1530) bool is_end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1531)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1532) ntfs_debug("Shrinking runlist.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1533) /* Determine the runlist size. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1534) trl = rl + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1535) while (likely(trl->length))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1536) trl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1537) old_size = trl - runlist->rl + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1538) /* Truncate the run. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1539) rl->length = new_length - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1540) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1541) * If a run was partially truncated, make the following runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1542) * element a terminator.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1543) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1544) is_end = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1545) if (rl->length) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1546) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1547) if (!rl->length)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1548) is_end = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1549) rl->vcn = new_length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1550) rl->length = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1551) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1552) rl->lcn = LCN_ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1553) /* Reallocate memory if necessary. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1554) if (!is_end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1555) int new_size = rl - runlist->rl + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1556) rl = ntfs_rl_realloc(runlist->rl, old_size, new_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1557) if (IS_ERR(rl))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1558) ntfs_warning(vol->sb, "Failed to shrink "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1559) "runlist buffer. This just "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1560) "wastes a bit of memory "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1561) "temporarily so we ignore it "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1562) "and return success.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1563) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1564) runlist->rl = rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1565) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1566) } else if (likely(/* !rl->length && */ new_length > rl->vcn)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1567) ntfs_debug("Expanding runlist.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1568) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1569) * If there is a previous runlist element and it is a sparse
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1570) * one, extend it. Otherwise need to add a new, sparse runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1571) * element.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1572) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1573) if ((rl > runlist->rl) && ((rl - 1)->lcn == LCN_HOLE))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1574) (rl - 1)->length = new_length - (rl - 1)->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1575) else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1576) /* Determine the runlist size. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1577) old_size = rl - runlist->rl + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1578) /* Reallocate memory if necessary. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1579) rl = ntfs_rl_realloc(runlist->rl, old_size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1580) old_size + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1581) if (IS_ERR(rl)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1582) ntfs_error(vol->sb, "Failed to expand runlist "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1583) "buffer, aborting.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1584) return PTR_ERR(rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1585) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1586) runlist->rl = rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1587) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1588) * Set @rl to the same runlist element in the new
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1589) * runlist as before in the old runlist.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1590) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1591) rl += old_size - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1592) /* Add a new, sparse runlist element. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1593) rl->lcn = LCN_HOLE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1594) rl->length = new_length - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1595) /* Add a new terminator runlist element. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1596) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1597) rl->length = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1598) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1599) rl->vcn = new_length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1600) rl->lcn = LCN_ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1601) } else /* if (unlikely(!rl->length && new_length == rl->vcn)) */ {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1602) /* Runlist already has same size as requested. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1603) rl->lcn = LCN_ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1604) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1605) ntfs_debug("Done.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1606) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1607) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1608)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1609) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1610) * ntfs_rl_punch_nolock - punch a hole into a runlist
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1611) * @vol: ntfs volume (needed for error output)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1612) * @runlist: runlist to punch a hole into
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1613) * @start: starting VCN of the hole to be created
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1614) * @length: size of the hole to be created in units of clusters
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1615) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1616) * Punch a hole into the runlist @runlist starting at VCN @start and of size
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1617) * @length clusters.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1618) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1619) * Return 0 on success and -errno on error, in which case @runlist has not been
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1620) * modified.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1621) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1622) * If @start and/or @start + @length are outside the runlist return error code
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1623) * -ENOENT.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1624) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1625) * If the runlist contains unmapped or error elements between @start and @start
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1626) * + @length return error code -EINVAL.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1627) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1628) * Locking: The caller must hold @runlist->lock for writing.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1629) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1630) int ntfs_rl_punch_nolock(const ntfs_volume *vol, runlist *const runlist,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1631) const VCN start, const s64 length)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1632) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1633) const VCN end = start + length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1634) s64 delta;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1635) runlist_element *rl, *rl_end, *rl_real_end, *trl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1636) int old_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1637) bool lcn_fixup = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1638)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1639) ntfs_debug("Entering for start 0x%llx, length 0x%llx.",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1640) (long long)start, (long long)length);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1641) BUG_ON(!runlist);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1642) BUG_ON(start < 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1643) BUG_ON(length < 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1644) BUG_ON(end < 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1645) rl = runlist->rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1646) if (unlikely(!rl)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1647) if (likely(!start && !length))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1648) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1649) return -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1650) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1651) /* Find @start in the runlist. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1652) while (likely(rl->length && start >= rl[1].vcn))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1653) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1654) rl_end = rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1655) /* Find @end in the runlist. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1656) while (likely(rl_end->length && end >= rl_end[1].vcn)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1657) /* Verify there are no unmapped or error elements. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1658) if (unlikely(rl_end->lcn < LCN_HOLE))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1659) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1660) rl_end++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1661) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1662) /* Check the last element. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1663) if (unlikely(rl_end->length && rl_end->lcn < LCN_HOLE))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1664) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1665) /* This covers @start being out of bounds, too. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1666) if (!rl_end->length && end > rl_end->vcn)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1667) return -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1668) if (!length)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1669) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1670) if (!rl->length)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1671) return -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1672) rl_real_end = rl_end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1673) /* Determine the runlist size. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1674) while (likely(rl_real_end->length))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1675) rl_real_end++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1676) old_size = rl_real_end - runlist->rl + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1677) /* If @start is in a hole simply extend the hole. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1678) if (rl->lcn == LCN_HOLE) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1679) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1680) * If both @start and @end are in the same sparse run, we are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1681) * done.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1682) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1683) if (end <= rl[1].vcn) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1684) ntfs_debug("Done (requested hole is already sparse).");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1685) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1686) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1687) extend_hole:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1688) /* Extend the hole. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1689) rl->length = end - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1690) /* If @end is in a hole, merge it with the current one. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1691) if (rl_end->lcn == LCN_HOLE) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1692) rl_end++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1693) rl->length = rl_end->vcn - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1694) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1695) /* We have done the hole. Now deal with the remaining tail. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1696) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1697) /* Cut out all runlist elements up to @end. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1698) if (rl < rl_end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1699) memmove(rl, rl_end, (rl_real_end - rl_end + 1) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1700) sizeof(*rl));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1701) /* Adjust the beginning of the tail if necessary. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1702) if (end > rl->vcn) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1703) delta = end - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1704) rl->vcn = end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1705) rl->length -= delta;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1706) /* Only adjust the lcn if it is real. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1707) if (rl->lcn >= 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1708) rl->lcn += delta;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1709) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1710) shrink_allocation:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1711) /* Reallocate memory if the allocation changed. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1712) if (rl < rl_end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1713) rl = ntfs_rl_realloc(runlist->rl, old_size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1714) old_size - (rl_end - rl));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1715) if (IS_ERR(rl))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1716) ntfs_warning(vol->sb, "Failed to shrink "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1717) "runlist buffer. This just "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1718) "wastes a bit of memory "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1719) "temporarily so we ignore it "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1720) "and return success.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1721) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1722) runlist->rl = rl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1723) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1724) ntfs_debug("Done (extend hole).");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1725) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1726) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1727) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1728) * If @start is at the beginning of a run things are easier as there is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1729) * no need to split the first run.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1730) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1731) if (start == rl->vcn) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1732) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1733) * @start is at the beginning of a run.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1734) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1735) * If the previous run is sparse, extend its hole.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1736) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1737) * If @end is not in the same run, switch the run to be sparse
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1738) * and extend the newly created hole.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1739) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1740) * Thus both of these cases reduce the problem to the above
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1741) * case of "@start is in a hole".
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1742) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1743) if (rl > runlist->rl && (rl - 1)->lcn == LCN_HOLE) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1744) rl--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1745) goto extend_hole;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1746) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1747) if (end >= rl[1].vcn) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1748) rl->lcn = LCN_HOLE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1749) goto extend_hole;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1750) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1751) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1752) * The final case is when @end is in the same run as @start.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1753) * For this need to split the run into two. One run for the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1754) * sparse region between the beginning of the old run, i.e.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1755) * @start, and @end and one for the remaining non-sparse
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1756) * region, i.e. between @end and the end of the old run.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1757) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1758) trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1759) if (IS_ERR(trl))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1760) goto enomem_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1761) old_size++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1762) if (runlist->rl != trl) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1763) rl = trl + (rl - runlist->rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1764) rl_end = trl + (rl_end - runlist->rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1765) rl_real_end = trl + (rl_real_end - runlist->rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1766) runlist->rl = trl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1767) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1768) split_end:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1769) /* Shift all the runs up by one. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1770) memmove(rl + 1, rl, (rl_real_end - rl + 1) * sizeof(*rl));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1771) /* Finally, setup the two split runs. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1772) rl->lcn = LCN_HOLE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1773) rl->length = length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1774) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1775) rl->vcn += length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1776) /* Only adjust the lcn if it is real. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1777) if (rl->lcn >= 0 || lcn_fixup)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1778) rl->lcn += length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1779) rl->length -= length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1780) ntfs_debug("Done (split one).");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1781) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1782) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1783) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1784) * @start is neither in a hole nor at the beginning of a run.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1785) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1786) * If @end is in a hole, things are easier as simply truncating the run
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1787) * @start is in to end at @start - 1, deleting all runs after that up
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1788) * to @end, and finally extending the beginning of the run @end is in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1789) * to be @start is all that is needed.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1790) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1791) if (rl_end->lcn == LCN_HOLE) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1792) /* Truncate the run containing @start. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1793) rl->length = start - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1794) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1795) /* Cut out all runlist elements up to @end. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1796) if (rl < rl_end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1797) memmove(rl, rl_end, (rl_real_end - rl_end + 1) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1798) sizeof(*rl));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1799) /* Extend the beginning of the run @end is in to be @start. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1800) rl->vcn = start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1801) rl->length = rl[1].vcn - start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1802) goto shrink_allocation;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1803) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1804) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1805) * If @end is not in a hole there are still two cases to distinguish.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1806) * Either @end is or is not in the same run as @start.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1807) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1808) * The second case is easier as it can be reduced to an already solved
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1809) * problem by truncating the run @start is in to end at @start - 1.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1810) * Then, if @end is in the next run need to split the run into a sparse
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1811) * run followed by a non-sparse run (already covered above) and if @end
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1812) * is not in the next run switching it to be sparse, again reduces the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1813) * problem to the already covered case of "@start is in a hole".
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1814) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1815) if (end >= rl[1].vcn) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1816) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1817) * If @end is not in the next run, reduce the problem to the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1818) * case of "@start is in a hole".
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1819) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1820) if (rl[1].length && end >= rl[2].vcn) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1821) /* Truncate the run containing @start. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1822) rl->length = start - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1823) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1824) rl->vcn = start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1825) rl->lcn = LCN_HOLE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1826) goto extend_hole;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1827) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1828) trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1829) if (IS_ERR(trl))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1830) goto enomem_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1831) old_size++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1832) if (runlist->rl != trl) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1833) rl = trl + (rl - runlist->rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1834) rl_end = trl + (rl_end - runlist->rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1835) rl_real_end = trl + (rl_real_end - runlist->rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1836) runlist->rl = trl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1837) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1838) /* Truncate the run containing @start. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1839) rl->length = start - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1840) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1841) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1842) * @end is in the next run, reduce the problem to the case
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1843) * where "@start is at the beginning of a run and @end is in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1844) * the same run as @start".
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1845) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1846) delta = rl->vcn - start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1847) rl->vcn = start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1848) if (rl->lcn >= 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1849) rl->lcn -= delta;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1850) /* Need this in case the lcn just became negative. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1851) lcn_fixup = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1852) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1853) rl->length += delta;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1854) goto split_end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1855) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1856) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1857) * The first case from above, i.e. @end is in the same run as @start.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1858) * We need to split the run into three. One run for the non-sparse
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1859) * region between the beginning of the old run and @start, one for the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1860) * sparse region between @start and @end, and one for the remaining
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1861) * non-sparse region, i.e. between @end and the end of the old run.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1862) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1863) trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1864) if (IS_ERR(trl))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1865) goto enomem_out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1866) old_size += 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1867) if (runlist->rl != trl) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1868) rl = trl + (rl - runlist->rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1869) rl_end = trl + (rl_end - runlist->rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1870) rl_real_end = trl + (rl_real_end - runlist->rl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1871) runlist->rl = trl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1872) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1873) /* Shift all the runs up by two. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1874) memmove(rl + 2, rl, (rl_real_end - rl + 1) * sizeof(*rl));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1875) /* Finally, setup the three split runs. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1876) rl->length = start - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1877) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1878) rl->vcn = start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1879) rl->lcn = LCN_HOLE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1880) rl->length = length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1881) rl++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1882) delta = end - rl->vcn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1883) rl->vcn = end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1884) rl->lcn += delta;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1885) rl->length -= delta;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1886) ntfs_debug("Done (split both).");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1887) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1888) enomem_out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1889) ntfs_error(vol->sb, "Not enough memory to extend runlist buffer.");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1890) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1891) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1892)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1893) #endif /* NTFS_RW */
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags