The patch titled
ext3: more comments about block allocation/reservation code
has been added to the -mm tree. Its filename is
ext3-more-comments-about-block-allocation-reservation-code.patch
See http://www.zip.com.au/~akpm/linux/patches/stuff/added-to-mm.txt to find
out what to do about this
------------------------------------------------------
Subject: ext3: more comments about block allocation/reservation code
From: Mingming Cao <cmm@xxxxxxxxxx>
Add more comments in block allocation/reservation code.
Signed-off-by: Mingming Cao <cmm@xxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxx>
---
fs/ext3/balloc.c | 143 +++++++++++++++++++++++++++++++++++++--------
1 file changed, 119 insertions(+), 24 deletions(-)
diff -puN fs/ext3/balloc.c~ext3-more-comments-about-block-allocation-reservation-code fs/ext3/balloc.c
--- a/fs/ext3/balloc.c~ext3-more-comments-about-block-allocation-reservation-code
+++ a/fs/ext3/balloc.c
@@ -103,13 +103,19 @@ error_out:
* Operations include:
* dump, find, add, remove, is_empty, find_next_reservable_window, etc.
*
- * We use sorted double linked list for the per-filesystem reservation
- * window list. (like in vm_region).
+ * We use a red-black tree to represent per-filesystem reservation
+ * windows.
*
- * Initially, we keep those small operations in the abstract functions,
- * so later if we need a better searching tree than double linked-list,
- * we could easily switch to that without changing too much
- * code.
+ */
+
+/**
+ * __rsv_window_dump() -- Dump the filesystem block allocation
+ * reservation map
+ *
+ * if verbose is turned on, it will print the whole block reservation
+ * windows(start, end).
+ * Otherwise, it will only print out the "bad" windows: those window overlaps
+ * with it's immediate neighbors.
*/
#if 1
static void __rsv_window_dump(struct rb_root *root, int verbose,
@@ -161,6 +167,17 @@ restart:
#define rsv_window_dump(root, verbose) do {} while (0)
#endif
+/**
+ * goal_in_my_reservation() -- test if the given goal block (group relative)
+ * is within the file's own block reservation
+ * window range.
+ *
+ * if the reservation window is outside the goal allocation group, return 0;
+ * grp_goal (given goal block) could be -1, which means no specific
+ * goal block. In this case, always return 1.
+ * If the goal block is within the reservation window, return 1;
+ * otherwise, return 0;
+ */
static int
goal_in_my_reservation(struct ext3_reserve_window *rsv, ext3_grpblk_t grp_goal,
unsigned int group, struct super_block * sb)
@@ -216,6 +233,11 @@ search_reserve_window(struct rb_root *ro
return rsv;
}
+/**
+ * ext3_rsv_window_add() -- Insert a block window to the block
+ * reservation rb tree.
+ * Must be called with rsv_lock hold.
+ */
void ext3_rsv_window_add(struct super_block *sb,
struct ext3_reserve_window_node *rsv)
{
@@ -246,6 +268,12 @@ void ext3_rsv_window_add(struct super_bl
rb_insert_color(node, root);
}
+/**
+ * ext3_rsv_window_remove() -- Mark the block reservation window as
+ * uninitialized and unlink it from the filesystem reservation
+ * window rb tree.
+ * Must be called with rsv_lock hold.
+ */
static void rsv_window_remove(struct super_block *sb,
struct ext3_reserve_window_node *rsv)
{
@@ -255,11 +283,37 @@ static void rsv_window_remove(struct sup
rb_erase(&rsv->rsv_node, &EXT3_SB(sb)->s_rsv_window_root);
}
+/*
+ * rsv_is_empty() -- Check if the reservation window is allocated.
+ *
+ * returns 1 if the end block is EXT3_RESERVE_WINDOW_NOT_ALLOCATED.
+ */
static inline int rsv_is_empty(struct ext3_reserve_window *rsv)
{
/* a valid reservation end block could not be 0 */
return (rsv->_rsv_end == EXT3_RESERVE_WINDOW_NOT_ALLOCATED);
}
+
+/**
+ * ext3_init_block_alloc_info() -- Allocate and initialize the
+ * reservation window structure, and link the window to
+ * the ext3 inode structure at last
+ *
+ *
+ * The reservation window structure is only dynamically allocated
+ * and linked to ext3 inode whenever the first time the open file
+ * needs a new block. So, before every ext3_new_block(s) call, for
+ * regular files, we should check whether the reservation window
+ * structure exists or not. In the later case, this function is called.
+ * Fail to do so will result in block reservation turns off for that
+ * open file.
+ *
+ * This function is called from ext3_get_blocks_handle(), also called
+ * when setting the reservation window size through ioctl before the file
+ * is open for write (needs block allocation).
+ *
+ * Needs truncate_mutex protection prior to call this function.
+ */
void ext3_init_block_alloc_info(struct inode *inode)
{
struct ext3_inode_info *ei = EXT3_I(inode);
@@ -289,6 +343,16 @@ void ext3_init_block_alloc_info(struct i
ei->i_block_alloc_info = block_i;
}
+/**
+ * ext3_discard_reservation() -- discard(free) block reservation window
+ * on last file close.
+ *
+ * It is being called in three cases:
+ * ext3_release_file(): last writer close the file
+ * ext3_clear_inode(): last iput(), when nobody link to this file.
+ * ext3_truncate(): when the block indirect map is about to change.
+ *
+ */
void ext3_discard_reservation(struct inode *inode)
{
struct ext3_inode_info *ei = EXT3_I(inode);
@@ -543,6 +607,14 @@ static int ext3_test_allocatable(ext3_gr
return ret;
}
+/**
+ * bitmap_search_next_usable_block()
+ *
+ * The bitmap search --- search forward alternately through the actual
+ * bitmap and the last-committed copy, until we find a bit free in
+ * both bitmaps
+ */
+ while (start < maxblocks) {
static ext3_grpblk_t
bitmap_search_next_usable_block(ext3_grpblk_t start, struct buffer_head *bh,
ext3_grpblk_t maxblocks)
@@ -550,11 +622,6 @@ bitmap_search_next_usable_block(ext3_grp
ext3_grpblk_t next;
struct journal_head *jh = bh2jh(bh);
- /*
- * The bitmap search --- search forward alternately through the actual
- * bitmap and the last-committed copy until we find a bit free in
- * both
- */
while (start < maxblocks) {
next = ext3_find_next_zero_bit(bh->b_data, maxblocks, start);
if (next >= maxblocks)
@@ -570,8 +637,10 @@ bitmap_search_next_usable_block(ext3_grp
return -1;
}
-/*
- * Find an allocatable block in a bitmap. We honour both the bitmap and
+/**
+ * find_next_usable_block()
+ *
+ * Find an allocatable block in a bitmap. We honor both the bitmap and
* its last-committed copy (if that exists), and perform the "most
* appropriate allocation" algorithm of looking for a free block near
* the initial goal; then for a free byte somewhere in the bitmap; then
@@ -648,7 +717,19 @@ claim_block(spinlock_t *lock, ext3_grpbl
return ret;
}
-/*
+/**
+ * ext3_try_to_allocate()
+ *
+ * Attempt to allocate blocks within a give range. Set the range of allocation
+ * first, then find the first free bit(s) from the bitmap (within the range),
+ * and at last, allocate the blocks by claiming the found free bit as allocated.
+ *
+ * To set the range of this allocation:
+ * if there is a reservation window, only try to allocate block(s) from the
+ * file's own reservation window;
+ * Otherwise, the allocation range starts from the give goal block, ends at
+ * the block group's last block.
+ *
* If we failed to allocate the desired block then we may end up crossing to a
* new bitmap. In that case we must release write access to the old one via
* ext3_journal_release_buffer(), else we'll run out of credits.
@@ -1012,6 +1093,18 @@ retry:
goto retry;
}
+/**
+ * try_to_extend_reservation() -- try to expand the reservation window
+ * to large enough to have required number of free blocks
+ *
+ * Since ext3_try_to_allocate() will always allocate blocks within
+ * the reservation window range, if the window size is too small,
+ * multiple blocks allocation has to stop at the end of the reservation
+ * window. To make this more efficient, given the total number of
+ * blocks needed and the current size of the window, we try to
+ * expand the reservation window size if necessary on a best-effort
+ * basis before ext3_new_blocks() tries to allocate blocks,
+ */
static void try_to_extend_reservation(struct ext3_reserve_window_node *my_rsv,
struct super_block *sb, int size)
{
@@ -1053,9 +1146,7 @@ static void try_to_extend_reservation(st
* reservation), and there are lots of free blocks, but they are all
* being reserved.
*
- * We use a sorted double linked list for the per-filesystem reservation list.
- * The insert, remove and find a free space(non-reserved) operations for the
- * sorted double linked list should be fast.
+ * We use a red-black tree for the per-filesystem reservation list.
*
*/
static ext3_grpblk_t
@@ -1165,6 +1256,10 @@ out:
return ret;
}
+/**
+ * ext3_has_free_blocks() -- check if filesystem has at least 1 free block
+ * available for allocation.
+ */
static int ext3_has_free_blocks(struct ext3_sb_info *sbi)
{
ext3_fsblk_t free_blocks, root_blocks;
@@ -1195,13 +1290,13 @@ int ext3_should_retry_alloc(struct super
return journal_force_commit_nested(EXT3_SB(sb)->s_journal);
}
-/*
- * ext3_new_block uses a goal block to assist allocation. If the goal is
- * free, or there is a free block within 32 blocks of the goal, that block
- * is allocated. Otherwise a forward search is made for a free block; within
- * each block group the search first looks for an entire free byte in the block
- * bitmap, and then for any free bit if that fails.
- * This function also updates quota and i_blocks field.
+/**
+ * ext3_new_blocks() -- core block(s) allocation function
+ * ext3_new_blocks uses a goal block to assist allocation. It tries to
+ * allocate block(s) from the block group contains the goal block first. If that
+ * fails, it will try to allocate block(s) from other block groups without
+ * any specific goal block.
+ *
*/
ext3_fsblk_t ext3_new_blocks(handle_t *handle, struct inode *inode,
ext3_fsblk_t goal, unsigned long *count, int *errp)
_
Patches currently in -mm which might be from cmm@xxxxxxxxxx are
ext3-filesystem-bogus-enospc-with-reservation-fix.patch
ext3-and-jbd-cleanup-remove-whitespace.patch
fix-ext3-mounts-at-16t.patch
ext3-turn-on-reservation-dump-on-block-allocation-errors.patch
ext3-more-comments-about-block-allocation-reservation-code.patch
-
To unsubscribe from this list: send the line "unsubscribe mm-commits" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
