* [PATCH v3 2/3] ntfs: add a runlist merge that leaves the source runlist to the caller
2026-10-02 4:34 [PATCH v3 0/3] ntfs: fix the undo path of $MFT data extension Matthias Goergens
2026-10-02 4:34 ` [PATCH v3 1/3] ntfs: do not use a stale runlist pointer when undoing $MFT extension Matthias Goergens
@ 2026-10-02 4:34 ` Matthias Goergens
2026-10-02 4:34 ` [PATCH v3 3/3] ntfs: balance the $MFT runlist lock in data extension error paths Matthias Goergens
2026-10-03 1:02 ` [PATCH v3 0/3] ntfs: fix the undo path of $MFT data extension Namjae Jeon
3 siblings, 0 replies; 5+ messages in thread
From: Matthias Goergens @ 2026-10-02 4:34 UTC (permalink / raw)
To: Namjae Jeon, Hyunchul Lee; +Cc: Baolin Liu, ntfs, linux-kernel
ntfs_runlists_merge() frees the source runlist once its runs are in the
destination. A caller that may have to undo the merge then has to work
out its runs again from the merged runlist, where the first and the
last of them may have been coalesced with neighbouring runs.
Add ntfs_runlists_merge_keep_src(), which neither modifies nor frees
the source runlist. For that, ntfs_rl_append() and ntfs_rl_replace()
now merge the right-hand end into the copied run in the destination
instead of into the last source run before copying it, and the merge
helpers take the source as const, so the compiler checks that none of
them writes to it. The merged runlist is the same as before.
For every caller, a source runlist without any mapped run, which the
merge already warns about, now fails with -EINVAL instead of carrying
on with nothing to insert: with no run copied, the right-hand merge
into the destination would index before the insertion point.
The next patch uses ntfs_runlists_merge_keep_src() to free exactly the
clusters it allocated when it has to undo an $MFT data extension.
Suggested-by: Hyunchul Lee <hyc.lee@gmail.com>
Cc: stable@vger.kernel.org # needed by the next patch
Signed-off-by: Matthias Goergens <matthias.goergens@gmail.com>
---
v3: new, for patch 3 (Hyunchul Lee).
I compared the merge code before and after this patch in userspace, on
three million random valid runlists covering all four merge helpers
and the right-hand merges in append and replace: the merged runlists
are identical, and ntfs_runlists_merge_keep_src() leaves the source as
it was. The harness, with the seed, is in the reproducer linked from
the cover letter.
fs/ntfs/runlist.c | 98 ++++++++++++++++++++++++++++++++++++++---------
fs/ntfs/runlist.h | 3 ++
2 files changed, 82 insertions(+), 19 deletions(-)
diff --git a/fs/ntfs/runlist.c b/fs/ntfs/runlist.c
index f13d28c15887..76ba6ab72b8a 100644
--- a/fs/ntfs/runlist.c
+++ b/fs/ntfs/runlist.c
@@ -47,7 +47,7 @@ static inline void ntfs_rl_mm(struct runlist_element *base, int dst, int src, in
* @srcbase.
*/
static inline void ntfs_rl_mc(struct runlist_element *dstbase, int dst,
- struct runlist_element *srcbase, int src, int size)
+ const struct runlist_element *srcbase, int src, int size)
{
if (likely(size > 0))
memcpy(dstbase + dst, srcbase + src, size * sizeof(*dstbase));
@@ -152,8 +152,8 @@ static inline struct runlist_element *ntfs_rl_realloc_nofail(struct runlist_elem
* Return: true Success, the runlists can be merged.
* false Failure, the runlists cannot be merged.
*/
-static inline bool ntfs_are_rl_mergeable(struct runlist_element *dst,
- struct runlist_element *src)
+static inline bool ntfs_are_rl_mergeable(const struct runlist_element *dst,
+ const struct runlist_element *src)
{
/* We can merge unmapped regions even if they are misaligned. */
if ((dst->lcn == LCN_RL_NOT_MAPPED) && (src->lcn == LCN_RL_NOT_MAPPED))
@@ -186,7 +186,8 @@ static inline bool ntfs_are_rl_mergeable(struct runlist_element *dst,
*
* It is up to the caller to serialize access to the runlists @dst and @src.
*/
-static inline void __ntfs_rl_merge(struct runlist_element *dst, struct runlist_element *src)
+static inline void __ntfs_rl_merge(struct runlist_element *dst,
+ const struct runlist_element *src)
{
dst->length += src->length;
}
@@ -214,10 +215,11 @@ static inline void __ntfs_rl_merge(struct runlist_element *dst, struct runlist_e
* On error, return -errno. Both runlists are left unmodified.
*/
static inline struct runlist_element *ntfs_rl_append(struct runlist_element *dst,
- int dsize, struct runlist_element *src, int ssize, int loc,
+ int dsize, const struct runlist_element *src, int ssize, int loc,
size_t *new_size)
{
bool right = false; /* Right end of @src needs merging. */
+ s64 right_length = 0; /* Length of the run merged at the right. */
int marker; /* End of the inserted runs. */
/* First, check if the right hand end needs merging. */
@@ -235,9 +237,9 @@ static inline struct runlist_element *ntfs_rl_append(struct runlist_element *dst
* original runlists.
*/
- /* First, merge the right hand end, if necessary. */
+ /* Remember the run that the right hand end absorbs, if any. */
if (right)
- __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
+ right_length = dst[loc + 1].length;
/* First run after the @src runs that have been inserted. */
marker = loc + ssize + 1;
@@ -246,6 +248,9 @@ static inline struct runlist_element *ntfs_rl_append(struct runlist_element *dst
ntfs_rl_mm(dst, marker, loc + 1 + right, dsize - (loc + 1 + right));
ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
+ /* Merge the right hand end into the copy, leaving @src intact. */
+ dst[marker - 1].length += right_length;
+
/* Adjust the size of the preceding hole. */
dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
@@ -279,7 +284,7 @@ static inline struct runlist_element *ntfs_rl_append(struct runlist_element *dst
* On error, return -errno. Both runlists are left unmodified.
*/
static inline struct runlist_element *ntfs_rl_insert(struct runlist_element *dst,
- int dsize, struct runlist_element *src, int ssize, int loc,
+ int dsize, const struct runlist_element *src, int ssize, int loc,
size_t *new_size)
{
bool left = false; /* Left end of @src needs merging. */
@@ -374,12 +379,13 @@ static inline struct runlist_element *ntfs_rl_insert(struct runlist_element *dst
* On error, return -errno. Both runlists are left unmodified.
*/
static inline struct runlist_element *ntfs_rl_replace(struct runlist_element *dst,
- int dsize, struct runlist_element *src, int ssize, int loc,
+ int dsize, const struct runlist_element *src, int ssize, int loc,
size_t *new_size)
{
int delta;
bool left = false; /* Left end of @src needs merging. */
bool right = false; /* Right end of @src needs merging. */
+ s64 right_length = 0; /* Length of the run merged at the right. */
int tail; /* Start of tail of @dst. */
int marker; /* End of the inserted runs. */
@@ -405,9 +411,12 @@ static inline struct runlist_element *ntfs_rl_replace(struct runlist_element *ds
* original runlists.
*/
- /* First, merge the left and right ends, if necessary. */
+ /*
+ * Remember the run that the right hand end absorbs, if any, then
+ * merge the left hand end.
+ */
if (right)
- __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
+ right_length = dst[loc + 1].length;
if (left)
__ntfs_rl_merge(dst + loc - 1, src);
/*
@@ -432,6 +441,13 @@ static inline struct runlist_element *ntfs_rl_replace(struct runlist_element *ds
ntfs_rl_mm(dst, marker, tail, dsize - tail);
ntfs_rl_mc(dst, loc, src, left, ssize - left);
+ /*
+ * Merge the right hand end into the last run of @src, now in @dst at
+ * @marker - 1 (or into @dst[@loc - 1] if that absorbed all of @src),
+ * leaving @src intact.
+ */
+ dst[marker - 1].length += right_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;
@@ -461,7 +477,7 @@ static inline struct runlist_element *ntfs_rl_replace(struct runlist_element *ds
* On error, return -errno. Both runlists are left unmodified.
*/
static inline struct runlist_element *ntfs_rl_split(struct runlist_element *dst, int dsize,
- struct runlist_element *src, int ssize, int loc,
+ const struct runlist_element *src, int ssize, int loc,
size_t *new_size)
{
/* Space required: @dst size + @src size + one new hole. */
@@ -488,11 +504,12 @@ static inline struct runlist_element *ntfs_rl_split(struct runlist_element *dst,
}
/*
- * ntfs_runlists_merge - merge two runlists into one
+ * __ntfs_runlists_merge - merge two runlists into one
* @d_runlist: destination runlist structure to merge into
* @srl: source runlist to merge from
* @s_rl_count: number of elements in @srl (0 to auto-detect)
* @new_rl_count: on success, set to the new combined runlist size
+ * @keep_srl: leave @srl to the caller instead of deallocating it
*
* First we sanity check the two runlists @srl and @drl to make sure that they
* are sensible and can be merged. The runlist @srl must be either after the
@@ -515,13 +532,14 @@ static inline struct runlist_element *ntfs_rl_split(struct runlist_element *dst,
* On success, return a pointer to the new, combined, runlist. Note, both
* runlists @drl and @srl are deallocated before returning so you cannot use
* the pointers for anything any more. (Strictly speaking the returned runlist
- * may be the same as @dst but this is irrelevant.)
+ * may be the same as @dst but this is irrelevant.) If @keep_srl is true,
+ * @srl is neither modified nor deallocated, and @drl must not be NULL.
*
* On error, return -errno. Both runlists are left unmodified.
*/
-struct runlist_element *ntfs_runlists_merge(struct runlist *d_runlist,
- struct runlist_element *srl, size_t s_rl_count,
- size_t *new_rl_count)
+static struct runlist_element *__ntfs_runlists_merge(struct runlist *d_runlist,
+ struct runlist_element *srl, size_t s_rl_count,
+ size_t *new_rl_count, bool keep_srl)
{
int di, si; /* Current index into @[ds]rl. */
int sstart; /* First index with lcn > LCN_RL_NOT_MAPPED. */
@@ -553,6 +571,8 @@ struct runlist_element *ntfs_runlists_merge(struct runlist *d_runlist,
/* Check for the case where the first mapping is being done now. */
if (unlikely(!drl)) {
+ if (WARN_ON(keep_srl))
+ return ERR_PTR(-EINVAL);
drl = srl;
/* Complete the source runlist if necessary. */
if (unlikely(drl[0].vcn)) {
@@ -582,7 +602,8 @@ struct runlist_element *ntfs_runlists_merge(struct runlist *d_runlist,
si++;
/* Can't have an entirely unmapped source runlist. */
- WARN_ON(!srl[si].length);
+ if (WARN_ON(!srl[si].length))
+ return ERR_PTR(-EINVAL);
/* Record the starting points. */
sstart = si;
@@ -652,7 +673,8 @@ struct runlist_element *ntfs_runlists_merge(struct runlist *d_runlist,
ntfs_error(NULL, "Merge failed.");
return drl;
}
- kvfree(srl);
+ if (!keep_srl)
+ kvfree(srl);
if (marker) {
ntfs_debug("Triggering marker code.");
for (ds = dend; drl[ds].length; ds++)
@@ -713,6 +735,44 @@ struct runlist_element *ntfs_runlists_merge(struct runlist *d_runlist,
return drl;
}
+/*
+ * ntfs_runlists_merge - merge two runlists into one
+ * @d_runlist: destination runlist structure to merge into
+ * @srl: source runlist to merge from, deallocated on success
+ * @s_rl_count: number of elements in @srl (0 to auto-detect)
+ * @new_rl_count: on success, set to the new combined runlist size
+ *
+ * See __ntfs_runlists_merge().
+ */
+struct runlist_element *ntfs_runlists_merge(struct runlist *d_runlist,
+ struct runlist_element *srl, size_t s_rl_count,
+ size_t *new_rl_count)
+{
+ return __ntfs_runlists_merge(d_runlist, srl, s_rl_count, new_rl_count,
+ false);
+}
+
+/*
+ * ntfs_runlists_merge_keep_src - merge two runlists, keeping the source
+ * @d_runlist: destination runlist structure to merge into, not empty
+ * @srl: source runlist to merge from
+ * @s_rl_count: number of elements in @srl (0 to auto-detect)
+ * @new_rl_count: on success, set to the new combined runlist size
+ *
+ * Like ntfs_runlists_merge(), but @srl is neither modified nor deallocated,
+ * on success or on error, and remains the caller's to kvfree(). Even when
+ * runs of @srl are coalesced with runs of @d_runlist, @srl keeps describing
+ * exactly its own runs, e.g. the clusters a caller has to free to undo the
+ * merge.
+ */
+struct runlist_element *ntfs_runlists_merge_keep_src(struct runlist *d_runlist,
+ struct runlist_element *srl, size_t s_rl_count,
+ size_t *new_rl_count)
+{
+ return __ntfs_runlists_merge(d_runlist, srl, s_rl_count, new_rl_count,
+ true);
+}
+
/*
* ntfs_mapping_pairs_decompress - convert mapping pairs array to runlist
* @vol: ntfs volume
diff --git a/fs/ntfs/runlist.h b/fs/ntfs/runlist.h
index cc92e09fbf68..0d4c32b1a338 100644
--- a/fs/ntfs/runlist.h
+++ b/fs/ntfs/runlist.h
@@ -68,6 +68,9 @@ enum {
struct runlist_element *ntfs_runlists_merge(struct runlist *d_runlist,
struct runlist_element *srl, size_t s_rl_count,
size_t *new_rl_count);
+struct runlist_element *ntfs_runlists_merge_keep_src(struct runlist *d_runlist,
+ struct runlist_element *srl, size_t s_rl_count,
+ size_t *new_rl_count);
struct runlist_element *ntfs_mapping_pairs_decompress(const struct ntfs_volume *vol,
const struct attr_record *attr, struct runlist *old_runlist,
size_t *new_rl_count);
--
2.56.0
^ permalink raw reply [flat|nested] 5+ messages in thread* [PATCH v3 3/3] ntfs: balance the $MFT runlist lock in data extension error paths
2026-10-02 4:34 [PATCH v3 0/3] ntfs: fix the undo path of $MFT data extension Matthias Goergens
2026-10-02 4:34 ` [PATCH v3 1/3] ntfs: do not use a stale runlist pointer when undoing $MFT extension Matthias Goergens
2026-10-02 4:34 ` [PATCH v3 2/3] ntfs: add a runlist merge that leaves the source runlist to the caller Matthias Goergens
@ 2026-10-02 4:34 ` Matthias Goergens
2026-10-03 1:02 ` [PATCH v3 0/3] ntfs: fix the undo path of $MFT data extension Namjae Jeon
3 siblings, 0 replies; 5+ messages in thread
From: Matthias Goergens @ 2026-10-02 4:34 UTC (permalink / raw)
To: Namjae Jeon, Hyunchul Lee; +Cc: Baolin Liu, ntfs, linux-kernel
ntfs_mft_data_extend_allocation_nolock() drops the $MFT runlist lock
before allocating clusters, and every path into undo_alloc arrives
without it, except a map_mft_record() failure, which takes it first.
undo_alloc never releases it, so the lock leaks and the next $MFT
extension and $MFT writeback hang. The restore_undo_alloc failure
path, on the other hand, releases the lock without holding it. And
undo_alloc frees the clusters with ntfs_cluster_free() and truncates
the runlist without the lock, although both require it.
Enter undo_alloc without the lock on every path. Merge the new clusters
with ntfs_runlists_merge_keep_src() and keep the runlist that
ntfs_cluster_alloc() returned until the extension is complete. On
failure, undo_alloc truncates $MFT's runlist under the lock and, after
dropping it, frees the clusters from the kept runlist with
ntfs_cluster_free_from_rl(). That keeps lcnbmp_lock outside the runlist
lock, the order given by the comment before the cluster allocation.
Unlike ntfs_cluster_free() on a volume mounted with -o discard, this
does not issue discards for the clusters, which were never written; the
runlist merge failure path already frees them the same way. If the
truncation fails, the runlist may still reference the clusters, so they
stay allocated and the volume is marked for chkdsk; at this call site
the truncation only shrinks the runlist and cannot fail today.
A shorter fix would keep calling ntfs_cluster_free() on the live
runlist without the lock, relying on $MFT's runlist being fully mapped
and changed only by this function under mrec_lock. That breaks
ntfs_cluster_free()'s documented locking rule on an argument about the
rest of the driver, so this patch does not do that.
Fixes: 115380f9a2f9 ("ntfs: update mft operations")
Cc: stable@vger.kernel.org
Signed-off-by: Matthias Goergens <matthias.goergens@gmail.com>
---
v3: free the clusters from the runlist that ntfs_cluster_alloc()
returned, kept intact by the merge from patch 2, instead of from a copy
of the new runs made with ntfs_mft_copy_tail() in undo_alloc (Hyunchul
Lee). The undo path no longer allocates, so the case where the copy
failed and the clusters stayed allocated is gone. A copy made before
the merge would also have worked, but would add an allocation to every
$MFT extension.
v2: do not free the clusters if ntfs_rl_truncate_nolock() fails
(Hyunchul Lee).
Without this patch, a forced map_mft_record() failure gives "WARNING:
lock held when returning to user space" for the $MFT runlist lock, and
the next file create and $MFT writeback block on it. A forced lookup
failure in restore_undo_alloc gives "bad unlock balance". With it, the
create fails with the injected error, lockdep stays quiet and the
volume keeps working, also when the merge is forced to fail. With the
truncation forced to fail, nothing is freed that $MFT's runlist still
maps. A debug check in undo_alloc found, in every undo of these runs,
that the kept runlist describes exactly the runs taken off $MFT's
runlist. $MFT growth on a nearly full, fragmented volume behaves as
before.
fs/ntfs/mft.c | 50 ++++++++++++++++++++++++++++++++++----------------
1 file changed, 34 insertions(+), 16 deletions(-)
diff --git a/fs/ntfs/mft.c b/fs/ntfs/mft.c
index c2339acc6319..89288b794348 100644
--- a/fs/ntfs/mft.c
+++ b/fs/ntfs/mft.c
@@ -1791,7 +1791,7 @@ static int ntfs_mft_data_extend_allocation_nolock(struct ntfs_volume *vol)
s64 min_nr, nr, ll;
unsigned long flags;
struct ntfs_inode *mft_ni;
- struct runlist_element *rl, *rl2;
+ struct runlist_element *rl, *rl2, *alloc_rl;
struct ntfs_attr_search_ctx *ctx = NULL;
struct mft_record *mrec;
struct attr_record *a = NULL;
@@ -1859,15 +1859,15 @@ static int ntfs_mft_data_extend_allocation_nolock(struct ntfs_volume *vol)
up_write(&mft_ni->runlist.lock);
do {
- rl2 = ntfs_cluster_alloc(vol, old_last_vcn, nr, lcn, MFT_ZONE,
- true, false, false);
- if (!IS_ERR(rl2))
+ alloc_rl = ntfs_cluster_alloc(vol, old_last_vcn, nr, lcn,
+ MFT_ZONE, true, false, false);
+ if (!IS_ERR(alloc_rl))
break;
- if (PTR_ERR(rl2) != -ENOSPC || nr == min_nr) {
+ if (PTR_ERR(alloc_rl) != -ENOSPC || nr == min_nr) {
ntfs_error(vol->sb,
"Failed to allocate the minimal number of clusters (%lli) for the mft data attribute.",
nr);
- return PTR_ERR(rl2);
+ return PTR_ERR(alloc_rl);
}
/*
* There is not enough space to do the allocation, but there
@@ -1878,17 +1878,22 @@ static int ntfs_mft_data_extend_allocation_nolock(struct ntfs_volume *vol)
ntfs_debug("Retrying mft data allocation with minimal cluster count %lli.", nr);
} while (1);
+ /*
+ * Keep @alloc_rl until the extension is complete: it describes exactly
+ * the new clusters, which undo_alloc frees if a later step fails.
+ */
down_write(&mft_ni->runlist.lock);
- rl = ntfs_runlists_merge(&mft_ni->runlist, rl2, 0, &new_rl_count);
+ rl = ntfs_runlists_merge_keep_src(&mft_ni->runlist, alloc_rl, 0,
+ &new_rl_count);
if (IS_ERR(rl)) {
up_write(&mft_ni->runlist.lock);
ntfs_error(vol->sb, "Failed to merge runlists for mft data attribute.");
- if (ntfs_cluster_free_from_rl(vol, rl2)) {
+ if (ntfs_cluster_free_from_rl(vol, alloc_rl)) {
ntfs_error(vol->sb,
"Failed to deallocate clusters from the mft data attribute.%s", es);
NVolSetErrors(vol);
}
- kvfree(rl2);
+ kvfree(alloc_rl);
return PTR_ERR(rl);
}
mft_ni->runlist.rl = rl;
@@ -1904,7 +1909,6 @@ static int ntfs_mft_data_extend_allocation_nolock(struct ntfs_volume *vol)
if (IS_ERR(mrec)) {
ntfs_error(vol->sb, "Failed to map mft record.");
ret = PTR_ERR(mrec);
- down_write(&mft_ni->runlist.lock);
goto undo_alloc;
}
ctx = ntfs_attr_get_search_ctx(mft_ni, mrec);
@@ -2002,6 +2006,7 @@ static int ntfs_mft_data_extend_allocation_nolock(struct ntfs_volume *vol)
mark_mft_record_dirty(ctx->ntfs_ino);
ntfs_attr_put_search_ctx(ctx);
unmap_mft_record(mft_ni);
+ kvfree(alloc_rl);
ntfs_debug("Done.");
return 0;
restore_undo_alloc:
@@ -2015,7 +2020,7 @@ static int ntfs_mft_data_extend_allocation_nolock(struct ntfs_volume *vol)
write_unlock_irqrestore(&mft_ni->size_lock, flags);
ntfs_attr_put_search_ctx(ctx);
unmap_mft_record(mft_ni);
- up_write(&mft_ni->runlist.lock);
+ kvfree(alloc_rl);
/*
* The only thing that is now wrong is ->allocated_size of the
* base attribute extent which chkdsk should be able to fix.
@@ -2026,15 +2031,28 @@ static int ntfs_mft_data_extend_allocation_nolock(struct ntfs_volume *vol)
ctx->attr->data.non_resident.highest_vcn =
cpu_to_le64(old_last_vcn - 1);
undo_alloc:
- if (ntfs_cluster_free(mft_ni, old_last_vcn, -1, ctx) < 0) {
- ntfs_error(vol->sb, "Failed to free clusters from mft data attribute.%s", es);
- NVolSetErrors(vol);
- }
-
+ /*
+ * Entered without the runlist lock. Take the new runs off the
+ * runlist under it, and free their clusters from @alloc_rl once it
+ * is dropped, as lcnbmp_lock nests outside it (see above).
+ */
+ down_write(&mft_ni->runlist.lock);
if (ntfs_rl_truncate_nolock(vol, &mft_ni->runlist, old_last_vcn)) {
ntfs_error(vol->sb, "Failed to truncate mft data attribute runlist.%s", es);
NVolSetErrors(vol);
+ /*
+ * The runlist may still reference the clusters, so leave them
+ * allocated until chkdsk.
+ */
+ kvfree(alloc_rl);
+ alloc_rl = NULL;
+ }
+ up_write(&mft_ni->runlist.lock);
+ if (ntfs_cluster_free_from_rl(vol, alloc_rl)) {
+ ntfs_error(vol->sb, "Failed to free clusters from mft data attribute.%s", es);
+ NVolSetErrors(vol);
}
+ kvfree(alloc_rl);
if (mp_extended && ntfs_attr_update_mapping_pairs(mft_ni, 0)) {
ntfs_error(vol->sb, "Failed to restore mapping pairs.%s",
es);
--
2.56.0
^ permalink raw reply [flat|nested] 5+ messages in thread