* [RFC PATCH v2 1/2] ext4: fast commit: track disjoint modified ranges per inode
[not found] ` <CGME20260623082331epcms2p4798e9d26b06f9a005bcca7b2edf395d3@epcms2p8>
@ 2026-06-23 8:25 ` Daejun Park
2026-06-23 8:26 ` [RFC PATCH v2 2/2] ext4: fast commit: allocate the range array lazily Daejun Park
1 sibling, 0 replies; 3+ messages in thread
From: Daejun Park @ 2026-06-23 8:25 UTC (permalink / raw)
To: tytso, adilger.kernel
Cc: me, libaokun, harshadshirwadkar, yi.zhang, ojaswin, linux-ext4,
linux-kernel, Daejun Park
Fast commit tracks a single coalesced logical range per inode
(i_fc_lblk_start .. i_fc_lblk_len). When an inode is modified at
several disjoint offsets between two commits (e.g. random writes), that
range widens to span [min, max] of all touched offsets. At commit time
ext4_fc_snapshot_inode_data() walks that whole span through the extent
status tree, emitting an ADD_RANGE per mapped segment and a DEL_RANGE
per hole -- including the unmodified ones. On scattered allocations
this produces hundreds to thousands of ranges per commit and exceeds
EXT4_FC_SNAPSHOT_MAX_RANGES, which fails the snapshot and falls back to
a full jbd2 commit -- the heavy path fast commit is meant to avoid.
Replace the single range with a bounded set of up to EXT4_FC_MAX_RANGES
(16) sorted, mutually disjoint ranges. ext4_fc_range_add() inserts and
merges into it; on overflow the two ranges separated by the smallest
gap are coalesced, so the worst case degrades to the old single-span
behaviour. ext4_fc_snapshot_inode_data() now walks only the tracked
ranges. The on-disk fast-commit (TLV) format is unchanged.
On a sparse random-write workload (1 GiB span, 16 disjoint 4 KiB writes
per fsync, 300 fsyncs, dev 7.1.0-rc4): ranges per commit 1095 -> 16,
full-commit fallback 76% -> 0.7%, snap_fail_ranges_cap 226 -> 0.
Signed-off-by: Daejun Park <daejun7.park@samsung.com>
---
fs/ext4/ext4.h | 31 ++++++--
fs/ext4/fast_commit.c | 165 +++++++++++++++++++++++++++++++++---------
2 files changed, 156 insertions(+), 40 deletions(-)
diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
index ddc903738c6b..8e93d30766fd 100644
--- a/fs/ext4/ext4.h
+++ b/fs/ext4/ext4.h
@@ -1042,6 +1042,20 @@ enum ext4_fc_snap_err {
EXT4_FC_SNAP_ERR_INODE_LOC,
};
+/*
+ * Maximum number of disjoint logical-block ranges tracked per inode for a
+ * single fast commit. Scattered allocations that exceed this get their two
+ * closest ranges merged (see ext4_fc_range_add()), degrading gracefully to
+ * the old single coalesced-range behaviour.
+ */
+#define EXT4_FC_MAX_RANGES 16
+
+/* In-memory record of an lblk range modified in the current fast commit. */
+struct ext4_fc_lblk_range {
+ ext4_lblk_t start;
+ ext4_lblk_t len;
+};
+
/*
* fourth extended file system inode data in memory
*/
@@ -1091,11 +1105,16 @@ struct ext4_inode_info {
* protected by sbi->s_fc_lock.
*/
- /* Start of lblk range that needs to be committed in this fast commit */
- ext4_lblk_t i_fc_lblk_start;
-
- /* End of lblk range that needs to be committed in this fast commit */
- ext4_lblk_t i_fc_lblk_len;
+ /*
+ * Disjoint lblk ranges modified in this fast commit. Tracking the
+ * actual modified ranges (instead of one coalesced [min,max]) avoids
+ * snapshotting the whole spanned extent map for scattered allocations.
+ * Sorted by start, mutually disjoint. Bounded by EXT4_FC_MAX_RANGES;
+ * the extra slot is transient room used while inserting before an
+ * overflow merge. Protected by i_fc_lock.
+ */
+ struct ext4_fc_lblk_range i_fc_ranges[EXT4_FC_MAX_RANGES + 1];
+ unsigned int i_fc_nr_ranges;
/*
* Commit-time fast commit snapshots.
@@ -1116,7 +1135,7 @@ struct ext4_inode_info {
spinlock_t i_raw_lock; /* protects updates to the raw inode */
/*
- * Protect concurrent accesses on i_fc_lblk_start, i_fc_lblk_len
+ * Protect concurrent accesses on i_fc_ranges, i_fc_nr_ranges
* and inode's EXT4_FC_STATE_COMMITTING state bit.
*/
spinlock_t i_fc_lock;
diff --git a/fs/ext4/fast_commit.c b/fs/ext4/fast_commit.c
index 4ef796b9b6cb..1ea3742a55b1 100644
--- a/fs/ext4/fast_commit.c
+++ b/fs/ext4/fast_commit.c
@@ -222,8 +222,7 @@ static inline void ext4_fc_reset_inode(struct inode *inode)
{
struct ext4_inode_info *ei = EXT4_I(inode);
- ei->i_fc_lblk_start = 0;
- ei->i_fc_lblk_len = 0;
+ ei->i_fc_nr_ranges = 0;
}
void ext4_fc_init_inode(struct inode *inode)
@@ -582,7 +581,7 @@ static int __track_inode(handle_t *handle, struct inode *inode, void *arg,
if (update)
return -EEXIST;
- EXT4_I(inode)->i_fc_lblk_len = 0;
+ EXT4_I(inode)->i_fc_nr_ranges = 0;
return 0;
}
@@ -622,12 +621,74 @@ struct __track_range_args {
ext4_lblk_t start, end;
};
+/*
+ * Record that logical block range [start, end] was modified in the current
+ * fast commit. Maintains a small, bounded set of sorted, mutually disjoint
+ * ranges, merging the new range with any it overlaps or is adjacent to. When
+ * the set would exceed EXT4_FC_MAX_RANGES, the consecutive pair separated by
+ * the smallest gap is merged (absorbing that gap), so the worst case degrades
+ * gracefully to the old single coalesced-range behaviour. Tracking the actual
+ * modified ranges (rather than one [min,max] span) keeps
+ * ext4_fc_snapshot_inode_data() from snapshotting the whole spanned extent map
+ * on scattered allocations. Caller holds ei->i_fc_lock; ei->i_fc_ranges is
+ * non-NULL with room for EXT4_FC_MAX_RANGES + 1 entries.
+ */
+static void ext4_fc_range_add(struct ext4_inode_info *ei,
+ ext4_lblk_t start, ext4_lblk_t end)
+{
+ struct ext4_fc_lblk_range *r = ei->i_fc_ranges;
+ unsigned int n = ei->i_fc_nr_ranges;
+ unsigned int i, j;
+
+ /* Skip ranges lying entirely before [start - 1] (no overlap/adjacency). */
+ i = 0;
+ while (i < n && r[i].start + r[i].len < start)
+ i++;
+
+ /* Absorb every range overlapping or adjacent to the growing [start,end]. */
+ j = i;
+ while (j < n && r[j].start <= end + 1) {
+ if (r[j].start < start)
+ start = r[j].start;
+ if (r[j].start + r[j].len - 1 > end)
+ end = r[j].start + r[j].len - 1;
+ j++;
+ }
+
+ /* Replace r[i..j-1] with the merged range (j == i is a plain insert). */
+ if (j != i + 1)
+ memmove(&r[i + 1], &r[j], (n - j) * sizeof(*r));
+ r[i].start = start;
+ r[i].len = end - start + 1;
+ ei->i_fc_nr_ranges = n - (j - i) + 1;
+
+ /* Overflow: merge the consecutive pair separated by the smallest gap. */
+ while (ei->i_fc_nr_ranges > EXT4_FC_MAX_RANGES) {
+ ext4_lblk_t best_gap = ~0U;
+ unsigned int best = 0;
+
+ n = ei->i_fc_nr_ranges;
+ for (i = 0; i + 1 < n; i++) {
+ ext4_lblk_t gap = r[i + 1].start -
+ (r[i].start + r[i].len);
+
+ if (gap < best_gap) {
+ best_gap = gap;
+ best = i;
+ }
+ }
+ r[best].len = r[best + 1].start + r[best + 1].len - r[best].start;
+ memmove(&r[best + 1], &r[best + 2],
+ (n - best - 2) * sizeof(*r));
+ ei->i_fc_nr_ranges = n - 1;
+ }
+}
+
/* __track_fn for tracking data updates */
static int __track_range(handle_t *handle, struct inode *inode, void *arg,
bool update)
{
struct ext4_inode_info *ei = EXT4_I(inode);
- ext4_lblk_t oldstart;
struct __track_range_args *__arg =
(struct __track_range_args *)arg;
@@ -636,17 +697,16 @@ static int __track_range(handle_t *handle, struct inode *inode, void *arg,
return -ECANCELED;
}
- oldstart = ei->i_fc_lblk_start;
+ /*
+ * A sub-block punch hole rounds up the start and down the end, passing
+ * end == start - 1: no whole block changed, so there is nothing to
+ * track. (ext4_fc_track_template has already reset the range set for a
+ * new transaction.)
+ */
+ if (__arg->end < __arg->start)
+ return 0;
- if (update && ei->i_fc_lblk_len > 0) {
- ei->i_fc_lblk_start = min(ei->i_fc_lblk_start, __arg->start);
- ei->i_fc_lblk_len =
- max(oldstart + ei->i_fc_lblk_len - 1, __arg->end) -
- ei->i_fc_lblk_start + 1;
- } else {
- ei->i_fc_lblk_start = __arg->start;
- ei->i_fc_lblk_len = __arg->end - __arg->start + 1;
- }
+ ext4_fc_range_add(ei, __arg->start, __arg->end);
return 0;
}
@@ -994,31 +1054,26 @@ static void ext4_fc_free_inode_snap(struct inode *inode)
ei->i_fc_snap = NULL;
}
-static int ext4_fc_snapshot_inode_data(struct inode *inode,
+/*
+ * Snapshot one modified lblk range [start_lblk, end_lblk] into @ranges by
+ * walking the extent status tree, emitting an ADD_RANGE per mapped segment and
+ * a DEL_RANGE per hole. *nr_ranges accumulates the number of ranges produced
+ * for this inode across calls; together with nr_ranges_total (ranges already
+ * produced by earlier inodes in this commit) it is bounded against
+ * EXT4_FC_SNAPSHOT_MAX_RANGES.
+ */
+static int ext4_fc_snapshot_lblk_range(struct inode *inode,
+ ext4_lblk_t start_lblk,
+ ext4_lblk_t end_lblk,
struct list_head *ranges,
unsigned int nr_ranges_total,
- unsigned int *nr_rangesp,
+ unsigned int *nr_ranges,
int *snap_err)
{
- struct ext4_inode_info *ei = EXT4_I(inode);
struct ext4_fc_snap_stats *stats =
&EXT4_SB(inode->i_sb)->s_fc_snap_stats;
- ext4_lblk_t start_lblk, end_lblk, cur_lblk;
- unsigned int nr_ranges = 0;
+ ext4_lblk_t cur_lblk = start_lblk;
- spin_lock(&ei->i_fc_lock);
- if (ei->i_fc_lblk_len == 0) {
- spin_unlock(&ei->i_fc_lock);
- if (nr_rangesp)
- *nr_rangesp = 0;
- return 0;
- }
- start_lblk = ei->i_fc_lblk_start;
- end_lblk = ei->i_fc_lblk_start + ei->i_fc_lblk_len - 1;
- ei->i_fc_lblk_len = 0;
- spin_unlock(&ei->i_fc_lock);
-
- cur_lblk = start_lblk;
ext4_debug("snapshot data ranges %u-%u for inode %llu\n",
start_lblk, end_lblk,
(unsigned long long)inode->i_ino);
@@ -1050,7 +1105,7 @@ static int ext4_fc_snapshot_inode_data(struct inode *inode,
continue;
}
- if (nr_ranges_total + nr_ranges >= EXT4_FC_SNAPSHOT_MAX_RANGES) {
+ if (nr_ranges_total + *nr_ranges >= EXT4_FC_SNAPSHOT_MAX_RANGES) {
atomic64_inc(&stats->snap_fail_ranges_cap);
ext4_fc_set_snap_err(snap_err,
EXT4_FC_SNAP_ERR_RANGES_CAP);
@@ -1063,7 +1118,7 @@ static int ext4_fc_snapshot_inode_data(struct inode *inode,
ext4_fc_set_snap_err(snap_err, EXT4_FC_SNAP_ERR_NOMEM);
return -ENOMEM;
}
- nr_ranges++;
+ (*nr_ranges)++;
range->lblk = cur_lblk;
range->len = len;
@@ -1101,6 +1156,48 @@ static int ext4_fc_snapshot_inode_data(struct inode *inode,
cur_lblk += range->len;
}
+ return 0;
+}
+
+static int ext4_fc_snapshot_inode_data(struct inode *inode,
+ struct list_head *ranges,
+ unsigned int nr_ranges_total,
+ unsigned int *nr_rangesp,
+ int *snap_err)
+{
+ struct ext4_inode_info *ei = EXT4_I(inode);
+ struct ext4_fc_lblk_range tracked[EXT4_FC_MAX_RANGES + 1];
+ unsigned int nr_ranges = 0, nr_tracked, t;
+ int ret;
+
+ spin_lock(&ei->i_fc_lock);
+ nr_tracked = ei->i_fc_nr_ranges;
+ if (nr_tracked == 0) {
+ spin_unlock(&ei->i_fc_lock);
+ if (nr_rangesp)
+ *nr_rangesp = 0;
+ return 0;
+ }
+ memcpy(tracked, ei->i_fc_ranges, nr_tracked * sizeof(tracked[0]));
+ ei->i_fc_nr_ranges = 0;
+ spin_unlock(&ei->i_fc_lock);
+
+ /*
+ * Snapshot only the actually-modified ranges, not the whole [min,max]
+ * span: this is what keeps scattered allocations from blowing past
+ * EXT4_FC_SNAPSHOT_MAX_RANGES and falling back to a full commit.
+ */
+ for (t = 0; t < nr_tracked; t++) {
+ ext4_lblk_t s = tracked[t].start;
+ ext4_lblk_t e = s + tracked[t].len - 1;
+
+ ret = ext4_fc_snapshot_lblk_range(inode, s, e, ranges,
+ nr_ranges_total, &nr_ranges,
+ snap_err);
+ if (ret)
+ return ret;
+ }
+
if (nr_rangesp)
*nr_rangesp = nr_ranges;
return 0;
--
2.43.0
^ permalink raw reply [flat|nested] 3+ messages in thread* [RFC PATCH v2 2/2] ext4: fast commit: allocate the range array lazily
[not found] ` <CGME20260623082331epcms2p4798e9d26b06f9a005bcca7b2edf395d3@epcms2p8>
2026-06-23 8:25 ` [RFC PATCH v2 1/2] ext4: fast commit: track disjoint modified ranges per inode Daejun Park
@ 2026-06-23 8:26 ` Daejun Park
1 sibling, 0 replies; 3+ messages in thread
From: Daejun Park @ 2026-06-23 8:26 UTC (permalink / raw)
To: tytso, adilger.kernel
Cc: me, libaokun, harshadshirwadkar, yi.zhang, ojaswin, linux-ext4,
linux-kernel, Daejun Park
Patch 1 keeps the disjoint-range set in a fixed EXT4_FC_MAX_RANGES+1
array. Embedding that in every ext4_inode_info costs ~140 bytes on
inodes that never use fast commit or only ever touch a single
contiguous range.
Keep the first range inline in i_fc_range and allocate the array only
when a second disjoint range appears; free it when the inode is
evicted. The tracking path runs under i_fc_lock, so the array is
allocated with GFP_ATOMIC; on allocation failure we coalesce into the
inline range -- i.e. the original single-range behaviour -- so memory
pressure never forces a full commit. The per-inode fast-commit
footprint drops to 20 bytes.
Signed-off-by: Daejun Park <daejun7.park@samsung.com>
---
fs/ext4/ext4.h | 23 +++++++++++-----
fs/ext4/fast_commit.c | 64 ++++++++++++++++++++++++++++++++++++++++---
fs/ext4/super.c | 1 +
3 files changed, 77 insertions(+), 11 deletions(-)
diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
index 8e93d30766fd..d93cc52cd01e 100644
--- a/fs/ext4/ext4.h
+++ b/fs/ext4/ext4.h
@@ -1106,14 +1106,23 @@ struct ext4_inode_info {
*/
/*
- * Disjoint lblk ranges modified in this fast commit. Tracking the
+ * Logical block ranges modified in this fast commit. Tracking the
* actual modified ranges (instead of one coalesced [min,max]) avoids
* snapshotting the whole spanned extent map for scattered allocations.
- * Sorted by start, mutually disjoint. Bounded by EXT4_FC_MAX_RANGES;
- * the extra slot is transient room used while inserting before an
- * overflow merge. Protected by i_fc_lock.
+ *
+ * The first range is kept inline in i_fc_range, so the common case of a
+ * single contiguous dirty region needs no allocation. When a second
+ * disjoint range appears the inode is upgraded to the i_fc_ranges array
+ * (EXT4_FC_MAX_RANGES + 1 entries, sorted and mutually disjoint; the
+ * extra slot is transient room used while inserting before an overflow
+ * merge), allocated then and freed when the inode is evicted. If that
+ * allocation fails we fall back to coalescing into i_fc_range, i.e. the
+ * original single coalesced-range behaviour. i_fc_nr_ranges counts the
+ * valid ranges; while i_fc_ranges is NULL it is 0 or 1. Protected by
+ * i_fc_lock.
*/
- struct ext4_fc_lblk_range i_fc_ranges[EXT4_FC_MAX_RANGES + 1];
+ struct ext4_fc_lblk_range i_fc_range;
+ struct ext4_fc_lblk_range *i_fc_ranges;
unsigned int i_fc_nr_ranges;
/*
@@ -1135,8 +1144,8 @@ struct ext4_inode_info {
spinlock_t i_raw_lock; /* protects updates to the raw inode */
/*
- * Protect concurrent accesses on i_fc_ranges, i_fc_nr_ranges
- * and inode's EXT4_FC_STATE_COMMITTING state bit.
+ * Protect concurrent accesses on i_fc_range, i_fc_ranges,
+ * i_fc_nr_ranges and inode's EXT4_FC_STATE_COMMITTING state bit.
*/
spinlock_t i_fc_lock;
diff --git a/fs/ext4/fast_commit.c b/fs/ext4/fast_commit.c
index 1ea3742a55b1..9d36365eae02 100644
--- a/fs/ext4/fast_commit.c
+++ b/fs/ext4/fast_commit.c
@@ -230,6 +230,7 @@ void ext4_fc_init_inode(struct inode *inode)
struct ext4_inode_info *ei = EXT4_I(inode);
ext4_fc_reset_inode(inode);
+ ei->i_fc_ranges = NULL;
ext4_clear_inode_state(inode, EXT4_STATE_FC_COMMITTING);
ext4_clear_inode_state(inode, EXT4_STATE_FC_REQUEUE);
INIT_LIST_HEAD(&ei->i_fc_list);
@@ -691,6 +692,8 @@ static int __track_range(handle_t *handle, struct inode *inode, void *arg,
struct ext4_inode_info *ei = EXT4_I(inode);
struct __track_range_args *__arg =
(struct __track_range_args *)arg;
+ ext4_lblk_t start = __arg->start, end = __arg->end;
+ ext4_lblk_t s0, e0;
if (inode->i_ino < EXT4_FIRST_INO(inode->i_sb)) {
ext4_debug("Special inode %llu being modified\n", inode->i_ino);
@@ -701,12 +704,61 @@ static int __track_range(handle_t *handle, struct inode *inode, void *arg,
* A sub-block punch hole rounds up the start and down the end, passing
* end == start - 1: no whole block changed, so there is nothing to
* track. (ext4_fc_track_template has already reset the range set for a
- * new transaction.)
+ * new transaction, so we need not do it here.)
*/
- if (__arg->end < __arg->start)
+ if (end < start)
return 0;
- ext4_fc_range_add(ei, __arg->start, __arg->end);
+ /* Already upgraded to the heap array: full multi-interval tracking. */
+ if (ei->i_fc_ranges) {
+ ext4_fc_range_add(ei, start, end);
+ return 0;
+ }
+
+ /* First range of this commit stays inline, no allocation needed. */
+ if (ei->i_fc_nr_ranges == 0) {
+ ei->i_fc_range.start = start;
+ ei->i_fc_range.len = end - start + 1;
+ ei->i_fc_nr_ranges = 1;
+ return 0;
+ }
+
+ /* One inline range so far. */
+ s0 = ei->i_fc_range.start;
+ e0 = s0 + ei->i_fc_range.len - 1;
+
+ /* Disjoint from it: try to upgrade to the array for exact tracking. */
+ if (start > e0 + 1 || end + 1 < s0) {
+ struct ext4_fc_lblk_range *heap;
+
+ /*
+ * GFP_ATOMIC: we hold i_fc_lock. __GFP_NOWARN: failure is not
+ * fatal -- we fall back to the single coalesced range below --
+ * so it must not splat under memory pressure.
+ */
+ heap = kmalloc_array(EXT4_FC_MAX_RANGES + 1, sizeof(*heap),
+ GFP_ATOMIC | __GFP_NOWARN);
+ if (heap) {
+ heap[0] = ei->i_fc_range;
+ ei->i_fc_ranges = heap;
+ ext4_fc_range_add(ei, start, end);
+ return 0;
+ }
+ /*
+ * Out of memory: fall back to the original single coalesced
+ * range by absorbing the gap below. This over-logs the spanned
+ * extents but stays a valid fast commit (no full-commit
+ * fallback), so there is nothing to mark ineligible.
+ */
+ }
+
+ /* Overlapping/adjacent, or array allocation failed: coalesce inline. */
+ if (start < s0)
+ s0 = start;
+ if (end > e0)
+ e0 = end;
+ ei->i_fc_range.start = s0;
+ ei->i_fc_range.len = e0 - s0 + 1;
return 0;
}
@@ -1178,7 +1230,11 @@ static int ext4_fc_snapshot_inode_data(struct inode *inode,
*nr_rangesp = 0;
return 0;
}
- memcpy(tracked, ei->i_fc_ranges, nr_tracked * sizeof(tracked[0]));
+ if (ei->i_fc_ranges)
+ memcpy(tracked, ei->i_fc_ranges,
+ nr_tracked * sizeof(tracked[0]));
+ else
+ tracked[0] = ei->i_fc_range; /* inline single-range mode */
ei->i_fc_nr_ranges = 0;
spin_unlock(&ei->i_fc_lock);
diff --git a/fs/ext4/super.c b/fs/ext4/super.c
index f2c52cc74676..cfa7e6bec385 100644
--- a/fs/ext4/super.c
+++ b/fs/ext4/super.c
@@ -1455,6 +1455,7 @@ static void ext4_free_in_core_inode(struct inode *inode)
pr_warn("%s: inode %llu still in fc list",
__func__, inode->i_ino);
}
+ kfree(EXT4_I(inode)->i_fc_ranges);
kmem_cache_free(ext4_inode_cachep, EXT4_I(inode));
}
--
2.43.0
^ permalink raw reply [flat|nested] 3+ messages in thread