X-Git-Url: https://git.openpandora.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;ds=sidebyside;f=fs%2Fntfs%2Frunlist.c;h=9afd72c7ad0db7c81f4487302971c2340cabecf0;hb=6f3a28f7d1f0a65a78443c273b6e8ec01becf301;hp=f5b2ac929081eb16c1f3bc0b83c3af295d240264;hpb=8ccc457722ba226ea72fca6f9ba3b54535d4749e;p=pandora-kernel.git diff --git a/fs/ntfs/runlist.c b/fs/ntfs/runlist.c index f5b2ac929081..9afd72c7ad0d 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 @@ -149,26 +149,30 @@ static inline runlist_element *ntfs_rl_realloc_nofail(runlist_element *rl, * * It is up to the caller to serialize access to the runlists @dst and @src. * - * Return: TRUE Success, the runlists can be merged. - * FALSE Failure, the runlists cannot be merged. + * Return: true Success, the runlists can be merged. + * false Failure, the runlists cannot be merged. */ -static inline BOOL ntfs_are_rl_mergeable(runlist_element *dst, +static inline bool ntfs_are_rl_mergeable(runlist_element *dst, runlist_element *src) { 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; - 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; + /* 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 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,42 +381,65 @@ 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; + signed delta; + 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. */ - dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left - right); - if (IS_ERR(dst)) - return dst; + /* + * Allocate some space. We will need less if the left, right, or both + * ends get merged. The -1 accounts for the run being replaced. + */ + delta = ssize - 1 - left - right; + if (delta > 0) { + dst = ntfs_rl_realloc(dst, dsize, dsize + delta); + if (IS_ERR(dst)) + return 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; } @@ -601,8 +620,8 @@ runlist_element *ntfs_runlists_merge(runlist_element *drl, ; { - BOOL start; - BOOL finish; + bool start; + bool finish; int ds = dend + 1; /* Number of elements in drl & srl */ int ss = sfinal - sstart + 1; @@ -616,7 +635,7 @@ runlist_element *ntfs_runlists_merge(runlist_element *drl, if (finish && !drl[dins].length) ss++; if (marker && (drl[dins].vcn + drl[dins].length > srl[send - 1].vcn)) - finish = FALSE; + finish = false; #if 0 ntfs_debug("dfinal = %i, dend = %i", dfinal, dend); ntfs_debug("sstart = %i, sfinal = %i, send = %i", sstart, sfinal, send); @@ -1115,7 +1134,7 @@ int ntfs_get_size_for_mapping_pairs(const ntfs_volume *vol, { LCN prev_lcn; int rls; - BOOL the_end = FALSE; + bool the_end = false; BUG_ON(first_vcn < 0); BUG_ON(last_vcn < -1); @@ -1149,7 +1168,7 @@ int ntfs_get_size_for_mapping_pairs(const ntfs_volume *vol, s64 s1 = last_vcn + 1; if (unlikely(rl[1].vcn > s1)) length = s1 - rl->vcn; - the_end = TRUE; + the_end = true; } delta = first_vcn - rl->vcn; /* Header byte + length. */ @@ -1185,7 +1204,7 @@ int ntfs_get_size_for_mapping_pairs(const ntfs_volume *vol, s64 s1 = last_vcn + 1; if (unlikely(rl[1].vcn > s1)) length = s1 - rl->vcn; - the_end = TRUE; + the_end = true; } /* Header byte + length. */ rls += 1 + ntfs_get_nr_significant_bytes(length); @@ -1308,7 +1327,7 @@ int ntfs_mapping_pairs_build(const ntfs_volume *vol, s8 *dst, LCN prev_lcn; s8 *dst_max, *dst_next; int err = -ENOSPC; - BOOL the_end = FALSE; + bool the_end = false; s8 len_len, lcn_len; BUG_ON(first_vcn < 0); @@ -1351,7 +1370,7 @@ int ntfs_mapping_pairs_build(const ntfs_volume *vol, s8 *dst, s64 s1 = last_vcn + 1; if (unlikely(rl[1].vcn > s1)) length = s1 - rl->vcn; - the_end = TRUE; + the_end = true; } delta = first_vcn - rl->vcn; /* Write length. */ @@ -1403,7 +1422,7 @@ int ntfs_mapping_pairs_build(const ntfs_volume *vol, s8 *dst, s64 s1 = last_vcn + 1; if (unlikely(rl[1].vcn > s1)) length = s1 - rl->vcn; - the_end = TRUE; + the_end = true; } /* Write length. */ len_len = ntfs_write_significant_bytes(dst + 1, dst_max, @@ -1522,7 +1541,7 @@ int ntfs_rl_truncate_nolock(const ntfs_volume *vol, runlist *const runlist, */ if (rl->length) { runlist_element *trl; - BOOL is_end; + bool is_end; ntfs_debug("Shrinking runlist."); /* Determine the runlist size. */ @@ -1536,11 +1555,11 @@ int ntfs_rl_truncate_nolock(const ntfs_volume *vol, runlist *const runlist, * If a run was partially truncated, make the following runlist * element a terminator. */ - is_end = FALSE; + is_end = false; if (rl->length) { rl++; if (!rl->length) - is_end = TRUE; + is_end = true; rl->vcn = new_length; rl->length = 0; } @@ -1629,7 +1648,7 @@ int ntfs_rl_punch_nolock(const ntfs_volume *vol, runlist *const runlist, s64 delta; runlist_element *rl, *rl_end, *rl_real_end, *trl; int old_size; - BOOL lcn_fixup = FALSE; + bool lcn_fixup = false; ntfs_debug("Entering for start 0x%llx, length 0x%llx.", (long long)start, (long long)length); @@ -1843,7 +1862,7 @@ split_end: if (rl->lcn >= 0) { rl->lcn -= delta; /* Need this in case the lcn just became negative. */ - lcn_fixup = TRUE; + lcn_fixup = true; } rl->length += delta; goto split_end;