aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorAnton Altaparmakov <aia21@cantab.net>2005-09-19 04:33:40 -0400
committerAnton Altaparmakov <aia21@cantab.net>2005-09-19 04:33:40 -0400
commit5c9f6de3b80ca46000bd1b63d892820f9ee32138 (patch)
treea4ed592a130837cf35052c6496073b4b93f58355
parent065d9cac98a5406ecd5a1368f8fd38f55739dee9 (diff)
NTFS: Fix various bugs in the runlist merging code. (Based on libntfs
changes by Richard Russon.) Signed-off-by: Anton Altaparmakov <aia21@cantab.net>
-rw-r--r--fs/ntfs/ChangeLog2
-rw-r--r--fs/ntfs/runlist.c132
2 files changed, 70 insertions, 64 deletions
diff --git a/fs/ntfs/ChangeLog b/fs/ntfs/ChangeLog
index 49eafbdb15c1..c7e9237379c2 100644
--- a/fs/ntfs/ChangeLog
+++ b/fs/ntfs/ChangeLog
@@ -92,6 +92,8 @@ ToDo/Notes:
92 an octal number to conform to how chmod(1) works, too. Thanks to 92 an octal number to conform to how chmod(1) works, too. Thanks to
93 Giuseppe Bilotta and Horst von Brand for pointing out the errors of 93 Giuseppe Bilotta and Horst von Brand for pointing out the errors of
94 my ways. 94 my ways.
95 - Fix various bugs in the runlist merging code. (Based on libntfs
96 changes by Richard Russon.)
95 97
962.1.23 - Implement extension of resident files and make writing safe as well as 982.1.23 - Implement extension of resident files and make writing safe as well as
97 many bug fixes, cleanups, and enhancements... 99 many bug fixes, cleanups, and enhancements...
diff --git a/fs/ntfs/runlist.c b/fs/ntfs/runlist.c
index f5b2ac929081..e2665d011d72 100644
--- a/fs/ntfs/runlist.c
+++ b/fs/ntfs/runlist.c
@@ -2,7 +2,7 @@
2 * runlist.c - NTFS runlist handling code. Part of the Linux-NTFS project. 2 * runlist.c - NTFS runlist handling code. Part of the Linux-NTFS project.
3 * 3 *
4 * Copyright (c) 2001-2005 Anton Altaparmakov 4 * Copyright (c) 2001-2005 Anton Altaparmakov
5 * Copyright (c) 2002 Richard Russon 5 * Copyright (c) 2002-2005 Richard Russon
6 * 6 *
7 * This program/include file is free software; you can redistribute it and/or 7 * This program/include file is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License as published 8 * modify it under the terms of the GNU General Public License as published
@@ -214,8 +214,8 @@ static inline void __ntfs_rl_merge(runlist_element *dst, runlist_element *src)
214static inline runlist_element *ntfs_rl_append(runlist_element *dst, 214static inline runlist_element *ntfs_rl_append(runlist_element *dst,
215 int dsize, runlist_element *src, int ssize, int loc) 215 int dsize, runlist_element *src, int ssize, int loc)
216{ 216{
217 BOOL right; 217 BOOL right; /* Right end of @src needs merging. */
218 int magic; 218 int marker; /* End of the inserted runs. */
219 219
220 BUG_ON(!dst); 220 BUG_ON(!dst);
221 BUG_ON(!src); 221 BUG_ON(!src);
@@ -236,18 +236,19 @@ static inline runlist_element *ntfs_rl_append(runlist_element *dst,
236 if (right) 236 if (right)
237 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1); 237 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
238 238
239 magic = loc + ssize; 239 /* First run after the @src runs that have been inserted. */
240 marker = loc + ssize + 1;
240 241
241 /* Move the tail of @dst out of the way, then copy in @src. */ 242 /* Move the tail of @dst out of the way, then copy in @src. */
242 ntfs_rl_mm(dst, magic + 1, loc + 1 + right, dsize - loc - 1 - right); 243 ntfs_rl_mm(dst, marker, loc + 1 + right, dsize - (loc + 1 + right));
243 ntfs_rl_mc(dst, loc + 1, src, 0, ssize); 244 ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
244 245
245 /* Adjust the size of the preceding hole. */ 246 /* Adjust the size of the preceding hole. */
246 dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn; 247 dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
247 248
248 /* We may have changed the length of the file, so fix the end marker */ 249 /* We may have changed the length of the file, so fix the end marker */
249 if (dst[magic + 1].lcn == LCN_ENOENT) 250 if (dst[marker].lcn == LCN_ENOENT)
250 dst[magic + 1].vcn = dst[magic].vcn + dst[magic].length; 251 dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
251 252
252 return dst; 253 return dst;
253} 254}
@@ -279,18 +280,17 @@ static inline runlist_element *ntfs_rl_append(runlist_element *dst,
279static inline runlist_element *ntfs_rl_insert(runlist_element *dst, 280static inline runlist_element *ntfs_rl_insert(runlist_element *dst,
280 int dsize, runlist_element *src, int ssize, int loc) 281 int dsize, runlist_element *src, int ssize, int loc)
281{ 282{
282 BOOL left = FALSE; 283 BOOL left = FALSE; /* Left end of @src needs merging. */
283 BOOL disc = FALSE; /* Discontinuity */ 284 BOOL disc = FALSE; /* Discontinuity between @dst and @src. */
284 BOOL hole = FALSE; /* Following a hole */ 285 int marker; /* End of the inserted runs. */
285 int magic;
286 286
287 BUG_ON(!dst); 287 BUG_ON(!dst);
288 BUG_ON(!src); 288 BUG_ON(!src);
289 289
290 /* disc => Discontinuity between the end of @dst and the start of @src. 290 /*
291 * This means we might need to insert a hole. 291 * disc => Discontinuity between the end of @dst and the start of @src.
292 * hole => @dst ends with a hole or an unmapped region which we can 292 * This means we might need to insert a "not mapped" run.
293 * extend to match the discontinuity. */ 293 */
294 if (loc == 0) 294 if (loc == 0)
295 disc = (src[0].vcn > 0); 295 disc = (src[0].vcn > 0);
296 else { 296 else {
@@ -303,58 +303,49 @@ static inline runlist_element *ntfs_rl_insert(runlist_element *dst,
303 merged_length += src->length; 303 merged_length += src->length;
304 304
305 disc = (src[0].vcn > dst[loc - 1].vcn + merged_length); 305 disc = (src[0].vcn > dst[loc - 1].vcn + merged_length);
306 if (disc)
307 hole = (dst[loc - 1].lcn == LCN_HOLE);
308 } 306 }
309 307 /*
310 /* Space required: @dst size + @src size, less one if we merged, plus 308 * Space required: @dst size + @src size, less one if we merged, plus
311 * one if there was a discontinuity, less one for a trailing hole. */ 309 * one if there was a discontinuity.
312 dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left + disc - hole); 310 */
311 dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left + disc);
313 if (IS_ERR(dst)) 312 if (IS_ERR(dst))
314 return dst; 313 return dst;
315 /* 314 /*
316 * We are guaranteed to succeed from here so can start modifying the 315 * We are guaranteed to succeed from here so can start modifying the
317 * original runlist. 316 * original runlist.
318 */ 317 */
319
320 if (left) 318 if (left)
321 __ntfs_rl_merge(dst + loc - 1, src); 319 __ntfs_rl_merge(dst + loc - 1, src);
322 320 /*
323 magic = loc + ssize - left + disc - hole; 321 * First run after the @src runs that have been inserted.
322 * Nominally, @marker equals @loc + @ssize, i.e. location + number of
323 * runs in @src. However, if @left, then the first run in @src has
324 * been merged with one in @dst. And if @disc, then @dst and @src do
325 * not meet and we need an extra run to fill the gap.
326 */
327 marker = loc + ssize - left + disc;
324 328
325 /* Move the tail of @dst out of the way, then copy in @src. */ 329 /* Move the tail of @dst out of the way, then copy in @src. */
326 ntfs_rl_mm(dst, magic, loc, dsize - loc); 330 ntfs_rl_mm(dst, marker, loc, dsize - loc);
327 ntfs_rl_mc(dst, loc + disc - hole, src, left, ssize - left); 331 ntfs_rl_mc(dst, loc + disc, src, left, ssize - left);
328 332
329 /* Adjust the VCN of the last run ... */ 333 /* Adjust the VCN of the first run after the insertion... */
330 if (dst[magic].lcn <= LCN_HOLE) 334 dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
331 dst[magic].vcn = dst[magic - 1].vcn + dst[magic - 1].length;
332 /* ... and the length. */ 335 /* ... and the length. */
333 if (dst[magic].lcn == LCN_HOLE || dst[magic].lcn == LCN_RL_NOT_MAPPED) 336 if (dst[marker].lcn == LCN_HOLE || dst[marker].lcn == LCN_RL_NOT_MAPPED)
334 dst[magic].length = dst[magic + 1].vcn - dst[magic].vcn; 337 dst[marker].length = dst[marker + 1].vcn - dst[marker].vcn;
335 338
336 /* Writing beyond the end of the file and there's a discontinuity. */ 339 /* Writing beyond the end of the file and there is a discontinuity. */
337 if (disc) { 340 if (disc) {
338 if (hole) 341 if (loc > 0) {
339 dst[loc - 1].length = dst[loc].vcn - dst[loc - 1].vcn; 342 dst[loc].vcn = dst[loc - 1].vcn + dst[loc - 1].length;
340 else { 343 dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
341 if (loc > 0) { 344 } else {
342 dst[loc].vcn = dst[loc - 1].vcn + 345 dst[loc].vcn = 0;
343 dst[loc - 1].length; 346 dst[loc].length = dst[loc + 1].vcn;
344 dst[loc].length = dst[loc + 1].vcn -
345 dst[loc].vcn;
346 } else {
347 dst[loc].vcn = 0;
348 dst[loc].length = dst[loc + 1].vcn;
349 }
350 dst[loc].lcn = LCN_RL_NOT_MAPPED;
351 } 347 }
352 348 dst[loc].lcn = LCN_RL_NOT_MAPPED;
353 magic += hole;
354
355 if (dst[magic].lcn == LCN_ENOENT)
356 dst[magic].vcn = dst[magic - 1].vcn +
357 dst[magic - 1].length;
358 } 349 }
359 return dst; 350 return dst;
360} 351}
@@ -385,9 +376,10 @@ static inline runlist_element *ntfs_rl_insert(runlist_element *dst,
385static inline runlist_element *ntfs_rl_replace(runlist_element *dst, 376static inline runlist_element *ntfs_rl_replace(runlist_element *dst,
386 int dsize, runlist_element *src, int ssize, int loc) 377 int dsize, runlist_element *src, int ssize, int loc)
387{ 378{
388 BOOL left = FALSE; 379 BOOL left = FALSE; /* Left end of @src needs merging. */
389 BOOL right; 380 BOOL right; /* Right end of @src needs merging. */
390 int magic; 381 int tail; /* Start of tail of @dst. */
382 int marker; /* End of the inserted runs. */
391 383
392 BUG_ON(!dst); 384 BUG_ON(!dst);
393 BUG_ON(!src); 385 BUG_ON(!src);
@@ -396,9 +388,10 @@ static inline runlist_element *ntfs_rl_replace(runlist_element *dst,
396 right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1); 388 right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1);
397 if (loc > 0) 389 if (loc > 0)
398 left = ntfs_are_rl_mergeable(dst + loc - 1, src); 390 left = ntfs_are_rl_mergeable(dst + loc - 1, src);
399 391 /*
400 /* Allocate some space. We'll need less if the left, right, or both 392 * Allocate some space. We will need less if the left, right, or both
401 * ends were merged. */ 393 * ends were merged.
394 */
402 dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left - right); 395 dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left - right);
403 if (IS_ERR(dst)) 396 if (IS_ERR(dst))
404 return dst; 397 return dst;
@@ -410,17 +403,28 @@ static inline runlist_element *ntfs_rl_replace(runlist_element *dst,
410 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1); 403 __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
411 if (left) 404 if (left)
412 __ntfs_rl_merge(dst + loc - 1, src); 405 __ntfs_rl_merge(dst + loc - 1, src);
413 406 /*
414 /* FIXME: What does this mean? (AIA) */ 407 * First run of @dst that needs to be moved out of the way to make
415 magic = loc + ssize - left; 408 * space for the runs to be copied from @src, i.e. the first run of the
409 * tail of @dst.
410 */
411 tail = loc + right + 1;
412 /*
413 * First run after the @src runs that have been inserted, i.e. where
414 * the tail of @dst needs to be moved to.
415 * Nominally, marker equals @loc + @ssize, i.e. location + number of
416 * runs in @src). However, if @left, then the first run in @src has
417 * been merged with one in @dst.
418 */
419 marker = loc + ssize - left;
416 420
417 /* Move the tail of @dst out of the way, then copy in @src. */ 421 /* Move the tail of @dst out of the way, then copy in @src. */
418 ntfs_rl_mm(dst, magic, loc + right + 1, dsize - loc - right - 1); 422 ntfs_rl_mm(dst, marker, tail, dsize - tail);
419 ntfs_rl_mc(dst, loc, src, left, ssize - left); 423 ntfs_rl_mc(dst, loc, src, left, ssize - left);
420 424
421 /* We may have changed the length of the file, so fix the end marker */ 425 /* We may have changed the length of the file, so fix the end marker. */
422 if (dst[magic].lcn == LCN_ENOENT) 426 if (dsize - tail > 0 && dst[marker].lcn == LCN_ENOENT)
423 dst[magic].vcn = dst[magic - 1].vcn + dst[magic - 1].length; 427 dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
424 return dst; 428 return dst;
425} 429}
426 430