Date: Tue, 15 Mar 2011 20:17:11 +0800 From: gnehzuil <gnehzuil@gmail.com> To: freebsd-fs@freebsd.org Cc: "Pedro F. Giffuni" <giffunip@yahoo.com> Subject: [ext2fs][patch] reallocblks Message-ID: <4D7F58C7.4060402@gmail.com>
next in thread | raw e-mail | index | archive | help
This is a multi-part message in MIME format.
--------------040509040101080104050601
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Hi there,
I have implemented reallocblks in ext2fs. I added some structures in
m_ext2fs to record cluster summary information due to group descriptor
has not a structure to record these data in disk. So I implemented it in
memory. The implementation is almost the same to in ffs.
I have done some simple benchmarks with dbench. This patch can improve
the performance a little.
Best regards,
lz
--------------040509040101080104050601
Content-Type: text/x-patch;
name="patch-realloc.diff"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="patch-realloc.diff"
diff -u ext2fs/ext2_alloc.c ext2fs_realloc/ext2_alloc.c
--- ext2fs/ext2_alloc.c 2011-03-15 19:57:35.000000000 +0000
+++ ext2fs_realloc/ext2_alloc.c 2011-03-15 19:53:56.000000000 +0000
@@ -42,6 +42,7 @@
#include <sys/vnode.h>
#include <sys/stat.h>
#include <sys/mount.h>
+#include <sys/sysctl.h>
#include <sys/syslog.h>
#include <sys/buf.h>
@@ -52,6 +53,7 @@
#include <fs/ext2fs/ext2_extern.h>
static daddr_t ext2_alloccg(struct inode *, int, daddr_t, int);
+static daddr_t ext2_clusteralloc(struct inode *, int, daddr_t, int);
static u_long ext2_dirpref(struct inode *);
static void ext2_fserr(struct m_ext2fs *, uid_t, char *);
static u_long ext2_hashalloc(struct inode *, int, long, int,
@@ -59,9 +61,6 @@
int));
static daddr_t ext2_nodealloccg(struct inode *, int, daddr_t, int);
static daddr_t ext2_mapsearch(struct m_ext2fs *, char *, daddr_t);
-#ifdef FANCY_REALLOC
-static int ext2_reallocblks(struct vop_reallocblks_args *);
-#endif
/*
* Allocate a block in the file system.
@@ -150,7 +149,6 @@
* the previous block allocation will be used.
*/
-#ifdef FANCY_REALLOC
SYSCTL_NODE(_vfs, OID_AUTO, ext2fs, CTLFLAG_RW, 0, "EXT2FS filesystem");
static int doasyncfree = 1;
@@ -159,7 +157,6 @@
static int doreallocblks = 1;
SYSCTL_INT(_vfs_ext2fs, OID_AUTO, doreallocblks, CTLFLAG_RW, &doreallocblks, 0, "");
-#endif
int
ext2_reallocblks(ap)
@@ -168,11 +165,6 @@
struct cluster_save *a_buflist;
} */ *ap;
{
-#ifndef FANCY_REALLOC
-/* printf("ext2_reallocblks not implemented\n"); */
-return ENOSPC;
-#else
-
struct m_ext2fs *fs;
struct inode *ip;
struct vnode *vp;
@@ -181,17 +173,19 @@
struct ext2mount *ump;
struct cluster_save *buflist;
struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp;
- int32_t start_lbn, end_lbn, soff, newblk, blkno =0;
+ int32_t start_lbn, end_lbn, soff, newblk, blkno;
int i, len, start_lvl, end_lvl, pref, ssize;
vp = ap->a_vp;
ip = VTOI(vp);
fs = ip->i_e2fs;
ump = ip->i_ump;
-#ifdef UNKLAR
- if (fs->fs_contigsumsize <= 0)
+
+ if (doreallocblks == 0)
return (ENOSPC);
-#endif
+ if (fs->e2fs_contigsumsize <= 0)
+ return (ENOSPC);
+
buflist = ap->a_buflist;
len = buflist->bs_nchildren;
start_lbn = buflist->bs_children[0]->b_lblkno;
@@ -228,11 +222,6 @@
soff = idp->in_off;
}
/*
- * Find the preferred location for the cluster.
- */
- EXT2_LOCK(ump);
- pref = ext2_blkpref(ip, start_lbn, soff, sbap, blkno);
- /*
* If the block range spans two block maps, get the second map.
*/
if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) {
@@ -243,13 +232,16 @@
panic("ext2_reallocblk: start == end");
#endif
ssize = len - (idp->in_off + 1);
- if (bread(vp, idp->in_lbn, (int)fs->e2fs_bsize, NOCRED, &ebp)){
- EXT2_UNLOCK(ump);
+ if (bread(vp, idp->in_lbn, (int)fs->e2fs_bsize, NOCRED, &ebp))
goto fail;
- }
ebap = (int32_t *)ebp->b_data;
}
/*
+ * Find the preferred location for the cluster.
+ */
+ EXT2_LOCK(ump);
+ pref = ext2_blkpref(ip, start_lbn, soff, sbap, 0);
+ /*
* Search the block map looking for an allocation of the desired size.
*/
if ((newblk = (int32_t)ext2_hashalloc(ip, dtog(fs, pref), pref,
@@ -264,15 +256,23 @@
* block pointers in the inode and indirect blocks associated
* with the file.
*/
+#ifdef DEBUG
+ printf("realloc: ino %d, lbns %jd-%jd\n\told:", ip->i_number,
+ (intmax_t)start_lbn, (intmax_t)end_lbn);
+#endif /* DEBUG */
blkno = newblk;
for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->e2fs_fpb) {
- if (i == ssize)
+ if (i == ssize) {
bap = ebap;
soff = -i;
+ }
#ifdef DIAGNOSTIC
if (buflist->bs_children[i]->b_blkno != fsbtodb(fs, *bap))
panic("ext2_reallocblks: alloc mismatch");
#endif
+#ifdef DEBUG
+ printf(" %d,", *bap);
+#endif /* DEBUG */
*bap++ = blkno;
}
/*
@@ -308,11 +308,20 @@
/*
* Last, free the old blocks and assign the new blocks to the buffers.
*/
+#ifdef DEBUG
+ printf("\n\tnew:");
+#endif /* DEBUG */
for (blkno = newblk, i = 0; i < len; i++, blkno += fs->e2fs_fpb) {
ext2_blkfree(ip, dbtofsb(fs, buflist->bs_children[i]->b_blkno),
fs->e2fs_bsize);
buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno);
- }
+#ifdef DEBUG
+ printf(" %d,", blkno);
+#endif /* DEBUG */
+ }
+#ifdef DEBUG
+ printf("\n");
+#endif /* DEBUG */
return (0);
fail:
@@ -321,8 +330,6 @@
if (sbap != &ip->i_db[0])
brelse(sbp);
return (ENOSPC);
-
-#endif /* FANCY_REALLOC */
}
/*
@@ -747,6 +754,7 @@
#endif
setbit(bbp, bno);
EXT2_LOCK(ump);
+ ext2_clusteracct(fs, bbp, cg, bno, -1);
fs->e2fs->e2fs_fbcount--;
fs->e2fs_gd[cg].ext2bgd_nbfree--;
fs->e2fs_fmod = 1;
@@ -755,6 +763,113 @@
return (cg * fs->e2fs->e2fs_fpg + fs->e2fs->e2fs_first_dblock + bno);
}
+static daddr_t
+ext2_clusteralloc(struct inode *ip, int cg, daddr_t bpref, int len)
+{
+ struct m_ext2fs *fs;
+ struct ext2mount *ump;
+ struct buf *bp;
+ char *bbp;
+ int bit, error, got, i, loc, run;
+ int32_t *lp;
+ daddr_t bno;
+
+ fs = ip->i_e2fs;
+ ump = ip->i_ump;
+
+ if (fs->e2fs_maxcluster[cg] < len)
+ return (0);
+
+ EXT2_UNLOCK(ump);
+ error = bread(ip->i_devvp,
+ fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_b_bitmap),
+ (int)fs->e2fs_bsize, NOCRED, &bp);
+ if (error)
+ goto fail_lock;
+
+ bbp = (char *)bp->b_data;
+ bp->b_xflags |= BX_BKGRDWRITE;
+
+ EXT2_LOCK(ump);
+ /*
+ * Check to see if a cluster of the needed size (or bigger) is
+ * available in this cylinder group.
+ */
+ lp = &fs->e2fs_clustersum[cg].cs_sum[len];
+ for (i = len; i <= fs->e2fs_contigsumsize; i++)
+ if (*lp++ > 0)
+ break;
+ if (i > fs->e2fs_contigsumsize) {
+ /*
+ * Update the cluster summary information to reflect
+ * the true maximum sized cluster so that future cluster
+ * allocation requests can avoid reading the bitmap only
+ * to find no cluster.
+ */
+ lp = &fs->e2fs_clustersum[cg].cs_sum[len - 1];
+ for (i = len - 1; i > 0; i--)
+ if (*lp-- > 0)
+ break;
+ fs->e2fs_maxcluster[cg] = i;
+ goto fail;
+ }
+ EXT2_UNLOCK(ump);
+
+ /* Search the bitmap to find a bit enough cluster like ffs. */
+ if (dtog(fs, bpref) != cg)
+ bpref = 0;
+ if (bpref != 0)
+ bpref = dtogd(fs, bpref);
+ loc = bpref / NBBY;
+ bit = 1 << (bpref % NBBY);
+ for (run = 0, got = bpref; got < fs->e2fs->e2fs_fpg; got++) {
+ if ((bbp[loc] & bit) != 0)
+ run = 0;
+ else {
+ run++;
+ if (run == len)
+ break;
+ }
+ if ((got & (NBBY - 1)) != (NBBY - 1))
+ bit <<= 1;
+ else {
+ loc++;
+ bit = 1;
+ }
+ }
+
+ if (got >= fs->e2fs->e2fs_fpg)
+ goto fail_lock;
+
+ /* Allocate the cluster that we have found. */
+ for (i = 1; i < len; i++)
+ if (!isclr(bbp, got - run + i))
+ panic("ext2_clusteralloc: map mismatch");
+
+ bno = got - run + 1;
+ if (bno >= fs->e2fs->e2fs_fpg)
+ panic("ext2_clusteralloc: allocated out of group");
+
+ EXT2_LOCK(ump);
+ for (i = 0; i < len; i += fs->e2fs_fpb) {
+ setbit(bbp, bno + i);
+ ext2_clusteracct(fs, bbp, cg, bno + i, -1);
+ fs->e2fs->e2fs_fbcount--;
+ fs->e2fs_gd[cg].ext2bgd_nbfree--;
+ }
+ fs->e2fs_fmod = 1;
+ EXT2_UNLOCK(ump);
+
+ bdwrite(bp);
+ return (cg * fs->e2fs->e2fs_fpg + fs->e2fs->e2fs_first_dblock + bno);
+
+fail_lock:
+ EXT2_LOCK(ump);
+fail:
+ brelse(bp);
+ return (0);
+}
+
/*
* Determine whether an inode can be allocated.
*
@@ -877,6 +992,7 @@
}
clrbit(bbp, bno);
EXT2_LOCK(ump);
+ ext2_clusteracct(fs, bbp, cg, bno, 1);
fs->e2fs->e2fs_fbcount++;
fs->e2fs_gd[cg].ext2bgd_nbfree++;
fs->e2fs_fmod = 1;
diff -u ext2fs/ext2_extern.h ext2fs_realloc/ext2_extern.h
--- ext2fs/ext2_extern.h 2011-03-15 19:57:35.000000000 +0000
+++ ext2fs_realloc/ext2_extern.h 2011-03-15 19:53:56.000000000 +0000
@@ -55,6 +55,7 @@
int32_t ext2_blkpref(struct inode *, int32_t, int, int32_t *, int32_t);
int ext2_bmap(struct vop_bmap_args *);
int ext2_bmaparray(struct vnode *, int32_t, int32_t *, int *, int *);
+void ext2_clusteracct(struct m_ext2fs *, char *, int, daddr_t, int);
void ext2_dirbad(struct inode *ip, doff_t offset, char *how);
void ext2_ei2i(struct ext2fs_dinode *, struct inode *);
int ext2_getlbns(struct vnode *, int32_t, struct indir *, int *);
diff -u ext2fs/ext2_subr.c ext2fs_realloc/ext2_subr.c
--- ext2fs/ext2_subr.c 2011-03-15 19:57:35.000000000 +0000
+++ ext2fs_realloc/ext2_subr.c 2011-03-15 19:53:56.000000000 +0000
@@ -120,3 +120,107 @@
}
}
#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;
+}
diff -u ext2fs/ext2_vfsops.c ext2fs_realloc/ext2_vfsops.c
--- ext2fs/ext2_vfsops.c 2011-03-15 19:57:35.000000000 +0000
+++ ext2fs_realloc/ext2_vfsops.c 2011-03-15 19:53:56.000000000 +0000
@@ -405,7 +405,7 @@
* Things to do to update the mount:
* 1) invalidate all cached meta-data.
* 2) re-read superblock from disk.
- * 3) re-read summary information from disk.
+ * 3) invalidate all cluster summary information.
* 4) invalidate all inactive vnodes.
* 5) invalidate all cached file data.
* 6) re-read inode data for all active vnodes.
@@ -419,7 +419,9 @@
struct buf *bp;
struct ext2fs *es;
struct m_ext2fs *fs;
- int error;
+ struct csum *sump;
+ int error, i;
+ int32_t *lp;
if ((mp->mnt_flag & MNT_RDONLY) == 0)
return (EINVAL);
@@ -456,6 +458,19 @@
#endif
brelse(bp);
+ /*
+ * Step 3: invalidate all cluster summary information.
+ */
+ if (fs->e2fs_contigsumsize > 0) {
+ lp = fs->e2fs_maxcluster;
+ sump = fs->e2fs_clustersum;
+ for (i = 0; i < fs->e2fs_gcount; i++, sump++) {
+ *lp++ = fs->e2fs_contigsumsize;
+ sump->cs_init = 0;
+ bzero(sump->cs_sum, fs->e2fs_contigsumsize + 1);
+ }
+ }
+
loop:
MNT_ILOCK(mp);
MNT_VNODE_FOREACH(vp, mp, mvp) {
@@ -511,8 +526,11 @@
struct cdev *dev = devvp->v_rdev;
struct g_consumer *cp;
struct bufobj *bo;
+ struct csum *sump;
int error;
int ronly;
+ int i, size;
+ int32_t *lp;
ronly = vfs_flagopt(mp->mnt_optnew, "ro", NULL, 0);
/* XXX: use VOP_ACESS to check FS perms */
@@ -582,6 +600,33 @@
if ((error = compute_sb_data(devvp, ump->um_e2fs->e2fs, ump->um_e2fs)))
goto out;
+ /*
+ * We calculate the max contiguous blks and size of cluster summary
+ * array. In ffs, these works are done in newfs. But superblock in
+ * ext2fs doesn't have these variables. So we just can calculate them
+ * in here.
+ */
+ ump->um_e2fs->e2fs_maxcontig = MAX(1, MAXPHYS / ump->um_e2fs->e2fs_bsize);
+ if (ump->um_e2fs->e2fs_maxcontig > 0)
+ ump->um_e2fs->e2fs_contigsumsize =
+ MIN(ump->um_e2fs->e2fs_maxcontig, EXT2_MAXCONTIG);
+ else
+ ump->um_e2fs->e2fs_contigsumsize = 0;
+ if (ump->um_e2fs->e2fs_contigsumsize > 0) {
+ size = ump->um_e2fs->e2fs_gcount * sizeof(int32_t);
+ ump->um_e2fs->e2fs_maxcluster = malloc(size, M_EXT2MNT, M_WAITOK);
+ size = ump->um_e2fs->e2fs_gcount * sizeof(struct csum);
+ ump->um_e2fs->e2fs_clustersum = malloc(size, M_EXT2MNT, M_WAITOK);
+ lp = ump->um_e2fs->e2fs_maxcluster;
+ sump = ump->um_e2fs->e2fs_clustersum;
+ for (i = 0; i < ump->um_e2fs->e2fs_gcount; i++, sump++) {
+ *lp++ = ump->um_e2fs->e2fs_contigsumsize;
+ sump->cs_init = 0;
+ sump->cs_sum = malloc((ump->um_e2fs->e2fs_contigsumsize + 1) *
+ sizeof(int32_t), M_EXT2MNT, M_WAITOK | M_ZERO);
+ }
+ }
+
brelse(bp);
bp = NULL;
fs = ump->um_e2fs;
@@ -656,7 +701,8 @@
{
struct ext2mount *ump;
struct m_ext2fs *fs;
- int error, flags, ronly;
+ struct csum *sump;
+ int error, flags, i, ronly;
flags = 0;
if (mntflags & MNT_FORCE) {
@@ -681,6 +727,11 @@
g_topology_unlock();
PICKUP_GIANT();
vrele(ump->um_devvp);
+ sump = fs->e2fs_clustersum;
+ for (i = 0; i < fs->e2fs_gcount; i++, sump++)
+ free(sump->cs_sum, M_EXT2MNT);
+ free(fs->e2fs_clustersum, M_EXT2MNT);
+ free(fs->e2fs_maxcluster, M_EXT2MNT);
free(fs->e2fs_gd, M_EXT2MNT);
free(fs->e2fs_contigdirs, M_EXT2MNT);
free(fs->e2fs, M_EXT2MNT);
diff -u ext2fs/ext2fs.h ext2fs_realloc/ext2fs.h
--- ext2fs/ext2fs.h 2011-03-15 19:57:35.000000000 +0000
+++ ext2fs_realloc/ext2fs.h 2011-03-15 19:53:56.000000000 +0000
@@ -45,6 +45,17 @@
#define EXT2_LINK_MAX 32000
/*
+ * A summary of contiguous blocks of various sizes in maintained
+ * in each cylinder group. Normally this is set by the initial
+ * value of fs_maxcontig. To conserve space, a maximum summary size
+ * is set by EXT2_MAXCONTIG.
+ *
+ * XXX:FS_MAXCONTIG is set to 16 to conserve space. Here we set it to
+ * 32 for performance.
+ */
+#define EXT2_MAXCONTIG 32
+
+/*
* Constants relative to the data blocks
*/
#define EXT2_NDIR_BLOCKS 12
@@ -140,6 +151,10 @@
char e2fs_wasvalid; /* valid at mount time */
off_t e2fs_maxfilesize;
struct ext2_gd *e2fs_gd; /* Group Descriptors */
+ int32_t e2fs_maxcontig; /* max number of contiguous blks */
+ int32_t e2fs_contigsumsize; /* size of cluster summary array */
+ int32_t *e2fs_maxcluster; /* max cluster in each cyl group */
+ struct csum *e2fs_clustersum; /* cluster summary in each cyl group */
};
/*
@@ -242,6 +257,13 @@
u_int32_t reserved2[3];
};
+/* cluster summary information */
+
+struct csum {
+ int8_t cs_init; /* cluster summary has been initialized */
+ int32_t *cs_sum; /* cluster summary array */
+};
+
/* EXT2FS metadatas are stored in little-endian byte order. These macros
* helps reading these metadatas
*/
--------------040509040101080104050601--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?4D7F58C7.4060402>