[Midnightbsd-cvs] src [9287] trunk/sys/ufs/ffs: reduce runtime of fsck and tweak first indrect block placement.
laffer1 at midnightbsd.org
laffer1 at midnightbsd.org
Thu Mar 2 18:04:59 EST 2017
Revision: 9287
http://svnweb.midnightbsd.org/src/?rev=9287
Author: laffer1
Date: 2017-03-02 18:04:59 -0500 (Thu, 02 Mar 2017)
Log Message:
-----------
reduce runtime of fsck and tweak first indrect block placement. freebsd svn 249782
Modified Paths:
--------------
trunk/sys/ufs/ffs/ffs_alloc.c
trunk/sys/ufs/ffs/ffs_balloc.c
trunk/sys/ufs/ffs/fs.h
Modified: trunk/sys/ufs/ffs/ffs_alloc.c
===================================================================
--- trunk/sys/ufs/ffs/ffs_alloc.c 2017-03-02 23:02:45 UTC (rev 9286)
+++ trunk/sys/ufs/ffs/ffs_alloc.c 2017-03-02 23:04:59 UTC (rev 9287)
@@ -536,6 +536,18 @@
panic("ffs_reallocblks: non-physical cluster %d", i);
#endif
/*
+ * If the cluster crosses the boundary for the first indirect
+ * block, leave space for the indirect block. Indirect blocks
+ * are initially laid out in a position after the last direct
+ * block. Block reallocation would usually destroy locality by
+ * moving the indirect block out of the way to make room for
+ * data blocks if we didn't compensate here. We should also do
+ * this for other indirect block boundaries, but it is only
+ * important for the first one.
+ */
+ if (start_lbn < NDADDR && end_lbn >= NDADDR)
+ return (ENOSPC);
+ /*
* If the latest allocation is in a new cylinder group, assume that
* the filesystem has decided to move and do not force it back to
* the previous cylinder group.
@@ -744,6 +756,18 @@
panic("ffs_reallocblks: non-physical cluster %d", i);
#endif
/*
+ * If the cluster crosses the boundary for the first indirect
+ * block, do not move anything in it. Indirect blocks are
+ * usually initially laid out in a position between the data
+ * blocks. Block reallocation would usually destroy locality by
+ * moving the indirect block out of the way to make room for
+ * data blocks if we didn't compensate here. We should also do
+ * this for other indirect block boundaries, but it is only
+ * important for the first one.
+ */
+ if (start_lbn < NDADDR && end_lbn >= NDADDR)
+ return (ENOSPC);
+ /*
* If the latest allocation is in a new cylinder group, assume that
* the filesystem has decided to move and do not force it back to
* the previous cylinder group.
@@ -1055,7 +1079,7 @@
struct inode *pip;
{
struct fs *fs;
- u_int cg, prefcg, dirsize, cgsize;
+ int cg, prefcg, dirsize, cgsize;
u_int avgifree, avgbfree, avgndir, curdirsize;
u_int minifree, minbfree, maxndir;
u_int mincg, minndir;
@@ -1123,6 +1147,22 @@
* Limit number of dirs in one cg and reserve space for
* regular files, but only if we have no deficit in
* inodes or space.
+ *
+ * We are trying to find a suitable cylinder group nearby
+ * our preferred cylinder group to place a new directory.
+ * We scan from our preferred cylinder group forward looking
+ * for a cylinder group that meets our criterion. If we get
+ * to the final cylinder group and do not find anything,
+ * we start scanning backwards from our preferred cylinder
+ * group. The ideal would be to alternate looking forward
+ * and backward, but that is just too complex to code for
+ * the gain it would get. The most likely place where the
+ * backward scan would take effect is when we start near
+ * the end of the filesystem and do not find anything from
+ * where we are to the end. In that case, scanning backward
+ * will likely find us a suitable cylinder group much closer
+ * to our desired location than if we were to start scanning
+ * forward from the beginning of the filesystem.
*/
prefcg = ino_to_cg(fs, pip->i_number);
for (cg = prefcg; cg < fs->fs_ncg; cg++)
@@ -1132,7 +1172,7 @@
if (fs->fs_contigdirs[cg] < maxcontigdirs)
return ((ino_t)(fs->fs_ipg * cg));
}
- for (cg = 0; cg < prefcg; cg++)
+ for (cg = prefcg - 1; cg >= 0; cg--)
if (fs->fs_cs(fs, cg).cs_ndir < maxndir &&
fs->fs_cs(fs, cg).cs_nifree >= minifree &&
fs->fs_cs(fs, cg).cs_nbfree >= minbfree) {
@@ -1145,7 +1185,7 @@
for (cg = prefcg; cg < fs->fs_ncg; cg++)
if (fs->fs_cs(fs, cg).cs_nifree >= avgifree)
return ((ino_t)(fs->fs_ipg * cg));
- for (cg = 0; cg < prefcg; cg++)
+ for (cg = prefcg - 1; cg >= 0; cg--)
if (fs->fs_cs(fs, cg).cs_nifree >= avgifree)
break;
return ((ino_t)(fs->fs_ipg * cg));
@@ -1158,9 +1198,15 @@
*
* If no blocks have been allocated in the first section, the policy is to
* request a block in the same cylinder group as the inode that describes
- * the file. If no blocks have been allocated in any other section, the
- * policy is to place the section in a cylinder group with a greater than
- * average number of free blocks. An appropriate cylinder group is found
+ * the file. The first indirect is allocated immediately following the last
+ * direct block and the data blocks for the first indirect immediately
+ * follow it.
+ *
+ * If no blocks have been allocated in any other section, the indirect
+ * block(s) are allocated in the same cylinder group as its inode in an
+ * area reserved immediately following the inode blocks. The policy for
+ * the data blocks is to place them in a cylinder group with a greater than
+ * average number of free blocks. An appropriate cylinder group is found
* by using a rotor that sweeps the cylinder groups. When a new group of
* blocks is needed, the sweep begins in the cylinder group following the
* cylinder group from which the previous allocation was made. The sweep
@@ -1183,23 +1229,78 @@
ufs1_daddr_t *bap;
{
struct fs *fs;
- u_int cg;
+ u_int cg, inocg;
u_int avgbfree, startcg;
+ ufs2_daddr_t pref;
+ KASSERT(indx <= 0 || bap != NULL, ("need non-NULL bap"));
mtx_assert(UFS_MTX(ip->i_ump), MA_OWNED);
fs = ip->i_fs;
+ /*
+ * Allocation of indirect blocks is indicated by passing negative
+ * values in indx: -1 for single indirect, -2 for double indirect,
+ * -3 for triple indirect. As noted below, we attempt to allocate
+ * the first indirect inline with the file data. For all later
+ * indirect blocks, the data is often allocated in other cylinder
+ * groups. However to speed random file access and to speed up
+ * fsck, the filesystem reserves the first fs_metaspace blocks
+ * (typically half of fs_minfree) of the data area of each cylinder
+ * group to hold these later indirect blocks.
+ */
+ inocg = ino_to_cg(fs, ip->i_number);
+ if (indx < 0) {
+ /*
+ * Our preference for indirect blocks is the zone at the
+ * beginning of the inode's cylinder group data area that
+ * we try to reserve for indirect blocks.
+ */
+ pref = cgmeta(fs, inocg);
+ /*
+ * If we are allocating the first indirect block, try to
+ * place it immediately following the last direct block.
+ */
+ if (indx == -1 && lbn < NDADDR + NINDIR(fs) &&
+ ip->i_din1->di_db[NDADDR - 1] != 0)
+ pref = ip->i_din1->di_db[NDADDR - 1] + fs->fs_frag;
+ return (pref);
+ }
+ /*
+ * If we are allocating the first data block in the first indirect
+ * block and the indirect has been allocated in the data block area,
+ * try to place it immediately following the indirect block.
+ */
+ if (lbn == NDADDR) {
+ pref = ip->i_din1->di_ib[0];
+ if (pref != 0 && pref >= cgdata(fs, inocg) &&
+ pref < cgbase(fs, inocg + 1))
+ return (pref + fs->fs_frag);
+ }
+ /*
+ * If we are at the beginning of a file, or we have already allocated
+ * the maximum number of blocks per cylinder group, or we do not
+ * have a block allocated immediately preceeding us, then we need
+ * to decide where to start allocating new blocks.
+ */
if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) {
- if (lbn < NDADDR + NINDIR(fs)) {
- cg = ino_to_cg(fs, ip->i_number);
- return (cgbase(fs, cg) + fs->fs_frag);
- }
/*
+ * If we are allocating a directory data block, we want
+ * to place it in the metadata area.
+ */
+ if ((ip->i_mode & IFMT) == IFDIR)
+ return (cgmeta(fs, inocg));
+ /*
+ * Until we fill all the direct and all the first indirect's
+ * blocks, we try to allocate in the data area of the inode's
+ * cylinder group.
+ */
+ if (lbn < NDADDR + NINDIR(fs))
+ return (cgdata(fs, inocg));
+ /*
* Find a cylinder with greater than average number of
* unused data blocks.
*/
if (indx == 0 || bap[indx - 1] == 0)
- startcg =
- ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg;
+ startcg = inocg + lbn / fs->fs_maxbpg;
else
startcg = dtog(fs, bap[indx - 1]) + 1;
startcg %= fs->fs_ncg;
@@ -1207,17 +1308,17 @@
for (cg = startcg; cg < fs->fs_ncg; cg++)
if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
fs->fs_cgrotor = cg;
- return (cgbase(fs, cg) + fs->fs_frag);
+ return (cgdata(fs, cg));
}
for (cg = 0; cg <= startcg; cg++)
if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
fs->fs_cgrotor = cg;
- return (cgbase(fs, cg) + fs->fs_frag);
+ return (cgdata(fs, cg));
}
return (0);
}
/*
- * We just always try to lay things out contiguously.
+ * Otherwise, we just always try to lay things out contiguously.
*/
return (bap[indx - 1] + fs->fs_frag);
}
@@ -1233,23 +1334,78 @@
ufs2_daddr_t *bap;
{
struct fs *fs;
- u_int cg;
+ u_int cg, inocg;
u_int avgbfree, startcg;
+ ufs2_daddr_t pref;
+ KASSERT(indx <= 0 || bap != NULL, ("need non-NULL bap"));
mtx_assert(UFS_MTX(ip->i_ump), MA_OWNED);
fs = ip->i_fs;
+ /*
+ * Allocation of indirect blocks is indicated by passing negative
+ * values in indx: -1 for single indirect, -2 for double indirect,
+ * -3 for triple indirect. As noted below, we attempt to allocate
+ * the first indirect inline with the file data. For all later
+ * indirect blocks, the data is often allocated in other cylinder
+ * groups. However to speed random file access and to speed up
+ * fsck, the filesystem reserves the first fs_metaspace blocks
+ * (typically half of fs_minfree) of the data area of each cylinder
+ * group to hold these later indirect blocks.
+ */
+ inocg = ino_to_cg(fs, ip->i_number);
+ if (indx < 0) {
+ /*
+ * Our preference for indirect blocks is the zone at the
+ * beginning of the inode's cylinder group data area that
+ * we try to reserve for indirect blocks.
+ */
+ pref = cgmeta(fs, inocg);
+ /*
+ * If we are allocating the first indirect block, try to
+ * place it immediately following the last direct block.
+ */
+ if (indx == -1 && lbn < NDADDR + NINDIR(fs) &&
+ ip->i_din2->di_db[NDADDR - 1] != 0)
+ pref = ip->i_din2->di_db[NDADDR - 1] + fs->fs_frag;
+ return (pref);
+ }
+ /*
+ * If we are allocating the first data block in the first indirect
+ * block and the indirect has been allocated in the data block area,
+ * try to place it immediately following the indirect block.
+ */
+ if (lbn == NDADDR) {
+ pref = ip->i_din2->di_ib[0];
+ if (pref != 0 && pref >= cgdata(fs, inocg) &&
+ pref < cgbase(fs, inocg + 1))
+ return (pref + fs->fs_frag);
+ }
+ /*
+ * If we are at the beginning of a file, or we have already allocated
+ * the maximum number of blocks per cylinder group, or we do not
+ * have a block allocated immediately preceeding us, then we need
+ * to decide where to start allocating new blocks.
+ */
if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) {
- if (lbn < NDADDR + NINDIR(fs)) {
- cg = ino_to_cg(fs, ip->i_number);
- return (cgbase(fs, cg) + fs->fs_frag);
- }
/*
+ * If we are allocating a directory data block, we want
+ * to place it in the metadata area.
+ */
+ if ((ip->i_mode & IFMT) == IFDIR)
+ return (cgmeta(fs, inocg));
+ /*
+ * Until we fill all the direct and all the first indirect's
+ * blocks, we try to allocate in the data area of the inode's
+ * cylinder group.
+ */
+ if (lbn < NDADDR + NINDIR(fs))
+ return (cgdata(fs, inocg));
+ /*
* Find a cylinder with greater than average number of
* unused data blocks.
*/
if (indx == 0 || bap[indx - 1] == 0)
- startcg =
- ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg;
+ startcg = inocg + lbn / fs->fs_maxbpg;
else
startcg = dtog(fs, bap[indx - 1]) + 1;
startcg %= fs->fs_ncg;
@@ -1257,17 +1413,17 @@
for (cg = startcg; cg < fs->fs_ncg; cg++)
if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
fs->fs_cgrotor = cg;
- return (cgbase(fs, cg) + fs->fs_frag);
+ return (cgdata(fs, cg));
}
for (cg = 0; cg <= startcg; cg++)
if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
fs->fs_cgrotor = cg;
- return (cgbase(fs, cg) + fs->fs_frag);
+ return (cgdata(fs, cg));
}
return (0);
}
/*
- * We just always try to lay things out contiguously.
+ * Otherwise, we just always try to lay things out contiguously.
*/
return (bap[indx - 1] + fs->fs_frag);
}
@@ -1544,7 +1700,7 @@
ufs1_daddr_t bno;
ufs2_daddr_t blkno;
u_int8_t *blksfree;
- int i;
+ int i, cgbpref;
fs = ip->i_fs;
ump = ip->i_ump;
@@ -1551,24 +1707,30 @@
mtx_assert(UFS_MTX(ump), MA_OWNED);
cgp = (struct cg *)bp->b_data;
blksfree = cg_blksfree(cgp);
- if (bpref == 0 || dtog(fs, bpref) != cgp->cg_cgx) {
+ if (bpref == 0) {
bpref = cgp->cg_rotor;
- } else {
- bpref = blknum(fs, bpref);
- bno = dtogd(fs, bpref);
- /*
- * if the requested block is available, use it
- */
- if (ffs_isblock(fs, blksfree, fragstoblks(fs, bno)))
- goto gotit;
+ } else if ((cgbpref = dtog(fs, bpref)) != cgp->cg_cgx) {
+ /* map bpref to correct zone in this cg */
+ if (bpref < cgdata(fs, cgbpref))
+ bpref = cgmeta(fs, cgp->cg_cgx);
+ else
+ bpref = cgdata(fs, cgp->cg_cgx);
}
/*
+ * if the requested block is available, use it
+ */
+ bno = dtogd(fs, blknum(fs, bpref));
+ if (ffs_isblock(fs, blksfree, fragstoblks(fs, bno)))
+ goto gotit;
+ /*
* Take the next available block in this cylinder group.
*/
bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag);
if (bno < 0)
return (0);
- cgp->cg_rotor = bno;
+ /* Update cg_rotor only if allocated from the data zone */
+ if (bno >= dtogd(fs, cgdata(fs, cgp->cg_cgx)))
+ cgp->cg_rotor = bno;
gotit:
blkno = fragstoblks(fs, bno);
ffs_clrblock(fs, blksfree, (long)blkno);
@@ -1675,9 +1837,10 @@
* be recalled to try an allocation in the next cylinder group.
*/
if (dtog(fs, bpref) != cg)
- bpref = 0;
+ bpref = cgdata(fs, cg);
else
- bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref)));
+ bpref = blknum(fs, bpref);
+ bpref = fragstoblks(fs, dtogd(fs, bpref));
mapp = &cg_clustersfree(cgp)[bpref / NBBY];
map = *mapp++;
bit = 1 << (bpref % NBBY);
Modified: trunk/sys/ufs/ffs/ffs_balloc.c
===================================================================
--- trunk/sys/ufs/ffs/ffs_balloc.c 2017-03-02 23:02:45 UTC (rev 9286)
+++ trunk/sys/ufs/ffs/ffs_balloc.c 2017-03-02 23:04:59 UTC (rev 9287)
@@ -245,12 +245,14 @@
lbns_remfree = lbns;
if (nb == 0) {
UFS_LOCK(ump);
- pref = ffs_blkpref_ufs1(ip, lbn, 0, (ufs1_daddr_t *)0);
+ pref = ffs_blkpref_ufs1(ip, lbn, -indirs[0].in_off - 1,
+ (ufs1_daddr_t *)0);
if ((error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize,
flags, cred, &newb)) != 0) {
curthread_pflags_restore(saved_inbdflush);
return (error);
}
+ pref = newb + fs->fs_frag;
nb = newb;
*allocblk++ = nb;
*lbns_remfree++ = indirs[1].in_lbn;
@@ -297,7 +299,8 @@
}
UFS_LOCK(ump);
if (pref == 0)
- pref = ffs_blkpref_ufs1(ip, lbn, 0, (ufs1_daddr_t *)0);
+ pref = ffs_blkpref_ufs1(ip, lbn, i - num - 1,
+ (ufs1_daddr_t *)0);
if ((error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize,
flags | IO_BUFLOCKED, cred, &newb)) != 0) {
brelse(bp);
@@ -315,6 +318,7 @@
}
goto fail;
}
+ pref = newb + fs->fs_frag;
nb = newb;
*allocblk++ = nb;
*lbns_remfree++ = indirs[i].in_lbn;
@@ -363,7 +367,9 @@
*/
if (nb == 0) {
UFS_LOCK(ump);
- pref = ffs_blkpref_ufs1(ip, lbn, indirs[i].in_off, &bap[0]);
+ if (pref == 0)
+ pref = ffs_blkpref_ufs1(ip, lbn, indirs[i].in_off,
+ &bap[0]);
error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize,
flags | IO_BUFLOCKED, cred, &newb);
if (error) {
@@ -783,12 +789,14 @@
lbns_remfree = lbns;
if (nb == 0) {
UFS_LOCK(ump);
- pref = ffs_blkpref_ufs2(ip, lbn, 0, (ufs2_daddr_t *)0);
+ pref = ffs_blkpref_ufs2(ip, lbn, -indirs[0].in_off - 1,
+ (ufs2_daddr_t *)0);
if ((error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize,
flags, cred, &newb)) != 0) {
curthread_pflags_restore(saved_inbdflush);
return (error);
}
+ pref = newb + fs->fs_frag;
nb = newb;
*allocblk++ = nb;
*lbns_remfree++ = indirs[1].in_lbn;
@@ -835,7 +843,8 @@
}
UFS_LOCK(ump);
if (pref == 0)
- pref = ffs_blkpref_ufs2(ip, lbn, 0, (ufs2_daddr_t *)0);
+ pref = ffs_blkpref_ufs2(ip, lbn, i - num - 1,
+ (ufs2_daddr_t *)0);
if ((error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize,
flags | IO_BUFLOCKED, cred, &newb)) != 0) {
brelse(bp);
@@ -853,6 +862,7 @@
}
goto fail;
}
+ pref = newb + fs->fs_frag;
nb = newb;
*allocblk++ = nb;
*lbns_remfree++ = indirs[i].in_lbn;
@@ -901,7 +911,9 @@
*/
if (nb == 0) {
UFS_LOCK(ump);
- pref = ffs_blkpref_ufs2(ip, lbn, indirs[i].in_off, &bap[0]);
+ if (pref == 0)
+ pref = ffs_blkpref_ufs2(ip, lbn, indirs[i].in_off,
+ &bap[0]);
error = ffs_alloc(ip, lbn, pref, (int)fs->fs_bsize,
flags | IO_BUFLOCKED, cred, &newb);
if (error) {
Modified: trunk/sys/ufs/ffs/fs.h
===================================================================
--- trunk/sys/ufs/ffs/fs.h 2017-03-02 23:02:45 UTC (rev 9286)
+++ trunk/sys/ufs/ffs/fs.h 2017-03-02 23:04:59 UTC (rev 9287)
@@ -333,7 +333,8 @@
int32_t fs_maxbsize; /* maximum blocking factor permitted */
int64_t fs_unrefs; /* number of unreferenced inodes */
int64_t fs_providersize; /* size of underlying GEOM provider */
- int64_t fs_sparecon64[15]; /* old rotation block list head */
+ int64_t fs_metaspace; /* size of area reserved for metadata */
+ int64_t fs_sparecon64[14]; /* old rotation block list head */
int64_t fs_sblockloc; /* byte offset of standard superblock */
struct csum_total fs_cstotal; /* (u) cylinder summary information */
ufs_time_t fs_time; /* last time written */
@@ -525,6 +526,8 @@
* They calc filesystem addresses of cylinder group data structures.
*/
#define cgbase(fs, c) (((ufs2_daddr_t)(fs)->fs_fpg) * (c))
+#define cgdata(fs, c) (cgdmin(fs, c) + (fs)->fs_metaspace) /* data zone */
+#define cgmeta(fs, c) (cgdmin(fs, c)) /* meta data */
#define cgdmin(fs, c) (cgstart(fs, c) + (fs)->fs_dblkno) /* 1st data */
#define cgimin(fs, c) (cgstart(fs, c) + (fs)->fs_iblkno) /* inode blk */
#define cgsblock(fs, c) (cgstart(fs, c) + (fs)->fs_sblkno) /* super blk */
More information about the Midnightbsd-cvs
mailing list