1 files changed, 92 insertions, 77 deletions

diff --git a/fs/ntfs/runlist.c b/fs/ntfs/runlist.c
index f5b2ac929081..061b5ff6b73c 100644
--- a/fs/ntfs/runlist.c
+++ b/fs/ntfs/runlist.c
@@ -2,7 +2,7 @@
  * runlist.c - NTFS runlist handling code.  Part of the Linux-NTFS project.
  *
  * Copyright (c) 2001-2005 Anton Altaparmakov
- * Copyright (c) 2002 Richard Russon
+ * Copyright (c) 2002-2005 Richard Russon
  *
  * This program/include file is free software; you can redistribute it and/or
  * modify it under the terms of the GNU General Public License as published
@@ -158,17 +158,21 @@ static inline BOOL ntfs_are_rl_mergeable(runlist_element *dst,
         BUG_ON(!dst);
         BUG_ON(!src);
 
-        if ((dst->lcn < 0) || (src->lcn < 0)) {   /* Are we merging holes? */
-                if (dst->lcn == LCN_HOLE && src->lcn == LCN_HOLE)
-                        return TRUE;
+        /* We can merge unmapped regions even if they are misaligned. */
+        if ((dst->lcn == LCN_RL_NOT_MAPPED) && (src->lcn == LCN_RL_NOT_MAPPED))
+                return TRUE;
+        /* If the runs are misaligned, we cannot merge them. */
+        if ((dst->vcn + dst->length) != src->vcn)
                 return FALSE;
-        }
-        if ((dst->lcn + dst->length) != src->lcn) /* Are the runs contiguous? */
-                return FALSE;
-        if ((dst->vcn + dst->length) != src->vcn) /* Are the runs misaligned? */
-                return FALSE;
-
-        return TRUE;
+        /* If both runs are non-sparse and contiguous, we can merge them. */
+        if ((dst->lcn >= 0) && (src->lcn >= 0) &&
+                        ((dst->lcn + dst->length) == src->lcn))
+                return TRUE;
+        /* If we are merging two holes, we can merge them. */
+        if ((dst->lcn == LCN_HOLE) && (src->lcn == LCN_HOLE))
+                return TRUE;
+        /* Cannot merge. */
+        return FALSE;
 }
 
 /**
@@ -214,14 +218,15 @@ static inline void __ntfs_rl_merge(runlist_element *dst, runlist_element *src)
 static inline runlist_element *ntfs_rl_append(runlist_element *dst,
                 int dsize, runlist_element *src, int ssize, int loc)
 {
-        BOOL right;
-        int magic;
+        BOOL right = FALSE;     /* Right end of @src needs merging. */
+        int marker;             /* End of the inserted runs. */
 
         BUG_ON(!dst);
         BUG_ON(!src);
 
         /* First, check if the right hand end needs merging. */
-        right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1);
+        if ((loc + 1) < dsize)
+                right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1);
 
         /* Space required: @dst size + @src size, less one if we merged. */
         dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - right);
@@ -236,18 +241,19 @@ static inline runlist_element *ntfs_rl_append(runlist_element *dst,
         if (right)
                 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
 
-        magic = loc + ssize;
+        /* First run after the @src runs that have been inserted. */
+        marker = loc + ssize + 1;
 
         /* Move the tail of @dst out of the way, then copy in @src. */
-        ntfs_rl_mm(dst, magic + 1, loc + 1 + right, dsize - loc - 1 - right);
+        ntfs_rl_mm(dst, marker, loc + 1 + right, dsize - (loc + 1 + right));
         ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
 
         /* Adjust the size of the preceding hole. */
         dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
 
         /* We may have changed the length of the file, so fix the end marker */
-        if (dst[magic + 1].lcn == LCN_ENOENT)
-                dst[magic + 1].vcn = dst[magic].vcn + dst[magic].length;
+        if (dst[marker].lcn == LCN_ENOENT)
+                dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
 
         return dst;
 }
@@ -279,18 +285,17 @@ static inline runlist_element *ntfs_rl_append(runlist_element *dst,
 static inline runlist_element *ntfs_rl_insert(runlist_element *dst,
                 int dsize, runlist_element *src, int ssize, int loc)
 {
-        BOOL left = FALSE;
-        BOOL disc = FALSE;      /* Discontinuity */
-        BOOL hole = FALSE;      /* Following a hole */
-        int magic;
+        BOOL left = FALSE;      /* Left end of @src needs merging. */
+        BOOL disc = FALSE;      /* Discontinuity between @dst and @src. */
+        int marker;             /* End of the inserted runs. */
 
         BUG_ON(!dst);
         BUG_ON(!src);
 
-        /* disc => Discontinuity between the end of @dst and the start of @src.
-         *         This means we might need to insert a hole.
-         * hole => @dst ends with a hole or an unmapped region which we can
-         *         extend to match the discontinuity. */
+        /*
+         * disc => Discontinuity between the end of @dst and the start of @src.
+         *         This means we might need to insert a "not mapped" run.
+         */
         if (loc == 0)
                 disc = (src[0].vcn > 0);
         else {
@@ -303,58 +308,49 @@ static inline runlist_element *ntfs_rl_insert(runlist_element *dst,
                         merged_length += src->length;
 
                 disc = (src[0].vcn > dst[loc - 1].vcn + merged_length);
-                if (disc)
-                        hole = (dst[loc - 1].lcn == LCN_HOLE);
         }
-
-        /* Space required: @dst size + @src size, less one if we merged, plus
-         * one if there was a discontinuity, less one for a trailing hole. */
-        dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left + disc - hole);
+        /*
+         * Space required: @dst size + @src size, less one if we merged, plus
+         * one if there was a discontinuity.
+         */
+        dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left + disc);
         if (IS_ERR(dst))
                 return dst;
         /*
          * We are guaranteed to succeed from here so can start modifying the
          * original runlist.
          */
-
         if (left)
                 __ntfs_rl_merge(dst + loc - 1, src);
-
-        magic = loc + ssize - left + disc - hole;
+        /*
+         * First run after the @src runs that have been inserted.
+         * Nominally,  @marker equals @loc + @ssize, i.e. location + number of
+         * runs in @src.  However, if @left, then the first run in @src has
+         * been merged with one in @dst.  And if @disc, then @dst and @src do
+         * not meet and we need an extra run to fill the gap.
+         */
+        marker = loc + ssize - left + disc;
 
         /* Move the tail of @dst out of the way, then copy in @src. */
-        ntfs_rl_mm(dst, magic, loc, dsize - loc);
-        ntfs_rl_mc(dst, loc + disc - hole, src, left, ssize - left);
+        ntfs_rl_mm(dst, marker, loc, dsize - loc);
+        ntfs_rl_mc(dst, loc + disc, src, left, ssize - left);
 
-        /* Adjust the VCN of the last run ... */
-        if (dst[magic].lcn <= LCN_HOLE)
-                dst[magic].vcn = dst[magic - 1].vcn + dst[magic - 1].length;
+        /* Adjust the VCN of the first run after the insertion... */
+        dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
         /* ... and the length. */
-        if (dst[magic].lcn == LCN_HOLE || dst[magic].lcn == LCN_RL_NOT_MAPPED)
-                dst[magic].length = dst[magic + 1].vcn - dst[magic].vcn;
+        if (dst[marker].lcn == LCN_HOLE || dst[marker].lcn == LCN_RL_NOT_MAPPED)
+                dst[marker].length = dst[marker + 1].vcn - dst[marker].vcn;
 
-        /* Writing beyond the end of the file and there's a discontinuity. */
+        /* Writing beyond the end of the file and there is a discontinuity. */
         if (disc) {
-                if (hole)
-                        dst[loc - 1].length = dst[loc].vcn - dst[loc - 1].vcn;
-                else {
-                        if (loc > 0) {
-                                dst[loc].vcn = dst[loc - 1].vcn +
-                                                dst[loc - 1].length;
-                                dst[loc].length = dst[loc + 1].vcn -
-                                                dst[loc].vcn;
-                        } else {
-                                dst[loc].vcn = 0;
-                                dst[loc].length = dst[loc + 1].vcn;
-                        }
-                        dst[loc].lcn = LCN_RL_NOT_MAPPED;
+                if (loc > 0) {
+                        dst[loc].vcn = dst[loc - 1].vcn + dst[loc - 1].length;
+                        dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
+                } else {
+                        dst[loc].vcn = 0;
+                        dst[loc].length = dst[loc + 1].vcn;
                 }
-
-                magic += hole;
-
-                if (dst[magic].lcn == LCN_ENOENT)
-                        dst[magic].vcn = dst[magic - 1].vcn +
-                                        dst[magic - 1].length;
+                dst[loc].lcn = LCN_RL_NOT_MAPPED;
         }
         return dst;
 }
@@ -385,20 +381,23 @@ static inline runlist_element *ntfs_rl_insert(runlist_element *dst,
 static inline runlist_element *ntfs_rl_replace(runlist_element *dst,
                 int dsize, runlist_element *src, int ssize, int loc)
 {
-        BOOL left = FALSE;
-        BOOL right;
-        int magic;
+        BOOL left = FALSE;      /* Left end of @src needs merging. */
+        BOOL right = FALSE;     /* Right end of @src needs merging. */
+        int tail;               /* Start of tail of @dst. */
+        int marker;             /* End of the inserted runs. */
 
         BUG_ON(!dst);
         BUG_ON(!src);
 
-        /* First, merge the left and right ends, if necessary. */
-        right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1);
+        /* First, see if the left and right ends need merging. */
+        if ((loc + 1) < dsize)
+                right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1);
         if (loc > 0)
                 left = ntfs_are_rl_mergeable(dst + loc - 1, src);
-
-        /* Allocate some space. We'll need less if the left, right, or both
-         * ends were merged. */
+        /*
+         * Allocate some space.  We will need less if the left, right, or both
+         * ends get merged.
+         */
         dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left - right);
         if (IS_ERR(dst))
                 return dst;
@@ -406,21 +405,37 @@ static inline runlist_element *ntfs_rl_replace(runlist_element *dst,
          * We are guaranteed to succeed from here so can start modifying the
          * original runlists.
          */
+
+        /* First, merge the left and right ends, if necessary. */
         if (right)
                 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
         if (left)
                 __ntfs_rl_merge(dst + loc - 1, src);
-
-        /* FIXME: What does this mean? (AIA) */
-        magic = loc + ssize - left;
+        /*
+         * Offset of the tail of @dst.  This needs to be moved out of the way
+         * to make space for the runs to be copied from @src, i.e. the first
+         * run of the tail of @dst.
+         * Nominally, @tail equals @loc + 1, i.e. location, skipping the
+         * replaced run.  However, if @right, then one of @dst's runs is
+         * already merged into @src.
+         */
+        tail = loc + right + 1;
+        /*
+         * First run after the @src runs that have been inserted, i.e. where
+         * the tail of @dst needs to be moved to.
+         * Nominally, @marker equals @loc + @ssize, i.e. location + number of
+         * runs in @src.  However, if @left, then the first run in @src has
+         * been merged with one in @dst.
+         */
+        marker = loc + ssize - left;
 
         /* Move the tail of @dst out of the way, then copy in @src. */
-        ntfs_rl_mm(dst, magic, loc + right + 1, dsize - loc - right - 1);
+        ntfs_rl_mm(dst, marker, tail, dsize - tail);
         ntfs_rl_mc(dst, loc, src, left, ssize - left);
 
-        /* We may have changed the length of the file, so fix the end marker */
-        if (dst[magic].lcn == LCN_ENOENT)
-                dst[magic].vcn = dst[magic - 1].vcn + dst[magic - 1].length;
+        /* We may have changed the length of the file, so fix the end marker. */
+        if (dsize - tail > 0 && dst[marker].lcn == LCN_ENOENT)
+                dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
         return dst;
 }