1 files changed, 353 insertions, 21 deletions

diff --git a/fs/ntfs/runlist.c b/fs/ntfs/runlist.c
index 758855b0414e..f5b2ac929081 100644
--- a/fs/ntfs/runlist.c
+++ b/fs/ntfs/runlist.c
@@ -35,7 +35,7 @@ static inline void ntfs_rl_mm(runlist_element *base, int dst, int src,
                 int size)
 {
         if (likely((dst != src) && (size > 0)))
-                memmove(base + dst, base + src, size * sizeof (*base));
+                memmove(base + dst, base + src, size * sizeof(*base));
 }
 
 /**
@@ -95,6 +95,51 @@ static inline runlist_element *ntfs_rl_realloc(runlist_element *rl,
 }
 
 /**
+ * ntfs_rl_realloc_nofail - Reallocate memory for runlists
+ * @rl:         original runlist
+ * @old_size:   number of runlist elements in the original runlist @rl
+ * @new_size:   number of runlist elements we need space for
+ *
+ * As the runlists grow, more memory will be required.  To prevent the
+ * kernel having to allocate and reallocate large numbers of small bits of
+ * memory, this function returns an entire page of memory.
+ *
+ * This function guarantees that the allocation will succeed.  It will sleep
+ * for as long as it takes to complete the allocation.
+ *
+ * It is up to the caller to serialize access to the runlist @rl.
+ *
+ * N.B.  If the new allocation doesn't require a different number of pages in
+ *       memory, the function will return the original pointer.
+ *
+ * On success, return a pointer to the newly allocated, or recycled, memory.
+ * On error, return -errno. The following error codes are defined:
+ *      -ENOMEM - Not enough memory to allocate runlist array.
+ *      -EINVAL - Invalid parameters were passed in.
+ */
+static inline runlist_element *ntfs_rl_realloc_nofail(runlist_element *rl,
+                int old_size, int new_size)
+{
+        runlist_element *new_rl;
+
+        old_size = PAGE_ALIGN(old_size * sizeof(*rl));
+        new_size = PAGE_ALIGN(new_size * sizeof(*rl));
+        if (old_size == new_size)
+                return rl;
+
+        new_rl = ntfs_malloc_nofs_nofail(new_size);
+        BUG_ON(!new_rl);
+
+        if (likely(rl != NULL)) {
+                if (unlikely(old_size > new_size))
+                        old_size = new_size;
+                memcpy(new_rl, rl, old_size);
+                ntfs_free(rl);
+        }
+        return new_rl;
+}
+
+/**
  * ntfs_are_rl_mergeable - test if two runlists can be joined together
  * @dst:        original runlist
  * @src:        new runlist to test for mergeability with @dst
@@ -497,6 +542,7 @@ runlist_element *ntfs_runlists_merge(runlist_element *drl,
                         /* Scan to the end of the source runlist. */
                         for (dend = 0; likely(drl[dend].length); dend++)
                                 ;
+                        dend++;
                         drl = ntfs_rl_realloc(drl, dend, dend + 1);
                         if (IS_ERR(drl))
                                 return drl;
@@ -566,8 +612,8 @@ runlist_element *ntfs_runlists_merge(runlist_element *drl,
                  ((drl[dins].vcn + drl[dins].length) <=      /* End of hole   */
                   (srl[send - 1].vcn + srl[send - 1].length)));
 
-        /* Or we'll lose an end marker */
-        if (start && finish && (drl[dins].length == 0))
+        /* Or we will lose an end marker. */
+        if (finish && !drl[dins].length)
                 ss++;
         if (marker && (drl[dins].vcn + drl[dins].length > srl[send - 1].vcn))
                 finish = FALSE;
@@ -621,11 +667,8 @@ runlist_element *ntfs_runlists_merge(runlist_element *drl,
                         if (drl[ds].lcn != LCN_RL_NOT_MAPPED) {
                                 /* Add an unmapped runlist element. */
                                 if (!slots) {
-                                        /* FIXME/TODO: We need to have the
-                                         * extra memory already! (AIA) */
-                                        drl = ntfs_rl_realloc(drl, ds, ds + 2);
-                                        if (!drl)
-                                                goto critical_error;
+                                        drl = ntfs_rl_realloc_nofail(drl, ds,
+                                                        ds + 2);
                                         slots = 2;
                                 }
                                 ds++;
@@ -640,13 +683,8 @@ runlist_element *ntfs_runlists_merge(runlist_element *drl,
                         drl[ds].length = marker_vcn - drl[ds].vcn;
                         /* Finally add the ENOENT terminator. */
                         ds++;
-                        if (!slots) {
-                                /* FIXME/TODO: We need to have the extra
-                                 * memory already! (AIA) */
-                                drl = ntfs_rl_realloc(drl, ds, ds + 1);
-                                if (!drl)
-                                        goto critical_error;
-                        }
+                        if (!slots)
+                                drl = ntfs_rl_realloc_nofail(drl, ds, ds + 1);
                         drl[ds].vcn = marker_vcn;
                         drl[ds].lcn = LCN_ENOENT;
                         drl[ds].length = (s64)0;
@@ -659,11 +697,6 @@ finished:
         ntfs_debug("Merged runlist:");
         ntfs_debug_dump_runlist(drl);
         return drl;
-
-critical_error:
-        /* Critical error! We cannot afford to fail here. */
-        ntfs_error(NULL, "Critical error! Not enough memory.");
-        panic("NTFS: Cannot continue.");
 }
 
 /**
@@ -727,6 +760,9 @@ runlist_element *ntfs_mapping_pairs_decompress(const ntfs_volume *vol,
                 ntfs_error(vol->sb, "Corrupt attribute.");
                 return ERR_PTR(-EIO);
         }
+        /* If the mapping pairs array is valid but empty, nothing to do. */
+        if (!vcn && !*buf)
+                return old_rl;
         /* Current position in runlist array. */
         rlpos = 0;
         /* Allocate first page and set current runlist size to one page. */
@@ -1419,6 +1455,7 @@ err_out:
 
 /**
  * ntfs_rl_truncate_nolock - truncate a runlist starting at a specified vcn
+ * @vol:        ntfs volume (needed for error output)
  * @runlist:    runlist to truncate
  * @new_length: the new length of the runlist in VCNs
  *
@@ -1426,12 +1463,16 @@ err_out:
  * holding the runlist elements to a length of @new_length VCNs.
  *
  * If @new_length lies within the runlist, the runlist elements with VCNs of
- * @new_length and above are discarded.
+ * @new_length and above are discarded.  As a special case if @new_length is
+ * zero, the runlist is discarded and set to NULL.
  *
  * If @new_length lies beyond the runlist, a sparse runlist element is added to
  * the end of the runlist @runlist or if the last runlist element is a sparse
  * one already, this is extended.
  *
+ * Note, no checking is done for unmapped runlist elements.  It is assumed that
+ * the caller has mapped any elements that need to be mapped already.
+ *
  * Return 0 on success and -errno on error.
  *
  * Locking: The caller must hold @runlist->lock for writing.
@@ -1446,6 +1487,13 @@ int ntfs_rl_truncate_nolock(const ntfs_volume *vol, runlist *const runlist,
         BUG_ON(!runlist);
         BUG_ON(new_length < 0);
         rl = runlist->rl;
+        if (!new_length) {
+                ntfs_debug("Freeing runlist.");
+                runlist->rl = NULL;
+                if (rl)
+                        ntfs_free(rl);
+                return 0;
+        }
         if (unlikely(!rl)) {
                 /*
                  * Create a runlist consisting of a sparse runlist element of
@@ -1553,4 +1601,288 @@ int ntfs_rl_truncate_nolock(const ntfs_volume *vol, runlist *const runlist,
         return 0;
 }
 
+/**
+ * ntfs_rl_punch_nolock - punch a hole into a runlist
+ * @vol:        ntfs volume (needed for error output)
+ * @runlist:    runlist to punch a hole into
+ * @start:      starting VCN of the hole to be created
+ * @length:     size of the hole to be created in units of clusters
+ *
+ * Punch a hole into the runlist @runlist starting at VCN @start and of size
+ * @length clusters.
+ *
+ * Return 0 on success and -errno on error, in which case @runlist has not been
+ * modified.
+ *
+ * If @start and/or @start + @length are outside the runlist return error code
+ * -ENOENT.
+ *
+ * If the runlist contains unmapped or error elements between @start and @start
+ * + @length return error code -EINVAL.
+ *
+ * Locking: The caller must hold @runlist->lock for writing.
+ */
+int ntfs_rl_punch_nolock(const ntfs_volume *vol, runlist *const runlist,
+                const VCN start, const s64 length)
+{
+        const VCN end = start + length;
+        s64 delta;
+        runlist_element *rl, *rl_end, *rl_real_end, *trl;
+        int old_size;
+        BOOL lcn_fixup = FALSE;
+
+        ntfs_debug("Entering for start 0x%llx, length 0x%llx.",
+                        (long long)start, (long long)length);
+        BUG_ON(!runlist);
+        BUG_ON(start < 0);
+        BUG_ON(length < 0);
+        BUG_ON(end < 0);
+        rl = runlist->rl;
+        if (unlikely(!rl)) {
+                if (likely(!start && !length))
+                        return 0;
+                return -ENOENT;
+        }
+        /* Find @start in the runlist. */
+        while (likely(rl->length && start >= rl[1].vcn))
+                rl++;
+        rl_end = rl;
+        /* Find @end in the runlist. */
+        while (likely(rl_end->length && end >= rl_end[1].vcn)) {
+                /* Verify there are no unmapped or error elements. */
+                if (unlikely(rl_end->lcn < LCN_HOLE))
+                        return -EINVAL;
+                rl_end++;
+        }
+        /* Check the last element. */
+        if (unlikely(rl_end->length && rl_end->lcn < LCN_HOLE))
+                return -EINVAL;
+        /* This covers @start being out of bounds, too. */
+        if (!rl_end->length && end > rl_end->vcn)
+                return -ENOENT;
+        if (!length)
+                return 0;
+        if (!rl->length)
+                return -ENOENT;
+        rl_real_end = rl_end;
+        /* Determine the runlist size. */
+        while (likely(rl_real_end->length))
+                rl_real_end++;
+        old_size = rl_real_end - runlist->rl + 1;
+        /* If @start is in a hole simply extend the hole. */
+        if (rl->lcn == LCN_HOLE) {
+                /*
+                 * If both @start and @end are in the same sparse run, we are
+                 * done.
+                 */
+                if (end <= rl[1].vcn) {
+                        ntfs_debug("Done (requested hole is already sparse).");
+                        return 0;
+                }
+extend_hole:
+                /* Extend the hole. */
+                rl->length = end - rl->vcn;
+                /* If @end is in a hole, merge it with the current one. */
+                if (rl_end->lcn == LCN_HOLE) {
+                        rl_end++;
+                        rl->length = rl_end->vcn - rl->vcn;
+                }
+                /* We have done the hole.  Now deal with the remaining tail. */
+                rl++;
+                /* Cut out all runlist elements up to @end. */
+                if (rl < rl_end)
+                        memmove(rl, rl_end, (rl_real_end - rl_end + 1) *
+                                        sizeof(*rl));
+                /* Adjust the beginning of the tail if necessary. */
+                if (end > rl->vcn) {
+                        s64 delta = end - rl->vcn;
+                        rl->vcn = end;
+                        rl->length -= delta;
+                        /* Only adjust the lcn if it is real. */
+                        if (rl->lcn >= 0)
+                                rl->lcn += delta;
+                }
+shrink_allocation:
+                /* Reallocate memory if the allocation changed. */
+                if (rl < rl_end) {
+                        rl = ntfs_rl_realloc(runlist->rl, old_size,
+                                        old_size - (rl_end - rl));
+                        if (IS_ERR(rl))
+                                ntfs_warning(vol->sb, "Failed to shrink "
+                                                "runlist buffer.  This just "
+                                                "wastes a bit of memory "
+                                                "temporarily so we ignore it "
+                                                "and return success.");
+                        else
+                                runlist->rl = rl;
+                }
+                ntfs_debug("Done (extend hole).");
+                return 0;
+        }
+        /*
+         * If @start is at the beginning of a run things are easier as there is
+         * no need to split the first run.
+         */
+        if (start == rl->vcn) {
+                /*
+                 * @start is at the beginning of a run.
+                 *
+                 * If the previous run is sparse, extend its hole.
+                 *
+                 * If @end is not in the same run, switch the run to be sparse
+                 * and extend the newly created hole.
+                 *
+                 * Thus both of these cases reduce the problem to the above
+                 * case of "@start is in a hole".
+                 */
+                if (rl > runlist->rl && (rl - 1)->lcn == LCN_HOLE) {
+                        rl--;
+                        goto extend_hole;
+                }
+                if (end >= rl[1].vcn) {
+                        rl->lcn = LCN_HOLE;
+                        goto extend_hole;
+                }
+                /*
+                 * The final case is when @end is in the same run as @start.
+                 * For this need to split the run into two.  One run for the
+                 * sparse region between the beginning of the old run, i.e.
+                 * @start, and @end and one for the remaining non-sparse
+                 * region, i.e. between @end and the end of the old run.
+                 */
+                trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1);
+                if (IS_ERR(trl))
+                        goto enomem_out;
+                old_size++;
+                if (runlist->rl != trl) {
+                        rl = trl + (rl - runlist->rl);
+                        rl_end = trl + (rl_end - runlist->rl);
+                        rl_real_end = trl + (rl_real_end - runlist->rl);
+                        runlist->rl = trl;
+                }
+split_end:
+                /* Shift all the runs up by one. */
+                memmove(rl + 1, rl, (rl_real_end - rl + 1) * sizeof(*rl));
+                /* Finally, setup the two split runs. */
+                rl->lcn = LCN_HOLE;
+                rl->length = length;
+                rl++;
+                rl->vcn += length;
+                /* Only adjust the lcn if it is real. */
+                if (rl->lcn >= 0 || lcn_fixup)
+                        rl->lcn += length;
+                rl->length -= length;
+                ntfs_debug("Done (split one).");
+                return 0;
+        }
+        /*
+         * @start is neither in a hole nor at the beginning of a run.
+         *
+         * If @end is in a hole, things are easier as simply truncating the run
+         * @start is in to end at @start - 1, deleting all runs after that up
+         * to @end, and finally extending the beginning of the run @end is in
+         * to be @start is all that is needed.
+         */
+        if (rl_end->lcn == LCN_HOLE) {
+                /* Truncate the run containing @start. */
+                rl->length = start - rl->vcn;
+                rl++;
+                /* Cut out all runlist elements up to @end. */
+                if (rl < rl_end)
+                        memmove(rl, rl_end, (rl_real_end - rl_end + 1) *
+                                        sizeof(*rl));
+                /* Extend the beginning of the run @end is in to be @start. */
+                rl->vcn = start;
+                rl->length = rl[1].vcn - start;
+                goto shrink_allocation;
+        }
+        /* 
+         * If @end is not in a hole there are still two cases to distinguish.
+         * Either @end is or is not in the same run as @start.
+         *
+         * The second case is easier as it can be reduced to an already solved
+         * problem by truncating the run @start is in to end at @start - 1.
+         * Then, if @end is in the next run need to split the run into a sparse
+         * run followed by a non-sparse run (already covered above) and if @end
+         * is not in the next run switching it to be sparse, again reduces the
+         * problem to the already covered case of "@start is in a hole".
+         */
+        if (end >= rl[1].vcn) {
+                /*
+                 * If @end is not in the next run, reduce the problem to the
+                 * case of "@start is in a hole".
+                 */
+                if (rl[1].length && end >= rl[2].vcn) {
+                        /* Truncate the run containing @start. */
+                        rl->length = start - rl->vcn;
+                        rl++;
+                        rl->vcn = start;
+                        rl->lcn = LCN_HOLE;
+                        goto extend_hole;
+                }
+                trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1);
+                if (IS_ERR(trl))
+                        goto enomem_out;
+                old_size++;
+                if (runlist->rl != trl) {
+                        rl = trl + (rl - runlist->rl);
+                        rl_end = trl + (rl_end - runlist->rl);
+                        rl_real_end = trl + (rl_real_end - runlist->rl);
+                        runlist->rl = trl;
+                }
+                /* Truncate the run containing @start. */
+                rl->length = start - rl->vcn;
+                rl++;
+                /*
+                 * @end is in the next run, reduce the problem to the case
+                 * where "@start is at the beginning of a run and @end is in
+                 * the same run as @start".
+                 */
+                delta = rl->vcn - start;
+                rl->vcn = start;
+                if (rl->lcn >= 0) {
+                        rl->lcn -= delta;
+                        /* Need this in case the lcn just became negative. */
+                        lcn_fixup = TRUE;
+                }
+                rl->length += delta;
+                goto split_end;
+        }
+        /*
+         * The first case from above, i.e. @end is in the same run as @start.
+         * We need to split the run into three.  One run for the non-sparse
+         * region between the beginning of the old run and @start, one for the
+         * sparse region between @start and @end, and one for the remaining
+         * non-sparse region, i.e. between @end and the end of the old run.
+         */
+        trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 2);
+        if (IS_ERR(trl))
+                goto enomem_out;
+        old_size += 2;
+        if (runlist->rl != trl) {
+                rl = trl + (rl - runlist->rl);
+                rl_end = trl + (rl_end - runlist->rl);
+                rl_real_end = trl + (rl_real_end - runlist->rl);
+                runlist->rl = trl;
+        }
+        /* Shift all the runs up by two. */
+        memmove(rl + 2, rl, (rl_real_end - rl + 1) * sizeof(*rl));
+        /* Finally, setup the three split runs. */
+        rl->length = start - rl->vcn;
+        rl++;
+        rl->vcn = start;
+        rl->lcn = LCN_HOLE;
+        rl->length = length;
+        rl++;
+        delta = end - rl->vcn;
+        rl->vcn = end;
+        rl->lcn += delta;
+        rl->length -= delta;
+        ntfs_debug("Done (split both).");
+        return 0;
+enomem_out:
+        ntfs_error(vol->sb, "Not enough memory to extend runlist buffer.");
+        return -ENOMEM;
+}
+
 #endif /* NTFS_RW */