Date: Sun, 6 Jun 2010 03:12:10 GMT From: Zheng Liu <lz@FreeBSD.org> To: Perforce Change Reviews <perforce@FreeBSD.org> Subject: PERFORCE change 179245 for review Message-ID: <201006060312.o563CAaO091966@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://p4web.freebsd.org/@@179245?ac=10 Change 179245 by lz@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)); } /*
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201006060312.o563CAaO091966>