Re: [PATCH 1/1] Extent overlap bugfix in ext4
On Wed, Jan 03, 2007 at 10:07:01AM -0800, Mingming Cao wrote:
Alex Tomas wrote:
I think that stuff that converts uninitialized blocks
to initialized ones should be a separate codepath and
shouldn't be done in the insert path. and an insert
(basic tree manipulation) should BUG_ON() one tries
to add extent with a block which is already covered
by the tree.
IMHO, get_blocks() should look like:
path = find_path()
if (found extent covers request block(s)) {
if (extent is uninitialized) {
convert();
}
}
where
function convert()
{
/* adopt existing extent so that it
* doesn't cover requested blocks */
/* insert head or tail of existing
* extent, if necessary */
/* insert new extent of initialized blocks */
}
thanks, Alex
I was thing about the same thing. The current ext4_ext_get_blocks()
function becomes very bulky. The code to convert uninitialized blocks to
initialized ones is pretty selfcontained, and worth the effort to put it
into a seperate function.
Ok. I will move this code to a new function.
--
Regards,
Amit Arora
-
To unsubscribe from this list: send the line unsubscribe linux-ext4 in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 1/1] Extent overlap bugfix in ext4
Mingming Cao (MC) writes: MC But the bug Amit pointed here is unrelated to the code convert MC uninitialized blocks to initialized ones. Rather, it's related to do MC multiple block allocation across on a window with parts already have MC blocks allocated. Without the check, the current code just simply MC allocate the requested extent and insert it into the tree which might MC overlap with existing extent. correct. thanks for catching. in delayed allocation patch get_blocks() isn't used and ext4_ext_walk_space() works right in this case. thanks, Alex - To unsubscribe from this list: send the line unsubscribe linux-ext4 in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 1/1] Extent overlap bugfix in ext4
Alex Tomas wrote: Mingming Cao (MC) writes: MC But the bug Amit pointed here is unrelated to the code convert MC uninitialized blocks to initialized ones. Rather, it's related to do MC multiple block allocation across on a window with parts already have MC blocks allocated. Without the check, the current code just simply MC allocate the requested extent and insert it into the tree which might MC overlap with existing extent. correct. thanks for catching. in delayed allocation patch get_blocks() isn't used and ext4_ext_walk_space() works right in this case. Yep, I realized that yesterday. That explains we never see this overlap problem when we testing extent+delalloc+mballoc last year. ext4_ext_walk_space did almost all the overlap check. I think we could reuse that code. Mingming thanks, Alex - To unsubscribe from this list: send the line unsubscribe linux-ext4 in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html - To unsubscribe from this list: send the line unsubscribe linux-ext4 in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH 1/1] Extent overlap bugfix in ext4
The ext4_ext_get_blocks() and ext4_ext_insert_extent() routines do not
check for extent overlap, when a new extent needs to be inserted in an
inode. An overlap is possible when the new extent being inserted has
ee_block that is not part of any of the existing extents, but the
tail/center portion of this new extent _is_. This is possible only when
we are writing/preallocating blocks across a hole.
This problem was first sighted while stress testing (using modified
fsx-linux stress test) persistent preallocation patches that I posted
earlier. Though I am not able to reproduce this bug (extent overlap)
without the persistent preallocation patches (because a write through a
hole results in get_blocks() of a single block at a time), but I think
that it is an independant problem and should be solved with a separate
patch. Hence this patch.
Comments please. Thanks!
Signed-off-by: Amit Arora ([EMAIL PROTECTED])
---
fs/ext4/extents.c | 71 +---
include/linux/ext4_fs_extents.h |1
2 files changed, 68 insertions(+), 4 deletions(-)
Index: linux-2.6.19.prealloc/fs/ext4/extents.c
===
--- linux-2.6.19.prealloc.orig/fs/ext4/extents.c2007-01-02
14:21:57.0 +0530
+++ linux-2.6.19.prealloc/fs/ext4/extents.c 2007-01-02 14:22:00.0
+0530
@@ -1119,6 +1119,44 @@
}
/*
+ * ext4_ext_check_overlap:
+ * check if a portion of the newext extent overlaps with an
+ * existing extent.
+ */
+struct ext4_extent * ext4_ext_check_overlap(struct inode *inode,
+ struct ext4_extent *newext)
+{
+ struct ext4_ext_path *path;
+ struct ext4_extent *ex;
+ unsigned int depth, b1, b2, len1;
+
+ b1 = le32_to_cpu(newext-ee_block);
+ len1 = le16_to_cpu(newext-ee_len);
+ path = ext4_ext_find_extent(inode, b1, NULL);
+ if (IS_ERR(path))
+ return NULL;
+
+ depth = ext_depth(inode);
+ ex = path[depth].p_ext;
+ if (!ex)
+ return NULL;
+
+ b2 = ext4_ext_next_allocated_block(path);
+ if (b2 == EXT_MAX_BLOCK)
+ return NULL;
+ path = ext4_ext_find_extent(inode, b2, path);
+ if (IS_ERR(path))
+ return NULL;
+ BUG_ON(path[depth].p_hdr == NULL);
+ ex = path[depth].p_ext;
+
+ if (b1 + len1 b2)
+ return ex;
+
+ return NULL;
+}
+
+/*
* ext4_ext_insert_extent:
* tries to merge requsted extent into the existing extent or
* inserts requested extent as new one into the tree,
@@ -1129,7 +1167,7 @@
struct ext4_extent *newext)
{
struct ext4_extent_header * eh;
- struct ext4_extent *ex, *fex;
+ struct ext4_extent *ex, *fex, *rex;
struct ext4_extent *nearex; /* nearest extent */
struct ext4_ext_path *npath = NULL;
int depth, len, err, next;
@@ -1139,6 +1177,18 @@
ex = path[depth].p_ext;
BUG_ON(path[depth].p_hdr == NULL);
+ /* check for overlap */
+ rex = ext4_ext_check_overlap(inode, newext);
+ if (rex) {
+ printk(KERN_ERR ERROR: ex=%u/%u overlaps newext=%u/%u\n,
+ le32_to_cpu(rex-ee_block),
+ le16_to_cpu(rex-ee_len),
+ le32_to_cpu(newext-ee_block),
+ le16_to_cpu(newext-ee_len));
+ ext4_ext_show_leaf(inode, path);
+ BUG();
+ }
+
/* try to insert block into found extent and return */
if (ex ext4_can_extents_be_merged(inode, ex, newext)) {
ext_debug(append %d block to %d:%d (from %llu)\n,
@@ -1921,7 +1971,7 @@
int create, int extend_disksize)
{
struct ext4_ext_path *path = NULL;
- struct ext4_extent newex, *ex;
+ struct ext4_extent newex, *ex, *ex2;
ext4_fsblk_t goal, newblock;
int err = 0, depth;
unsigned long allocated = 0;
@@ -1984,6 +2034,10 @@
*/
if (ee_len EXT_MAX_LEN)
goto out2;
+
+ if (iblock ee_block iblock + max_blocks = ee_block)
+ allocated = ee_block - iblock;
+
/* if found extent covers block, simply return it */
if (iblock = ee_block iblock ee_block + ee_len) {
newblock = iblock - ee_block + ee_start;
@@ -2016,7 +2070,17 @@
/* allocate new block */
goal = ext4_ext_find_goal(inode, path, iblock);
- allocated = max_blocks;
+
+ /* Check if we can really insert (iblock)::(iblock+max_blocks) extent */
+ newex.ee_block = cpu_to_le32(iblock);
+ if (!allocated) {
+ newex.ee_len = cpu_to_le16(max_blocks);
+ ex2 = ext4_ext_check_overlap(inode, newex);
+ if (ex2)
+
Re: [PATCH 1/1] Extent overlap bugfix in ext4
Amit K Arora (AKA) writes: AKA The ext4_ext_get_blocks() and ext4_ext_insert_extent() routines do not AKA check for extent overlap, when a new extent needs to be inserted in an AKA inode. An overlap is possible when the new extent being inserted has AKA ee_block that is not part of any of the existing extents, but the AKA tail/center portion of this new extent _is_. This is possible only when AKA we are writing/preallocating blocks across a hole. not sure I understand ... you shouldn't insert an extent that overlap any existing extent. when you write block(s), you first check is it already allocated and insert new extent only if it's not. for preallocated block(s), you should adapt existing extent(s) so that they don't overlap new extent you're inserting. am I missing something? also, I think that modification of existing extent(s) (not merging) isn't safe. thanks, Alex - To unsubscribe from this list: send the line unsubscribe linux-ext4 in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 1/1] Extent overlap bugfix in ext4
On Tue, Jan 02, 2007 at 12:25:21PM +0300, Alex Tomas (AT) wrote: Amit K Arora (AKA) writes: AKA The ext4_ext_get_blocks() and ext4_ext_insert_extent() routines do not AKA check for extent overlap, when a new extent needs to be inserted in an AKA inode. An overlap is possible when the new extent being inserted has AKA ee_block that is not part of any of the existing extents, but the AKA tail/center portion of this new extent _is_. This is possible only when AKA we are writing/preallocating blocks across a hole. AT not sure I understand ... you shouldn't insert an extent that overlap AT any existing extent. when you write block(s), you first check is AT it already allocated and insert new extent only if it's not. You are right. That is what this patch does. The current ext4 code is inserting an overlapped extent in a particular scenario (explained above). The suggested patch fixes this by having a check in get_blocks() for _not_ inserting an extent that may overlap with an existing one. AT for preallocated block(s), you should adapt existing extent(s) so that AT they don't overlap new extent you're inserting. am I missing something? The patch makes the new extent being inserted adjust its length based on any existing extent that may overlap, so that the overlap does not happen at all. AT also, I think that modification of existing extent(s) (not merging) AT isn't safe. The existing extent(s) are not being modified in any way here. We check if there is an overlap between the new extent being inserted by get_blocks(), with an existing one. If there is, we update the new extent (being inserted) accordingly. The existing extent is not touched (unless the insert_extent() does a merge, if possible). Please let me know if the intentions are still not clear here. Thanks! Regards, Amit Arora - To unsubscribe from this list: send the line unsubscribe linux-ext4 in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 1/1] Extent overlap bugfix in ext4
On Tue, 2007-01-02 at 14:39 +0530, Amit K. Arora wrote:
This problem was first sighted while stress testing (using modified
fsx-linux stress test) persistent preallocation patches that I posted
earlier. Though I am not able to reproduce this bug (extent overlap)
without the persistent preallocation patches (because a write through a
hole results in get_blocks() of a single block at a time), but I think
that it is an independant problem and should be solved with a separate
patch. Hence this patch.
Ah...without preallocation, I guess the problem still will be uncovered
when we have delayed allocation, that makes multiple block allocation
across hole possible.
/*
+ * ext4_ext_check_overlap:
+ * check if a portion of the newext extent overlaps with an
+ * existing extent.
+ */
+struct ext4_extent * ext4_ext_check_overlap(struct inode *inode,
+ struct ext4_extent *newext)
+{
+ struct ext4_ext_path *path;
+ struct ext4_extent *ex;
+ unsigned int depth, b1, b2, len1;
+
+ b1 = le32_to_cpu(newext-ee_block);
+ len1 = le16_to_cpu(newext-ee_len);
+ path = ext4_ext_find_extent(inode, b1, NULL);
+ if (IS_ERR(path))
+ return NULL;
+
+ depth = ext_depth(inode);
+ ex = path[depth].p_ext;
+ if (!ex)
+ return NULL;
+
I am confused, when we come here, isn't we confirmed that we need block
allocation, thus there is no extent start from b1?
+ b2 = ext4_ext_next_allocated_block(path);
+ if (b2 == EXT_MAX_BLOCK)
+
return NULL;
+ path = ext4_ext_find_extent(inode, b2, path);
+ if (IS_ERR(path))
+ return NULL;
+ BUG_ON(path[depth].p_hdr == NULL);
+ ex = path[depth].p_ext;
+
How useful to have the next extent pointer?It seems only used to print
out warning messages. I am a little concerned about the expensive
ext4_ext_find_extent(). After all ext4_ext_next_allocated_block()
already returns the start block of next extent, isn't it?
+ if (b1 + len1 b2)
+ return ex;
+
+ return NULL;
+}
+
+/*
* ext4_ext_insert_extent:
* tries to merge requsted extent into the existing extent or
* inserts requested extent as new one into the tree,
@@ -1129,7 +1167,7 @@
struct ext4_extent *newext)
{
struct ext4_extent_header * eh;
- struct ext4_extent *ex, *fex;
+ struct ext4_extent *ex, *fex, *rex;
struct ext4_extent *nearex; /* nearest extent */
struct ext4_ext_path *npath = NULL;
int depth, len, err, next;
@@ -1139,6 +1177,18 @@
ex = path[depth].p_ext;
BUG_ON(path[depth].p_hdr == NULL);
+ /* check for overlap */
+ rex = ext4_ext_check_overlap(inode, newext);
+ if (rex) {
+ printk(KERN_ERR ERROR: ex=%u/%u overlaps newext=%u/%u\n,
+ le32_to_cpu(rex-ee_block),
+ le16_to_cpu(rex-ee_len),
+ le32_to_cpu(newext-ee_block),
+ le16_to_cpu(newext-ee_len));
+ ext4_ext_show_leaf(inode, path);
+ BUG();
+ }
+
/* try to insert block into found extent and return */
if (ex ext4_can_extents_be_merged(inode, ex, newext)) {
ext_debug(append %d block to %d:%d (from %llu)\n,
@@ -1921,7 +1971,7 @@
int create, int extend_disksize)
{
struct ext4_ext_path *path = NULL;
- struct ext4_extent newex, *ex;
+ struct ext4_extent newex, *ex, *ex2;
ext4_fsblk_t goal, newblock;
int err = 0, depth;
unsigned long allocated = 0;
@@ -1984,6 +2034,10 @@
*/
if (ee_len EXT_MAX_LEN)
goto out2;
+
+ if (iblock ee_block iblock + max_blocks = ee_block)
+ allocated = ee_block - iblock;
+
/* if found extent covers block, simply return it */
if (iblock = ee_block iblock ee_block + ee_len) {
newblock = iblock - ee_block + ee_start;
@@ -2016,7 +2070,17 @@
/* allocate new block */
goal = ext4_ext_find_goal(inode, path, iblock);
- allocated = max_blocks;
+
+ /* Check if we can really insert (iblock)::(iblock+max_blocks) extent */
+ newex.ee_block = cpu_to_le32(iblock);
+ if (!allocated) {
+ newex.ee_len = cpu_to_le16(max_blocks);
+ ex2 = ext4_ext_check_overlap(inode, newex);
+ if (ex2)
+ allocated = le32_to_cpu(ex2-ee_block) - iblock;
+ else
+ allocated = max_blocks;
+ }
newblock = ext4_new_blocks(handle, inode, goal, allocated, err);
if (!newblock)
goto out2;
@@ -2024,7 +2088,6 @@
goal, newblock, allocated);
/* try to insert new extent into found leaf and return */
-
Re: [PATCH 1/1] Extent overlap bugfix in ext4
On Tue, Jan 02, 2007 at 05:35:28PM -0800, Mingming Cao wrote:
+struct ext4_extent * ext4_ext_check_overlap(struct inode *inode,
+ struct ext4_extent *newext)
+{
+ struct ext4_ext_path *path;
+ struct ext4_extent *ex;
+ unsigned int depth, b1, b2, len1;
+
+ b1 = le32_to_cpu(newext-ee_block);
+ len1 = le16_to_cpu(newext-ee_len);
+ path = ext4_ext_find_extent(inode, b1, NULL);
+ if (IS_ERR(path))
+ return NULL;
+
+ depth = ext_depth(inode);
+ ex = path[depth].p_ext;
+ if (!ex)
+ return NULL;
+
I am confused, when we come here, isn't we confirmed that we need block
allocation, thus there is no extent start from b1?
Yes, we are sure here that there is no extent which covers b1 block.
Since I couldn't find a direct way to get the next extent (extent on the
right from the would be position of the new extent in the tree), we
make a call to ext4_ext_find_extent() to get the extent on the left, and
then use this to call ext4_ext_next_allocated_block() to get the logical
block number (LBN) of the next extent in the tree. This LBN is
compared with the LBN of the new extent plus its length, to detect an
overlap.
+ b2 = ext4_ext_next_allocated_block(path);
+ if (b2 == EXT_MAX_BLOCK)
+
return NULL;
+ path = ext4_ext_find_extent(inode, b2, path);
+ if (IS_ERR(path))
+ return NULL;
+ BUG_ON(path[depth].p_hdr == NULL);
+ ex = path[depth].p_ext;
+
How useful to have the next extent pointer?It seems only used to print
out warning messages. I am a little concerned about the expensive
ext4_ext_find_extent(). After all ext4_ext_next_allocated_block()
already returns the start block of next extent, isn't it?
Ok, agreed. Will get rid of this extra code.
--
Regards,
Amit Arora
-
To unsubscribe from this list: send the line unsubscribe linux-ext4 in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
