aboutsummaryrefslogtreecommitdiffstats
path: root/fs/ntfs/runlist.c
diff options
context:
space:
mode:
authorAnton Altaparmakov <aia21@cantab.net>2005-09-20 09:19:30 -0400
committerAnton Altaparmakov <aia21@cantab.net>2005-09-20 09:19:30 -0400
commiteed8b2dee7cff46dd4bf5b82dc53465d229162ba (patch)
tree1508bedde4dda971c56dc30c7edf1e36bfbefc9e /fs/ntfs/runlist.c
parent676d55ae30ea3b688f0386f70553489f25f24d55 (diff)
NTFS: More runlist handling fixes from Richard Russon and myself.
Signed-off-by: Anton Altaparmakov <aia21@cantab.net>
Diffstat (limited to 'fs/ntfs/runlist.c')
-rw-r--r--fs/ntfs/runlist.c55
1 files changed, 33 insertions, 22 deletions
diff --git a/fs/ntfs/runlist.c b/fs/ntfs/runlist.c
index e2665d011d72..061b5ff6b73c 100644
--- a/fs/ntfs/runlist.c
+++ b/fs/ntfs/runlist.c
@@ -158,17 +158,21 @@ static inline BOOL ntfs_are_rl_mergeable(runlist_element *dst,
158 BUG_ON(!dst); 158 BUG_ON(!dst);
159 BUG_ON(!src); 159 BUG_ON(!src);
160 160
161 if ((dst->lcn < 0) || (src->lcn < 0)) { /* Are we merging holes? */ 161 /* We can merge unmapped regions even if they are misaligned. */
162 if (dst->lcn == LCN_HOLE && src->lcn == LCN_HOLE) 162 if ((dst->lcn == LCN_RL_NOT_MAPPED) && (src->lcn == LCN_RL_NOT_MAPPED))
163 return TRUE; 163 return TRUE;
164 /* If the runs are misaligned, we cannot merge them. */
165 if ((dst->vcn + dst->length) != src->vcn)
164 return FALSE; 166 return FALSE;
165 } 167 /* If both runs are non-sparse and contiguous, we can merge them. */
166 if ((dst->lcn + dst->length) != src->lcn) /* Are the runs contiguous? */ 168 if ((dst->lcn >= 0) && (src->lcn >= 0) &&
167 return FALSE; 169 ((dst->lcn + dst->length) == src->lcn))
168 if ((dst->vcn + dst->length) != src->vcn) /* Are the runs misaligned? */ 170 return TRUE;
169 return FALSE; 171 /* If we are merging two holes, we can merge them. */
170 172 if ((dst->lcn == LCN_HOLE) && (src->lcn == LCN_HOLE))
171 return TRUE; 173 return TRUE;
174 /* Cannot merge. */
175 return FALSE;
172} 176}
173 177
174/** 178/**
@@ -214,14 +218,15 @@ static inline void __ntfs_rl_merge(runlist_element *dst, runlist_element *src)
214static inline runlist_element *ntfs_rl_append(runlist_element *dst, 218static inline runlist_element *ntfs_rl_append(runlist_element *dst,
215 int dsize, runlist_element *src, int ssize, int loc) 219 int dsize, runlist_element *src, int ssize, int loc)
216{ 220{
217 BOOL right; /* Right end of @src needs merging. */ 221 BOOL right = FALSE; /* Right end of @src needs merging. */
218 int marker; /* End of the inserted runs. */ 222 int marker; /* End of the inserted runs. */
219 223
220 BUG_ON(!dst); 224 BUG_ON(!dst);
221 BUG_ON(!src); 225 BUG_ON(!src);
222 226
223 /* First, check if the right hand end needs merging. */ 227 /* First, check if the right hand end needs merging. */
224 right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1); 228 if ((loc + 1) < dsize)
229 right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1);
225 230
226 /* Space required: @dst size + @src size, less one if we merged. */ 231 /* Space required: @dst size + @src size, less one if we merged. */
227 dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - right); 232 dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - right);
@@ -377,20 +382,21 @@ static inline runlist_element *ntfs_rl_replace(runlist_element *dst,
377 int dsize, runlist_element *src, int ssize, int loc) 382 int dsize, runlist_element *src, int ssize, int loc)
378{ 383{
379 BOOL left = FALSE; /* Left end of @src needs merging. */ 384 BOOL left = FALSE; /* Left end of @src needs merging. */
380 BOOL right; /* Right end of @src needs merging. */ 385 BOOL right = FALSE; /* Right end of @src needs merging. */
381 int tail; /* Start of tail of @dst. */ 386 int tail; /* Start of tail of @dst. */
382 int marker; /* End of the inserted runs. */ 387 int marker; /* End of the inserted runs. */
383 388
384 BUG_ON(!dst); 389 BUG_ON(!dst);
385 BUG_ON(!src); 390 BUG_ON(!src);
386 391
387 /* First, merge the left and right ends, if necessary. */ 392 /* First, see if the left and right ends need merging. */
388 right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1); 393 if ((loc + 1) < dsize)
394 right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1);
389 if (loc > 0) 395 if (loc > 0)
390 left = ntfs_are_rl_mergeable(dst + loc - 1, src); 396 left = ntfs_are_rl_mergeable(dst + loc - 1, src);
391 /* 397 /*
392 * Allocate some space. We will need less if the left, right, or both 398 * Allocate some space. We will need less if the left, right, or both
393 * ends were merged. 399 * ends get merged.
394 */ 400 */
395 dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left - right); 401 dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left - right);
396 if (IS_ERR(dst)) 402 if (IS_ERR(dst))
@@ -399,21 +405,26 @@ static inline runlist_element *ntfs_rl_replace(runlist_element *dst,
399 * We are guaranteed to succeed from here so can start modifying the 405 * We are guaranteed to succeed from here so can start modifying the
400 * original runlists. 406 * original runlists.
401 */ 407 */
408
409 /* First, merge the left and right ends, if necessary. */
402 if (right) 410 if (right)
403 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1); 411 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
404 if (left) 412 if (left)
405 __ntfs_rl_merge(dst + loc - 1, src); 413 __ntfs_rl_merge(dst + loc - 1, src);
406 /* 414 /*
407 * First run of @dst that needs to be moved out of the way to make 415 * Offset of the tail of @dst. This needs to be moved out of the way
408 * space for the runs to be copied from @src, i.e. the first run of the 416 * to make space for the runs to be copied from @src, i.e. the first
409 * tail of @dst. 417 * run of the tail of @dst.
418 * Nominally, @tail equals @loc + 1, i.e. location, skipping the
419 * replaced run. However, if @right, then one of @dst's runs is
420 * already merged into @src.
410 */ 421 */
411 tail = loc + right + 1; 422 tail = loc + right + 1;
412 /* 423 /*
413 * First run after the @src runs that have been inserted, i.e. where 424 * First run after the @src runs that have been inserted, i.e. where
414 * the tail of @dst needs to be moved to. 425 * the tail of @dst needs to be moved to.
415 * Nominally, marker equals @loc + @ssize, i.e. location + number of 426 * Nominally, @marker equals @loc + @ssize, i.e. location + number of
416 * runs in @src). However, if @left, then the first run in @src has 427 * runs in @src. However, if @left, then the first run in @src has
417 * been merged with one in @dst. 428 * been merged with one in @dst.
418 */ 429 */
419 marker = loc + ssize - left; 430 marker = loc + ssize - left;