Bring in reallocblk to ext2fs.

The feature has been standard for a while in UFS as a means to reduce
fragmentation, therefore maintaining consistent performance with
filesystem aging. This is also very similar to what ext4 calls
"delayed allocation".

In his 2010 GSoC, Zheng Liu ported and benchmarked the missing
FANCY_REALLOC code to find more consistent performance improvements than
with the preallocation approach.

PR:		159233
Author:		Zheng Liu <gnehzuil AT SPAMFREE gmail DOT com>
Sponsored by:	Google Inc.
Approved by:	jhb (mentor)
MFC after:	2 weeks

1 files changed, 104 insertions, 0 deletions

diff --git a/sys/fs/ext2fs/ext2_subr.c b/sys/fs/ext2fs/ext2_subr.c
index 70ade83..b8d59bc 100644
--- a/sys/fs/ext2fs/ext2_subr.c
+++ b/sys/fs/ext2fs/ext2_subr.c
@@ -120,3 +120,107 @@ ext2_checkoverlap(bp, ip)
 	}
 }
 #endif /* KDB */
+
+/*
+ * Update the cluster map because of an allocation of free like ffs.
+ *
+ * Cnt == 1 means free; cnt == -1 means allocating.
+ */
+void
+ext2_clusteracct(struct m_ext2fs *fs, char *bbp, int cg, daddr_t bno, int cnt)
+{
+	int32_t *sump = fs->e2fs_clustersum[cg].cs_sum;
+	int32_t *lp;
+	int back, bit, end, forw, i, loc, start;
+
+	/* Initialize the cluster summary array. */
+	if (fs->e2fs_clustersum[cg].cs_init == 0) {
+		int run = 0;
+		bit = 1;
+		loc = 0;
+
+		for (i = 0; i < fs->e2fs->e2fs_fpg; i++) {
+			if ((bbp[loc] & bit) == 0)
+				run++;
+			else if (run != 0) {
+				if (run > fs->e2fs_contigsumsize)
+					run = fs->e2fs_contigsumsize;
+				sump[run]++;
+				run = 0;
+			}
+			if ((i & (NBBY - 1)) != (NBBY - 1))
+				bit <<= 1;
+			else {
+				loc++;
+				bit = 1;
+			}
+		}
+		if (run != 0) {
+			if (run > fs->e2fs_contigsumsize)
+				run = fs->e2fs_contigsumsize;
+			sump[run]++;
+		}
+		fs->e2fs_clustersum[cg].cs_init = 1;
+	}
+
+	if (fs->e2fs_contigsumsize <= 0)
+		return;
+
+	/* Find the size of the cluster going forward. */
+	start = bno + 1;
+	end = start + fs->e2fs_contigsumsize;
+	if (end > fs->e2fs->e2fs_fpg)
+		end = fs->e2fs->e2fs_fpg;
+	loc = start / NBBY;
+	bit = 1 << (start % NBBY);
+	for (i = start; i < end; i++) {
+		if ((bbp[loc] & bit) != 0)
+			break;
+		if ((i & (NBBY - 1)) != (NBBY - 1))
+			bit <<= 1;
+		else {
+			loc++;
+			bit = 1;
+		}
+	}
+	forw = i - start;
+
+	/* Find the size of the cluster going backward. */
+	start = bno - 1;
+	end = start - fs->e2fs_contigsumsize;
+	if (end < 0)
+		end = -1;
+	loc = start / NBBY;
+	bit = 1 << (start % NBBY);
+	for (i = start; i > end; i--) {
+		if ((bbp[loc] & bit) != 0)
+			break;
+		if ((i & (NBBY - 1)) != 0)
+			bit >>= 1;
+		else {
+			loc--;
+			bit = 1 << (NBBY - 1);
+		}
+	}
+	back = start - i;
+
+	/*
+	 * Account for old cluster and the possibly new forward and
+	 * back clusters.
+	 */
+	i = back + forw + 1;
+	if (i > fs->e2fs_contigsumsize)
+		i = fs->e2fs_contigsumsize;
+	sump[i] += cnt;
+	if (back > 0)
+		sump[back] -= cnt;
+	if (forw > 0)
+		sump[forw] -= cnt;
+
+	/* Update cluster summary information. */
+	lp = &sump[fs->e2fs_contigsumsize];
+	for (i = fs->e2fs_contigsumsize; i > 0; i--)
+		if (*lp-- > 0)
+			break;
+	fs->e2fs_maxcluster[cg] = i;
+}