Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1549151 > unrolled thread

[PATCH 0/3] ext4: fallocate insert/collapse range fixes

Back to article view | Back to linux.kernel

Contents

  [PATCH 0/3] ext4: fallocate insert/collapse range fixes Roman Pen <roman.penyaev@profitbricks.com> - 2017-01-02 14:00 +0100
    [PATCH 3/3] ext4: Find desired extent in ext4_ext_shift_extents() using binsearch Roman Pen <roman.penyaev@profitbricks.com> - 2017-01-02 14:00 +0100
      Re: [PATCH 3/3] ext4: Find desired extent in  ext4_ext_shift_extents() using binsearch Theodore Ts'o <tytso@mit.edu> - 2017-01-03 15:50 +0100
    [PATCH 2/3] ext4: Do not populate extents tree with outdated offsets while shifting extents Roman Pen <roman.penyaev@profitbricks.com> - 2017-01-02 14:00 +0100

#1549151 — [PATCH 0/3] ext4: fallocate insert/collapse range fixes

Hi all.

For couple of days I've played with inserting and collapsing range using
fallocate and have found two nasty bugs:

1.  On right shift (insert range) start block is not included in the range
and hole appears at the wrong offset.  The bug can be easily reproduced by
the following test:

    ptr = malloc(4096);
    assert(ptr);

    fd = open("./ext4.file", O_CREAT | O_TRUNC | O_RDWR, 0600);
    assert(fd >= 0);

    rc = fallocate(fd, 0, 0, 8192);
    assert(rc == 0);
    for (i = 0; i < 2048; i++)
            *((unsigned short *)ptr + i) = 0xbeef;
    rc = pwrite(fd, ptr, 4096, 0);
    assert(rc == 4096);
    rc = pwrite(fd, ptr, 4096, 4096);
    assert(rc == 4096);

    for (block = 2; block < 1000; block++) {
            rc = fallocate(fd, FALLOC_FL_INSERT_RANGE, 4096, 4096);
            assert(rc == 0);

            for (i = 0; i < 2048; i++)
                    *((unsigned short *)ptr + i) = block;

            rc = pwrite(fd, ptr, 4096, 4096);
            assert(rc == 4096);
    }

After the test no zero blocks should appear (test always does pwrite() after
fallocate), but zero blocks do exist:

  $ hexdump ./ext4.file | grep '0000 0000'

This bug is targeted by the first patch in the set.

2.  Inside ext4_ext_shift_extents() function ext4_find_extent() is called
without EXT4_EX_NOCACHE flag, which should prevent cache population.  This
leads to outdated offsets in the extents tree and wrong data blocks, which
can be observed doing read().  That is also quite well reproduced by the
test above.

This is fixed by the second patch.

3.  Just a minor optimization: linear search of a extent inside a block is
replaced by a binsearch.  This is the third patch.

Roman Pen (3):
  ext4: Include forgotten start block on fallocate insert range
  ext4: Do not populate extents tree with outdated offsets while
    shifting extents
  ext4: Find desired extent in ext4_ext_shift_extents() using binsearch

 fs/ext4/extents.c | 40 +++++++++++++++++++++++++++-------------
 1 file changed, 27 insertions(+), 13 deletions(-)

Signed-off-by: Roman Pen <roman.penyaev@profitbricks.com>
Cc: Namjae Jeon <namjae.jeon@samsung.com>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Andreas Dilger <adilger.kernel@dilger.ca>
Cc: linux-ext4@vger.kernel.org
Cc: linux-kernel@vger.kernel.org
-- 
2.10.2

[toc] | [next] | [standalone]

#1549152 — [PATCH 3/3] ext4: Find desired extent in ext4_ext_shift_extents() using binsearch

The aim of this patch is to optimize a search of an extent while
doing right shift using binsearch.

Cc: Namjae Jeon <namjae.jeon@samsung.com>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Andreas Dilger <adilger.kernel@dilger.ca>
Cc: linux-ext4@vger.kernel.org
Cc: linux-kernel@vger.kernel.org
---
 fs/ext4/extents.c | 13 +++++++++----
 1 file changed, 9 insertions(+), 4 deletions(-)

diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
index 9fbf92ca358c..f65cc2762780 100644
--- a/fs/ext4/extents.c
+++ b/fs/ext4/extents.c
@@ -5433,10 +5433,15 @@ ext4_ext_shift_extents(struct inode *inode, handle_t *handle,
 			else
 				/* Beginning is reached, end of the loop */
 				iterator = NULL;
-			/* Update path extent in case we need to stop */
-			while (le32_to_cpu(extent->ee_block) < start)
-				extent++;
-			path[depth].p_ext = extent;
+			if (le32_to_cpu(extent->ee_block) < start)
+				/*
+				 * Desired extent is somewhere in the middle,
+				 * do binsearch and update a path with it.
+				 */
+				ext4_ext_binsearch(inode, &path[depth], start);
+			else
+				/* Set the first extent */
+				path[depth].p_ext = extent;
 		}
 		ret = ext4_ext_shift_path_extents(path, shift, inode,
 				handle, SHIFT);
-- 
2.10.2

[toc] | [prev] | [next] | [standalone]

#1549833 — Re: [PATCH 3/3] ext4: Find desired extent in ext4_ext_shift_extents() using binsearch

On Mon, Jan 02, 2017 at 01:54:50PM +0100, Roman Pen wrote:
> The aim of this patch is to optimize a search of an extent while
> doing right shift using binsearch.
> 
> Cc: Namjae Jeon <namjae.jeon@samsung.com>
> Cc: "Theodore Ts'o" <tytso@mit.edu>
> Cc: Andreas Dilger <adilger.kernel@dilger.ca>
> Cc: linux-ext4@vger.kernel.org
> Cc: linux-kernel@vger.kernel.org

I would really appreciate it if patches that touch sensitive code (and
the extents manipulation code is an example of code which is fairly
subtle and fragile) are tested using xfstests first before you submit
them for review.  I've done a lot of work to make using xfstests
simple and easy for ext4 developers.  See:

	http://thunk.org/gce-xfstests

(especially the last slide :-).

BEGIN TEST 4k: Ext4 4k block Mon Jan  2 23:06:02 EST 2017
Failures: generic/061 generic/063 generic/075 generic/091 generic/112 generic/127 generic/231 generic/263 generic/389
BEGIN TEST 1k: Ext4 1k block Mon Jan  2 23:56:29 EST 2017
Failures: ext4/307 generic/013 generic/014 generic/016 generic/018 generic/020 generic/021 generic/022 generic/023
generic/024 generic/025 generic/028 generic/035 generic/036 generic/058 generic/060 generic/061 generic/063 generic/067
generic/070 generic/072 generic/074 generic/075 generic/077 generic/078 generic/080 generic/081 generic/082 generic/086
generic/087 generic/088 generic/089 generic/091 generic/092 generic/100 generic/112 generic/113 generic/114 generic/117
generic/123 generic/124 generic/126 generic/127 generic/131 generic/133 generic/184 generic/192 generic/193 generic/198
generic/207 generic/208 generic/209 generic/210 generic/211 generic/212 generic/213 generic/214 generic/215 generic/221
generic/228 generic/231 generic/233 generic/236 generic/237 generic/239 generic/240 generic/241 generic/245 generic/246
generic/247 generic/248 generic/249 generic/255 generic/256 generic/257 generic/258 generic/263 generic/269 generic/270
generic/273 generic/285 generic/286 generic/299 generic/300 generic/306 generic/308 generic/309 generic/310 generic/313
generic/314 generic/315 generic/316 generic/323 generic/355 generic/360 generic/361 generic/375 generic/378 generic/389
generic/391 shared/298

The 1k test failures look extremely scary, but that's because
generic/013 corrupted the file system, and caused all of the
subsequent tests using the test device to fail.  Of course, patches
_shouldn't_ be corrupting file systems.  That's a regression which
makes everyone said.  :-)

						- Ted

[toc] | [prev] | [next] | [standalone]

#1549153 — [PATCH 2/3] ext4: Do not populate extents tree with outdated offsets while shifting extents

Inside ext4_ext_shift_extents() function ext4_find_extent() is called
without EXT4_EX_NOCACHE flag, which should prevent cache population.

This leads to oudated offsets in the extents tree and wrong blocks
afterwards.

Patch fixes the problem providing EXT4_EX_NOCACHE flag for each
ext4_find_extents() call inside ext4_ext_shift_extents function.

Signed-off-by: Roman Pen <roman.penyaev@profitbricks.com>
Cc: Namjae Jeon <namjae.jeon@samsung.com>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Andreas Dilger <adilger.kernel@dilger.ca>
Cc: linux-ext4@vger.kernel.org
Cc: linux-kernel@vger.kernel.org
---
 fs/ext4/extents.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
index b4987ea2ca79..9fbf92ca358c 100644
--- a/fs/ext4/extents.c
+++ b/fs/ext4/extents.c
@@ -5344,7 +5344,8 @@ ext4_ext_shift_extents(struct inode *inode, handle_t *handle,
 	ext4_lblk_t stop, *iterator, ex_start, ex_end;
 
 	/* Let path point to the last extent */
-	path = ext4_find_extent(inode, EXT_MAX_BLOCKS - 1, NULL, 0);
+	path = ext4_find_extent(inode, EXT_MAX_BLOCKS - 1, NULL,
+				EXT4_EX_NOCACHE);
 	if (IS_ERR(path))
 		return PTR_ERR(path);
 
@@ -5360,7 +5361,8 @@ ext4_ext_shift_extents(struct inode *inode, handle_t *handle,
 	 * sure the hole is big enough to accommodate the shift.
 	*/
 	if (SHIFT == SHIFT_LEFT) {
-		path = ext4_find_extent(inode, start - 1, &path, 0);
+		path = ext4_find_extent(inode, start - 1, &path,
+					EXT4_EX_NOCACHE);
 		if (IS_ERR(path))
 			return PTR_ERR(path);
 		depth = path->p_depth;
@@ -5398,7 +5400,8 @@ ext4_ext_shift_extents(struct inode *inode, handle_t *handle,
 	 * becomes NULL to indicate the end of the loop.
 	 */
 	while (iterator && start <= stop) {
-		path = ext4_find_extent(inode, *iterator, &path, 0);
+		path = ext4_find_extent(inode, *iterator, &path,
+					EXT4_EX_NOCACHE);
 		if (IS_ERR(path))
 			return PTR_ERR(path);
 		depth = path->p_depth;
-- 
2.10.2

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web