From owner-p4-projects@FreeBSD.ORG Sun May 9 12:41:44 2010 Return-Path: Delivered-To: p4-projects@freebsd.org Received: by hub.freebsd.org (Postfix, from userid 32767) id C7E1E1065678; Sun, 9 May 2010 12:41:44 +0000 (UTC) Delivered-To: perforce@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 8C1AD1065672 for ; Sun, 9 May 2010 12:41:44 +0000 (UTC) (envelope-from lz@FreeBSD.org) Received: from repoman.freebsd.org (repoman.freebsd.org [69.147.83.41]) by mx1.freebsd.org (Postfix) with ESMTP id 7957B8FC13 for ; Sun, 9 May 2010 12:41:44 +0000 (UTC) Received: from repoman.freebsd.org (localhost [127.0.0.1]) by repoman.freebsd.org (8.14.3/8.14.3) with ESMTP id o49CfiAE086325 for ; Sun, 9 May 2010 12:41:44 GMT (envelope-from lz@FreeBSD.org) Received: (from perforce@localhost) by repoman.freebsd.org (8.14.3/8.14.3/Submit) id o49CfihP086323 for perforce@freebsd.org; Sun, 9 May 2010 12:41:44 GMT (envelope-from lz@FreeBSD.org) Date: Sun, 9 May 2010 12:41:44 GMT Message-Id: <201005091241.o49CfihP086323@repoman.freebsd.org> X-Authentication-Warning: repoman.freebsd.org: perforce set sender to lz@FreeBSD.org using -f From: Zheng Liu To: Perforce Change Reviews Precedence: bulk Cc: Subject: PERFORCE change 177996 for review X-BeenThere: p4-projects@freebsd.org X-Mailman-Version: 2.1.5 List-Id: p4 projects tree changes List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 09 May 2010 12:41:45 -0000 http://p4web.freebsd.org/@@177996?ac=10 Change 177996 by lz@gnehzuil-freebsd on 2010/05/09 12:40:52 Now it will allocate a new block from reservation window when cylinder group has some free blocks. When a cylinder group is full, Finding another cylinder group's algorithm will be implemented. There are some bugs which need to test and debug. * Add some related functions * Find a block in reservation when cylinder group has some blocks * When reservation window is empty or bpref is not in reservation window, it will try to find a new space Affected files ... .. //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_alloc.c#5 edit Differences ... ==== //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_alloc.c#5 (text+ko) ==== @@ -61,12 +61,13 @@ static daddr_t ext2_nodealloccg(struct inode *, int, daddr_t, int); static daddr_t ext2_mapsearch(struct m_ext2fs *, char *, daddr_t); -static void ext2_rsv_win_remove(struct m_ext2fs *, struct ext2_rsv_win *); -static int ext2_in_rsv(struct ext2_rsv_win *, int32_t); -static u_long ext2_try_alloc_rsv(struct ext2_rsv_win *rwp, struct inode *, int, int32_t, int, - daddr_t (*allocator)(struct inode *, int, daddr_t, int)); -static daddr_t ext2_alloccg_rsv(struct inode *, int, daddr_t, int); -static int ext2_alloc_new_rsv(struct ext2_rsv_win *, struct m_ext2fs *, int, int32_t); +static void ext2_rsv_win_remove(struct m_ext2fs *, struct ext2_rsv_win *); +static int ext2_in_rsv(struct ext2_rsv_win *, int32_t); +static daddr_t ext2_alloccg_rsv(struct inode *, int, daddr_t, int); +static int ext2_alloc_new_rsv(struct inode *, struct m_ext2fs *, int, int32_t, int); +static int ext2_search_rsv_win(struct inode *, struct m_ext2fs *, int, int32_t, int); +static u_long ext2_bmap_search_free_block(struct m_ext2fs *, char *, daddr_t); +static void ext2_rsv_win_add(struct m_ext2fs *, struct ext2_rsv_win *); RB_GENERATE(ext2_rsv_win_tree, ext2_rsv_win, rw_link, ext2_rsv_win_cmp); @@ -131,6 +132,14 @@ } /* + * Add a ext2_rsv_win struct to RB tree. + */ +static void ext2_rsv_win_add(struct m_ext2fs *sbp, struct ext2_rsv_win *rwp) +{ + RB_INSERT(ext2_rsv_win_tree, &sbp->e2fs_tree, rwp); +} + +/* * Remove a ext2_rsv_win structure from RB tree. */ static void @@ -148,8 +157,7 @@ static int ext2_in_rsv(struct ext2_rsv_win *rwp, int32_t bpref) { - if (bpref < rwp->rw_start || - bpref > rwp->rw_end) + if (bpref < rwp->rw_start || bpref > rwp->rw_end) return 0; return 1; @@ -214,23 +222,172 @@ } /* - * Allocate a block in reservation window. + * Search a free block from bpref. + */ +static u_long ext2_bmap_search_free_block(struct m_ext2fs *sbp, char *bbp, daddr_t bpref) +{ + daddr_t bno; + int start, len, loc, i, map; + + /* + * find the fragment by searching through the free block + * map for an appropriate bit pattern + */ + if (bpref) + start = dtogd(sbp, bpref) / NBBY; + else + start = 0; + len = howmany(sbp->e2fs->e2fs_fpg, NBBY) - start; + loc = skpc(0xff, len, &bbp[start]); + if (loc == 0) { + len = start + 1; + start = 0; + loc = skpc(0xff, len, &bbp[start]); + if (loc == 0) { + printf("start = %d, len = %d, fs = %s\n", + start, len, sbp->e2fs_fsmnt); + panic("ext2fs_alloccg: map corrupted"); + /* NOTREACHED */ + } + } + i = start + len - loc; + map = bbp[i]; + bno = i * NBBY; + for (i = 1; i < (1 << NBBY); i <<= 1, bno++) { + if ((map & i) == 0) + return 1; + } + return 0; +} + +/* + * Find a reservation window which includes bpref. */ -static u_long -ext2_try_alloc_rsv(struct ext2_rsv_win *rwp, struct inode *ip, int cg, int32_t bpref, int size, - daddr_t (*allocator)(struct inode *, int, daddr_t, int)) +static int +ext2_search_rsv_win(struct inode *ip, struct m_ext2fs *sbp, int cg, int32_t bpref, int size) { - mtx_assert(EXT2_MTX(ip->i_ump), MA_OWNED); - return (*allocator)(ip, cg, bpref, size); + struct buf *bp; + struct ext2mount *ump; + struct ext2_rsv_win *rwp; + int error; + char *bbp; + + ump = ip->i_ump; + if (sbp->e2fs_gd[cg].ext2bgd_nbfree == 0) + return (0); + EXT2_UNLOCK(ump); + error = bread(ip->i_devvp, fsbtodb(sbp, + sbp->e2fs_gd[cg].ext2bgd_b_bitmap), + (int)sbp->e2fs_bsize, NOCRED, &bp); + if (error) { + brelse(bp); + EXT2_LOCK(ump); + return (0); + } + + bbp = (char *)bp->b_data; + + mtx_lock_spin(&sbp->e2fs_rsv_win_lock); + + /* If RB tree is empty, then it just need to search a free block and allocate it. + * else we need to traverse tree to find a space. + */ + if (RB_EMPTY(&sbp->e2fs_tree)) { + if (!ext2_bmap_search_free_block(sbp, bbp, bpref)) + goto failed; + + rwp = &ip->i_rsv_winp->rwi_entry; + rwp->rw_start = bpref; + rwp->rw_end = bpref + rwp->rw_goal_size - 1; + ext2_rsv_win_add(sbp, rwp); + + goto success; + } else { + int32_t curr; + struct ext2_rsv_win *search; + struct ext2_rsv_win *prev; + + search = RB_ROOT(&sbp->e2fs_tree); + do { + prev = search; + if (bpref < search->rw_start) + search = RB_LEFT(search, rw_link); + else if (bpref > search->rw_end) + search = RB_RIGHT(search, rw_link); + else + break; + } while (search); + + /* get bpref's previous reservation window */ + if (search == NULL) + search = prev; + + curr = bpref; + while (1) { + if (curr <= search->rw_end) + curr = search->rw_end + 1; + + if (curr > sbp->e2fs->e2fs_first_dblock + + cg * EXT2_BLOCKS_PER_GROUP(sbp)) + goto failed; + + search = RB_NEXT(ext2_rsv_win_tree, &sbp->e2fs_tree, search); + + /* reach the last reservation window */ + if (search == NULL) + break; + + /* found a space */ + if (curr + size < search->rw_start) + break; + } + + if (!ext2_bmap_search_free_block(sbp, bbp, bpref)) + goto failed; + + rwp = &ip->i_rsv_winp->rwi_entry; + rwp->rw_start = bpref; + rwp->rw_end = bpref + rwp->rw_goal_size - 1; + ext2_rsv_win_add(sbp, rwp); + + goto success; + } + +success: + mtx_unlock_spin(&sbp->e2fs_rsv_win_lock); + EXT2_LOCK(ump); + return 1; + +failed: + mtx_unlock_spin(&sbp->e2fs_rsv_win_lock); + EXT2_LOCK(ump); + return 0; } /* * Allocate a new reservation window. */ static int -ext2_alloc_new_rsv(struct ext2_rsv_win *rwp, struct m_ext2fs *sbp, int cg, int32_t bpref) +ext2_alloc_new_rsv(struct inode *ip, struct m_ext2fs *sbp, int cg, int32_t bpref, int size) { - return -1; + struct ext2_rsv_win *rwp; + + rwp = &ip->i_rsv_winp->rwi_entry; + + /* delete old reservation window */ + if (rwp->rw_end != EXT2_RWI_NOT_ALLOCATED) { + mtx_lock_spin(&sbp->e2fs_rsv_win_lock); + ext2_rsv_win_remove(sbp, &ip->i_rsv_winp->rwi_entry); + mtx_unlock_spin(&sbp->e2fs_rsv_win_lock); + } + + /* try to allocate a new reservation window in cg's group */ + if (ext2_search_rsv_win(ip, sbp, cg, bpref, size)) + return 1; + + /* XXX: force to allocate a new reservation window in next group */ + + return 0; } /* @@ -244,7 +401,7 @@ struct ext2mount *ump; struct ext2_rsv_win_info *rwip; int32_t bno; - int cg, ret; + int cg; *bnp = 0; fs = ip->i_e2fs; @@ -269,27 +426,26 @@ * Otherwise, try to allocate a new reservation window. */ if (rwip->rwi_entry.rw_end == EXT2_RWI_NOT_ALLOCATED || - !ext2_in_rsv(&rwip->rwi_entry, bpref)) { - ret = ext2_alloc_new_rsv(&rwip->rwi_entry, fs, cg, bpref); - } else { - bno = ext2_try_alloc_rsv(&rwip->rwi_entry, - ip, cg, bpref, size, ext2_alloccg_rsv); - } + !ext2_in_rsv(&rwip->rwi_entry, bpref)) + if (!ext2_alloc_new_rsv(ip, fs, cg, bpref, size)) + goto nospace; + + bno = ext2_alloccg_rsv(ip, cg, bpref, size); - bno = (daddr_t)ext2_hashalloc(ip, cg, bpref, fs->e2fs_bsize, - ext2_alloccg); if (bno > 0) { ip->i_blocks += btodb(fs->e2fs_bsize); ip->i_flag |= IN_CHANGE | IN_UPDATE; *bnp = bno; return (0); } + nospace: EXT2_UNLOCK(ump); ext2_fserr(fs, cred->cr_uid, "file system full"); uprintf("\n%s: write failed, file system is full\n", fs->e2fs_fsmnt); return (ENOSPC); } + /* * Allocate a block in the file system. *