PERFORCE change 179245 for review
Zheng Liu
lz at FreeBSD.org
Sun Jun 6 03:12:11 UTC 2010
http://p4web.freebsd.org/@@179245?ac=10
Change 179245 by lz at gnehzuil-freebsd on 2010/06/06 03:11:36
Reimplement the reservation window.
* Old implementation's allocation hit ratio is too low when
the number of threads are greater thant 4
* Set i_next_alloc_goal variable to provide a better block preference
* NOTE: Not implement dynamically increase window size
Affected files ...
.. //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_alloc.c#21 edit
Differences ...
==== //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_alloc.c#21 (text+ko) ====
@@ -52,6 +52,8 @@
#include <fs/ext2fs/ext2_extern.h>
#include <fs/ext2fs/ext2_rsv_win.h>
+#define phy_blk(cg, fs) (((cg) * (fs->e2fs->e2fs_fpg)) + fs->e2fs->e2fs_first_dblock)
+
static daddr_t ext2_alloccg(struct inode *, int, daddr_t, int);
static u_long ext2_dirpref(struct inode *);
static void ext2_fserr(struct m_ext2fs *, uid_t, char *);
@@ -62,20 +64,85 @@
static daddr_t ext2_mapsearch(struct m_ext2fs *, char *, daddr_t);
/* For reservation window */
-static void ext2_add_rsv_win(struct m_ext2fs *, struct ext2_rsv_win *);
-static u_long ext2_alloc_blk(struct m_ext2fs *, struct inode *, int cg,
- struct buf *, int32_t, struct ext2_rsv_win *);
-static u_long ext2_alloc_new_rsv_win(struct inode *, struct ext2_rsv_win *, int32_t,
- struct m_ext2fs *, int, struct buf *);
-static int ext2_find_next_rsv_win(struct ext2_rsv_win *, struct ext2_rsv_win *,
+static u_long ext2_alloc_blk(struct inode *, int, struct buf *, int32_t, struct ext2_rsv_win *);
+static int ext2_alloc_new_rsv(struct inode *, int, struct buf *, int32_t);
+static int ext2_bpref_in_rsv(struct ext2_rsv_win *, int32_t);
+static int ext2_find_rsv(struct ext2_rsv_win *, struct ext2_rsv_win *,
struct m_ext2fs *, int32_t, int);
static void ext2_remove_rsv_win(struct m_ext2fs *, struct ext2_rsv_win *);
static u_long ext2_rsvalloc(struct m_ext2fs *, struct inode *, int,
struct buf *, int32_t, int);
-struct ext2_rsv_win *ext2_search_rsv_win(struct ext2_rsv_win_tree *, int32_t);
+static daddr_t ext2_search_next_block(struct m_ext2fs *, char *, int, int);
+static struct ext2_rsv_win *ext2_search_rsv(struct ext2_rsv_win_tree *, int32_t);
RB_GENERATE(ext2_rsv_win_tree, ext2_rsv_win, rsv_link, ext2_rsv_win_cmp);
+static u_long
+ext2_alloc_blk(struct inode *ip, int cg, struct buf *bp,
+ int32_t bpref, struct ext2_rsv_win *rp)
+{
+ struct m_ext2fs *fs;
+ struct ext2mount *ump;
+ int bno, start, end;
+ char *bbp;
+
+ fs = ip->i_e2fs;
+ ump = ip->i_ump;
+ bbp = (char *)bp->b_data;
+
+ if (fs->e2fs_gd[cg].ext2bgd_nbfree == 0)
+ return (0);
+
+ if (bpref < 0)
+ bpref = 0;
+
+ if (rp != NULL) {
+ if (dtog(fs, rp->rsv_start) != cg)
+ start = phy_blk(cg, fs);
+ else
+ start = rp->rsv_start;
+ if (dtog(fs, rp->rsv_end) != cg)
+ end = fs->e2fs->e2fs_fpg;
+ else
+ end = rp->rsv_end;
+
+ if (start <= bpref && bpref <= end) {
+ bpref = dtogd(fs, bpref);
+ if (isclr(bbp, bpref)) {
+ bno = bpref;
+ goto gotit;
+ }
+ } else
+ bpref = dtogd(fs, rp->rsv_start);
+ } else {
+ if (dtog(fs, bpref) != cg)
+ bpref = 0;
+ if (bpref != 0) {
+ bpref = dtogd(fs, bpref);
+ if (isclr(bbp, bpref)) {
+ bno = bpref;
+ goto gotit;
+ }
+ }
+ }
+
+ bno = ext2_mapsearch(fs, bbp, bpref);
+ if (bno < 0)
+ return (0);
+
+gotit:
+ setbit(bbp, (daddr_t)bno);
+ EXT2_LOCK(ump);
+ fs->e2fs->e2fs_fbcount--;
+ fs->e2fs_gd[cg].ext2bgd_nbfree--;
+ fs->e2fs_fmod = 1;
+ EXT2_UNLOCK(ump);
+ bdwrite(bp);
+ bno = phy_blk(cg, fs) + bno;
+ ip->i_next_alloc_goal = bno;
+ return (bno);
+}
+
/*
* Initialize reservation window per inode.
*/
@@ -143,23 +210,19 @@
rp->rsv_alloc_hit = 0;
}
-/*
- * Add a ext2_rsv_win struct to RB tree.
- */
-static void
-ext2_add_rsv_win(struct m_ext2fs *fs, struct ext2_rsv_win *rp)
+static int
+ext2_bpref_in_rsv(struct ext2_rsv_win *rp, int32_t bpref)
{
- RB_INSERT(ext2_rsv_win_tree, &fs->e2fs_rsv_tree, rp);
+ if (bpref >= 0 && (bpref < rp->rsv_start || bpref > rp->rsv_end))
+ return (0);
+
+ return (1);
}
-/*
- * Find a reservation window which can includes the bpref,
- * or the previous one if bpref is not in any window.
- */
-struct ext2_rsv_win *
-ext2_search_rsv_win(struct ext2_rsv_win_tree *root, int32_t bpref)
+static struct ext2_rsv_win *
+ext2_search_rsv(struct ext2_rsv_win_tree *root, int32_t start)
{
- struct ext2_rsv_win *next, *prev;
+ struct ext2_rsv_win *prev, *next;
if (RB_EMPTY(root))
return (NULL);
@@ -167,35 +230,42 @@
next = RB_ROOT(root);
do {
prev = next;
- if (bpref < next->rsv_start)
+ if (start < next->rsv_start)
next = RB_LEFT(next, rsv_link);
- else if (bpref > next->rsv_end)
+ else if (start > next->rsv_end)
next = RB_RIGHT(next, rsv_link);
else
- return (prev);
- } while(next != NULL);
+ return (next);
+ } while (next != NULL);
- if (prev->rsv_start > bpref)
- prev = RB_PREV(ext2_rsv_win_tree, root, prev);
+ if (prev->rsv_start > start) {
+ next = RB_PREV(ext2_rsv_win_tree, root, prev);
+ if (next != NULL)
+ prev = next;
+ }
return (prev);
}
-/*
- * Find a space to store a reservation window.
- */
static int
-ext2_find_next_rsv_win(struct ext2_rsv_win *search, struct ext2_rsv_win *rp,
- struct m_ext2fs *fs, int32_t bpref, int cg)
+ext2_find_rsv(struct ext2_rsv_win *search, struct ext2_rsv_win *rp,
+ struct m_ext2fs *fs, int32_t start, int cg)
{
- struct ext2_rsv_win *rsv, *prev, *next;
+ struct ext2_rsv_win *rsv, *prev;
int32_t cur;
int size = rp->rsv_goal_size;
- if (search == NULL)
- search = RB_ROOT(&fs->e2fs_rsv_tree);
+ if (search == NULL) {
+ rp->rsv_start = start & ~7;
+ rp->rsv_end = start + size - 1;
+ rp->rsv_alloc_hit = 0;
+
+ RB_INSERT(ext2_rsv_win_tree, &fs->e2fs_rsv_tree, rp);
+
+ return (0);
+ }
- cur = bpref;
+ cur = start & ~7;
rsv = search;
prev = NULL;
@@ -207,212 +277,100 @@
return (-1);
prev = rsv;
- next = RB_NEXT(ext2_rsv_win_tree, &fs->e2fs_rsv_tree, rsv);
- rsv = next;
+ rsv = RB_NEXT(ext2_rsv_win_tree, &fs->e2fs_rsv_tree, rsv);
- if (next == NULL)
+ if (rsv == NULL)
break;
if (cur + size <= rsv->rsv_start)
break;
}
- if (rp != NULL && rp->rsv_end != EXT2_RSV_NOT_ALLOCATED)
+ if (prev != rp && rp->rsv_end != EXT2_RSV_NOT_ALLOCATED)
ext2_remove_rsv_win(fs, rp);
rp->rsv_start = cur;
rp->rsv_end = cur + size - 1;
rp->rsv_alloc_hit = 0;
- ext2_add_rsv_win(fs, rp);
+ if (prev != rp)
+ RB_INSERT(ext2_rsv_win_tree, &fs->e2fs_rsv_tree, rp);
return (0);
}
-/*
- * Try to allocate a new reservation window.
- */
-static u_long
-ext2_alloc_new_rsv_win(struct inode *ip, struct ext2_rsv_win *rp, int32_t bpref,
- struct m_ext2fs *fs, int cg, struct buf *bp)
+static daddr_t
+ext2_search_next_block(struct m_ext2fs *fs, char *bbp, int bpref, int cg)
{
- struct ext2_rsv_win *search_rsv;
- struct ext2mount *ump;
- int size, ret;
- int start, end, loc, len, i, map;
- char *bbp;
+ daddr_t bno;
+ int start, loc, len, map, i;
- ump = ip->i_ump;
- bbp = (char *)bp->b_data;
- size = rp->rsv_goal_size;
+ start = bpref / NBBY;
+ len = howmany(fs->e2fs->e2fs_fpg, NBBY) - start;
+ loc = skpc(0xff, len, &bbp[start]);
+ if (loc == 0)
+ return (-1);
- EXT2_TREE_LOCK(fs);
-
- /* If tree is empty, then try to alloc according to bpref */
- if (RB_EMPTY(&fs->e2fs_rsv_tree)) {
- EXT2_TREE_UNLOCK(fs);
-
- if (bpref < 0 || dtog(fs, bpref) != cg)
- bpref = 0;
- if (bpref != 0) {
- bpref = dtogd(fs, bpref);
- if (isclr(bbp, bpref))
- goto gotit;
- }
- if (bpref)
- start = dtogd(fs, bpref) / NBBY;
- else
- start = 0;
- end = howmany(fs->e2fs->e2fs_fpg, NBBY) - start;
- for (loc = start; loc < end; loc++) {
- if (bbp[loc] == 0) {
- bpref = loc * NBBY;
- goto gotit;
- }
- }
-
- for (loc = 0; loc < start; loc++) {
- if (bbp[loc] == 0) {
- bpref = loc * NBBY;
- goto gotit;
- }
- }
-
- bpref = ext2_mapsearch(fs, bbp, bpref);
- if (bpref < 0)
- return (0);
- goto gotit;
- } else {
- if (bpref < 0)
- bpref = cg * fs->e2fs->e2fs_fpg + fs->e2fs->e2fs_first_dblock;
-
- search_rsv = ext2_search_rsv_win(&fs->e2fs_rsv_tree, bpref);
-
-repeat:
- ret = ext2_find_next_rsv_win(search_rsv, rp, fs, bpref, cg);
- if (ret < 0) {
- if (rp->rsv_end != EXT2_RSV_NOT_ALLOCATED)
- ext2_remove_rsv_win(fs, rp);
- EXT2_TREE_UNLOCK(fs);
-
- bpref = ext2_mapsearch(fs, bbp, bpref);
- if (bpref < 0)
- return (0);
- goto allocated;
- }
- EXT2_TREE_UNLOCK(fs);
-
- start = dtogd(fs, rp->rsv_start) / NBBY;
- len = howmany(fs->e2fs->e2fs_fpg, NBBY) - start;
- loc = skpc(0xff, len, &bbp[start]);
- if (loc == 0) {
- if (rp->rsv_end != EXT2_RSV_NOT_ALLOCATED) {
- EXT2_TREE_LOCK(fs);
- ext2_remove_rsv_win(fs, rp);
- EXT2_TREE_UNLOCK(fs);
- }
-
- bpref = ext2_mapsearch(fs, bbp, bpref);
- if (bpref < 0)
- return (0);
- goto allocated;
- }
- i = start + len - loc;
- map = bbp[i];
- bpref = i * NBBY;
- for (i = 1; i < (1 << NBBY); i <<= 1, bpref++)
- if ((map & i) == 0)
- break;
-
- start = cg * fs->e2fs->e2fs_fpg + fs->e2fs->e2fs_first_dblock + bpref;
- if (start >= rp->rsv_start &&
- start < rp->rsv_end) {
- rp->rsv_alloc_hit = start - rp->rsv_start + 1;
- goto allocated;
- }
-
- bpref = start;
- search_rsv = rp;
- EXT2_TREE_LOCK(fs);
- goto repeat;
+ i = start + len - loc;
+ map = bbp[i];
+ bno = i * NBBY;
+ for (i = 1; i < (1 << NBBY); i <<= 1, bno++) {
+ if ((map & i) == 0)
+ return (bno);
}
-gotit:
- rp->rsv_start = bpref + cg * fs->e2fs->e2fs_fpg + fs->e2fs->e2fs_first_dblock;
- rp->rsv_end = rp->rsv_start + size - 1;
- rp->rsv_alloc_hit = 0;
- EXT2_TREE_LOCK(fs);
- ext2_add_rsv_win(fs, rp);
- EXT2_TREE_UNLOCK(fs);
- rp->rsv_alloc_hit++;
-
-allocated:
- setbit(bbp, (daddr_t)bpref);
- EXT2_LOCK(ump);
- 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 + bpref);
+ return (-1);
}
-/*
- * Allocate a free block.
- */
-static u_long
-ext2_alloc_blk(struct m_ext2fs *fs, struct inode *ip, int cg,
- struct buf *bp, int32_t bpref, struct ext2_rsv_win *rp)
+static int
+ext2_alloc_new_rsv(struct inode *ip, int cg, struct buf *bp, int32_t bpref)
{
- struct ext2mount *ump;
- u_long start;
+ struct m_ext2fs *fs;
+ struct ext2_rsv_win *rp, *search;
char *bbp;
- daddr_t bno = -1;
- int size = EXT2_RSV_DEFAULT_RESERVE_BLKS;
+ int start, size, ret;
- ump = ip->i_ump;
- bbp = (char *)bp->b_data;
+ fs = ip->i_e2fs;
+ rp = ip->i_rsv;
+ bbp = bp->b_data;
+ size = rp->rsv_goal_size;
- if (rp->rsv_end != EXT2_RSV_NOT_ALLOCATED &&
- rp->rsv_alloc_hit >
- (rp->rsv_goal_size / 2)) {
- size = rp->rsv_goal_size * 2;
- if (size > EXT2_RSV_MAX_RESERVE_BLKS)
- size = EXT2_RSV_MAX_RESERVE_BLKS;
- rp->rsv_goal_size = size;
- }
+ if (bpref <= 0)
+ start = phy_blk(cg, fs);
+ else
+ start = bpref;
- if (dtog(fs, bpref) != cg)
- goto find;
+ EXT2_TREE_LOCK(fs);
- start = dtogd(fs, bpref);
+ search = ext2_search_rsv(&fs->e2fs_rsv_tree, start);
- if (isclr(bbp, start)) {
- bno = start;
- rp->rsv_alloc_hit++;
- goto gotit;
+repeat:
+ ret = ext2_find_rsv(search, rp, fs, start, cg);
+ if (ret < 0) {
+ if (rp->rsv_end != EXT2_RSV_NOT_ALLOCATED)
+ ext2_remove_rsv_win(fs, rp);
+ EXT2_TREE_UNLOCK(fs);
+ return (-1);
}
-
-find:
- if (rp->rsv_end != EXT2_RSV_NOT_ALLOCATED) {
+ EXT2_TREE_UNLOCK(fs);
+
+ start = dtogd(fs, rp->rsv_start);
+ start = ext2_search_next_block(fs, bbp, start, cg);
+ if (start < 0) {
EXT2_TREE_LOCK(fs);
- ext2_remove_rsv_win(fs, rp);
+ if (rp->rsv_end != EXT2_RSV_NOT_ALLOCATED)
+ ext2_remove_rsv_win(fs, rp);
EXT2_TREE_UNLOCK(fs);
+ return (-1);
}
- bno = ext2_mapsearch(fs, bbp, bpref);
- if (bno < 0)
+ start = phy_blk(cg, fs) + start;
+ if (start >= rp->rsv_start && start <= rp->rsv_end)
return (0);
-gotit:
- setbit(bbp, (daddr_t)bno);
- EXT2_LOCK(ump);
- 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);
+ search = rp;
+ EXT2_TREE_LOCK(fs);
+ goto repeat;
}
/*
@@ -423,21 +381,20 @@
struct buf *bp, int32_t bpref, int size)
{
struct ext2_rsv_win *rp;
+ int ret;
rp = ip->i_rsv;
+ if (rp == NULL)
+ return (ext2_alloc_blk(ip, cg, bp, bpref, NULL));
- /*
- * If window is empty or bpref is not in reservation window,
- * we will try to allocate a new reservation window.
- * Then we try to allocate a free block.
- */
- if (rp->rsv_end == EXT2_RSV_NOT_ALLOCATED)
- return (ext2_alloc_new_rsv_win(ip, rp, bpref, fs, cg, bp));
- else if (rp->rsv_start + rp->rsv_alloc_hit > rp->rsv_end)
- return (ext2_alloc_new_rsv_win(ip, rp, rp->rsv_end + 1, fs, cg, bp));
+ if (rp->rsv_end == EXT2_RSV_NOT_ALLOCATED ||
+ !ext2_bpref_in_rsv(rp, bpref)) {
+ ret = ext2_alloc_new_rsv(ip, cg, bp, bpref);
+ if (ret < 0)
+ return (0);
+ }
- return (ext2_alloc_blk(fs, ip, cg, bp,
- rp->rsv_start + rp->rsv_alloc_hit, rp));
+ return (ext2_alloc_blk(ip, cg, bp, bpref, rp));
}
/*
More information about the p4-projects
mailing list