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>