PERFORCE change 177996 for review
Zheng Liu
lz at FreeBSD.org
Sun May 9 12:41:45 UTC 2010
http://p4web.freebsd.org/@@177996?ac=10
Change 177996 by lz at 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.
*
More information about the p4-projects
mailing list