merge extent blocks when possible
Subsystems (2)
PATCH 1/1 merge extent blocks when possible
Hi,
Please have a look at the patch attempting to handle the problem with deep extent tree.
Thanks, Alex
In some cases when a lot of extents are created initially by sparse file writes, they get merged over time, but there is no way to merge blocks in different indexes.
For example, if a file is written synchronously, all even blocks first, then odd blocks. The resulting extents tree looks like the following in "debugfs stat" output, often with only a single block in each index/leaf:
EXTENTS:
(ETB0):33796
(ETB1):33795
(0-677):2588672-2589349
(ETB1):2590753
(678):2589350
(ETB1):2590720
(679-1357):2589351-2590029
(ETB1):2590752
(1358):2590030
(ETB1):2590721
(1359-2037):2590031-2590709
(ETB1):2590751
(2038):2590710
(ETB1):2590722
:
:
With the patch applied the index and lead blocks are properly merged (0.6% slower under this random sync write workload, but later read IOPS are greatly reduced):
EXTENTS:
(ETB0):33796
(ETB1):2590736
(0-2047):2588672-2590719
(2048-11999):2592768-2602719
Originally the problem was hit with a real application operating on huge datasets and with just 27371 extents "inode has invalid extent depth: 6” problem occurred.
With the patch applied the application succeeded having finally 73637 in 3-level tree.
--- fs/ext4/extents.c | 185 ++++++++++++++++++++++++++++++++++++++++-- fs/jbd2/transaction.c | 1 + 2 files changed, 180 insertions(+), 6 deletions(-)
fs/ext4/extents.c +179 -6
@@ -1885,7 +1885,7 @@ static void ext4_ext_try_to_merge_up(handle_t *handle,* This function tries to merge the @ex extent to neighbours in the tree, then * tries to collapse the extent tree into the inode. */ -static void ext4_ext_try_to_merge (handle_t *handle, +static int ext4_ext_try_to_merge (handle_t *handle,struct inode *inode,struct ext4_ext_path *path,struct ext4_extent *ex)
@@ -1902,9 +1902,178 @@ static void ext4_ext_try_to_merge(handle_t *handle, merge_done =ext4_ext_try_to_merge_right (inode, path, ex -1 );if (!merge_done) - (void )ext4_ext_try_to_merge_right (inode, path, ex); + merge_done =ext4_ext_try_to_merge_right (inode, path, ex);ext4_ext_try_to_merge_up (handle, inode, path); + +return merge_done; +} + +/* +* This function tries to merge blocks from @path into @npath +*/ +static int ext4_ext_merge_blocks (handle_t *handle, +struct inode *inode, +struct ext4_ext_path *path, +struct ext4_ext_path *npath) +{ +unsigned int depth =ext_depth (inode); +int used, nused, free, i, k, err; +ext4_lblk_t next; + +if (path[depth].p_hdr == npath[depth].p_hdr) +return 0 ; + + used =le16_to_cpu (path[depth].p_hdr->eh_entries); + free =le16_to_cpu (npath[depth].p_hdr->eh_max) - +le16_to_cpu (npath[depth].p_hdr->eh_entries); +if (free < used) +return 0 ; + + err =ext4_ext_get_access (handle, inode, path + depth); +if (err) +return err; + err =ext4_ext_get_access (handle, inode, npath + depth); +if (err) +return err; + +/* move entries from the current leave to the next one */ + nused =le16_to_cpu (npath[depth].p_hdr->eh_entries); +memmove (EXT_FIRST_EXTENT (npath[depth].p_hdr) + used, +EXT_FIRST_EXTENT (npath[depth].p_hdr), + nused *sizeof (struct ext4_extent )); +memcpy (EXT_FIRST_EXTENT (npath[depth].p_hdr), +EXT_FIRST_EXTENT (path[depth].p_hdr), + used *sizeof (struct ext4_extent )); +le16_add_cpu (&npath[depth].p_hdr->eh_entries, used); +le16_add_cpu (&path[depth].p_hdr->eh_entries, -used); +ext4_ext_try_to_merge_right (inode, npath, +EXT_FIRST_EXTENT (npath[depth].p_hdr)); + + err =ext4_ext_dirty (handle, inode, path + depth); +if (err) +return err; + err =ext4_ext_dirty (handle, inode, npath + depth); +if (err) +return err; + +/* otherwise the index won't get corrected */ + npath[depth].p_ext =EXT_FIRST_EXTENT (npath[depth].p_hdr); + err =ext4_ext_correct_indexes (handle, inode, npath); +if (err) +return err; + +for (i = depth -1 ; i >=0 ; i--) { + + next =ext4_idx_pblock (path[i].p_idx); +ext4_free_blocks (handle, inode,NULL , next,1 , +EXT4_FREE_BLOCKS_METADATA | +EXT4_FREE_BLOCKS_FORGET ); + err =ext4_ext_get_access (handle, inode, path + i); +if (err) +return err; +le16_add_cpu (&path[i].p_hdr->eh_entries,-1 ); +if (le16_to_cpu (path[i].p_hdr->eh_entries) ==0 ) { +/* whole index block collapsed, go up */ +continue ; + } +/* remove index pointer */ + used =EXT_LAST_INDEX (path[i].p_hdr) - path[i].p_idx +1 ; +memmove (path[i].p_idx, path[i].p_idx +1 , + used *sizeof (struct ext4_extent_idx )); + + err =ext4_ext_dirty (handle, inode, path + i); +if (err) +return err; + +if (path[i].p_hdr == npath[i].p_hdr) +break ; + +/* try to move index pointers */ + used =le16_to_cpu (path[i].p_hdr->eh_entries); + free =le16_to_cpu (npath[i].p_hdr->eh_max) - +le16_to_cpu (npath[i].p_hdr->eh_entries); +if (used > free) +break ; + err =ext4_ext_get_access (handle, inode, npath + i); +if (err) +return err; +memmove (EXT_FIRST_INDEX (npath[i].p_hdr) + used, +EXT_FIRST_INDEX (npath[i].p_hdr), + npath[i].p_hdr->eh_entries *sizeof (struct ext4_extent_idx )); +memcpy (EXT_FIRST_INDEX (npath[i].p_hdr),EXT_FIRST_INDEX (path[i].p_hdr), + used *sizeof (struct ext4_extent_idx )); +le16_add_cpu (&path[i].p_hdr->eh_entries, -used); +le16_add_cpu (&npath[i].p_hdr->eh_entries, used); + err =ext4_ext_dirty (handle, inode, path + i); +if (err) +return err; + err =ext4_ext_dirty (handle, inode, npath + i); +if (err) +return err; + +/* correct index above */ +for (k = i; k >0 ; k--) { + err =ext4_ext_get_access (handle, inode, npath + k -1 ); +if (err) +return err; + npath[k-1 ].p_idx->ei_block = +EXT_FIRST_INDEX (npath[k].p_hdr)->ei_block; + err =ext4_ext_dirty (handle, inode, npath + k -1 ); +if (err) +return err; + } + } + +/* +* TODO: given we've got two paths, it should be possible to +* collapse those two blocks into the root one in some cases +*/ +return 1 ; +} + +static int ext4_ext_try_to_merge_blocks (handle_t *handle, +struct inode *inode, +struct ext4_ext_path *path) +{ +struct ext4_ext_path *npath =NULL ; +unsigned int depth =ext_depth (inode); +ext4_lblk_t next; +int used, rc =0 ; + +if (depth ==0 ) +return 0 ; + + used =le16_to_cpu (path[depth].p_hdr->eh_entries); +/* don't be too agressive as checking space in +* the next block is not free */ +if (used >ext4_ext_space_block (inode,0 ) /4 ) +return 0 ; + +/* try to merge to the next block */ + next =ext4_ext_next_leaf_block (path); +if (next ==EXT_MAX_BLOCKS ) +return 0 ; + npath =ext4_find_extent (inode, next,NULL ,0 ); +if (IS_ERR (npath)) +return 0 ; + rc =ext4_ext_merge_blocks (handle, inode, path, npath); +ext4_ext_drop_refs (npath); +kfree (npath); +if (rc) +return rc >0 ?0 : rc; + +/* try to merge with the previous block */ +if (EXT_FIRST_EXTENT (path[depth].p_hdr)->ee_block ==0 ) +return 0 ; + next =EXT_FIRST_EXTENT (path[depth].p_hdr)->ee_block -1 ; + npath =ext4_find_extent (inode, next,NULL ,0 ); +if (IS_ERR (npath)) +return 0 ; + rc =ext4_ext_merge_blocks (handle, inode, npath, path); +ext4_ext_drop_refs (npath); +kfree (npath); +return rc >0 ?0 : rc; }/*
@@ -1976,6 +2145,7 @@ int ext4_ext_insert_extent(handle_t *handle, struct inode *inode,int depth, len, err;ext4_lblk_t next;int mb_flags =0 , unwritten; +int merged =0 ;if (gb_flags &EXT4_GET_BLOCKS_DELALLOC_RESERVE ) mb_flags |=EXT4_MB_DELALLOC_RESERVED ;
@@ -2167,8 +2337,7 @@ int ext4_ext_insert_extent(handle_t *handle, struct inode *inode, merge:/* try to merge extents */ if (!(gb_flags &EXT4_GET_BLOCKS_PRE_IO )) -ext4_ext_try_to_merge (handle, inode, path, nearex); - + merged =ext4_ext_try_to_merge (handle, inode, path, nearex);/* time to correct all indexes above */ err =ext4_ext_correct_indexes (handle, inode, path);
@@ -2176,6 +2345,8 @@ int ext4_ext_insert_extent(handle_t *handle, struct inode *inode, goto cleanup; err =ext4_ext_dirty (handle, inode, path + path->p_depth); +if (!err && merged) + err =ext4_ext_try_to_merge_blocks (handle, inode, path); cleanup:ext4_free_ext_path (npath);
@@ -3765,7 +3936,8 @@ static int ext4_convert_unwritten_extents_endio(handle_t *handle,/* note: ext4_ext_correct_indexes() isn't needed here because * borders are not changed */ -ext4_ext_try_to_merge (handle, inode, path, ex); +if (ext4_ext_try_to_merge (handle, inode, path, ex)) +ext4_ext_try_to_merge_blocks (handle, inode, path);/* Mark modified extent as dirty */ err =ext4_ext_dirty (handle, inode, path + path->p_depth);
@@ -3828,7 +4000,8 @@ convert_initialized_extent(handle_t *handle, struct inode *inode,/* note: ext4_ext_correct_indexes() isn't needed here because * borders are not changed */ -ext4_ext_try_to_merge (handle, inode, path, ex); +if (ext4_ext_try_to_merge (handle, inode, path, ex)) +ext4_ext_try_to_merge_blocks (handle, inode, path);/* Mark modified extent as dirty */ err =ext4_ext_dirty (handle, inode, path + path->p_depth);
fs/jbd2/transaction.c +1 -0
@@ -513,6 +513,7 @@ handle_t *jbd2__journal_start(journal_t *journal, int nblocks, int rsv_blocks, } rsv_handle->h_reserved =1 ; rsv_handle->h_journal = journal; + rsv_handle->h_revoke_credits = revoke_records; handle->h_rsv_handle = rsv_handle; } handle->h_revoke_credits = revoke_records;
Signature · 1 line
2.40.1
Quoted 40 lines · Alex Zhuravlev
In some cases when a lot of extents are created initially by sparse file writes, they get merged over time, but there is no way to merge blocks in different indexes.
For example, if a file is written synchronously, all even blocks first, then odd blocks. The resulting extents tree looks like the following in "debugfs stat" output, often with only a single block in each index/leaf:
EXTENTS:
(ETB0):33796
(ETB1):33795
(0-677):2588672-2589349
(ETB1):2590753
(678):2589350
(ETB1):2590720
(679-1357):2589351-2590029
(ETB1):2590752
(1358):2590030
(ETB1):2590721
(1359-2037):2590031-2590709
(ETB1):2590751
(2038):2590710
(ETB1):2590722
:
:With the patch applied the index and lead blocks are properly merged (0.6% slower under this random sync write workload, but later read IOPS are greatly reduced):
EXTENTS:
(ETB0):33796
(ETB1):2590736
(0-2047):2588672-2590719
(2048-11999):2592768-2602719Originally the problem was hit with a real application operating on huge datasets and with just 27371 extents
Quoted 6 lines
inode has invalid extent depth: 6
problem occurred. With the patch applied the application succeeded having finally 73637 extents in 3-level tree.
Signed-off-by Alex Zhuravlev <[email protected]>
Quoted 258 lines
---
fs/ext4/extents.c| 185 ++++++++++++++++++++++++++++++++++++++++--fs/jbd2/transaction.c| 1 +2 files changed, 180 insertions(+), 6 deletions(-)fs/ext4/extents.c +172
-2@@ -1885,7 +1885,7 @@ static void ext4_ext_try_to_merge_up(handle_t *handle,* This function tries to merge the @ex extent to neighbours in the tree, then * tries to collapse the extent tree into the inode. */ -static void ext4_ext_try_to_merge (handle_t *handle, +static int ext4_ext_try_to_merge (handle_t *handle,struct inode *inode,struct ext4_ext_path *path,struct ext4_extent *ex)@@ -1902,9 +1902,178 @@ static void ext4_ext_try_to_merge(handle_t *handle, merge_done =ext4_ext_try_to_merge_right (inode, path, ex -1 );if (!merge_done) - (void )ext4_ext_try_to_merge_right (inode, path, ex); + merge_done =ext4_ext_try_to_merge_right (inode, path, ex);ext4_ext_try_to_merge_up (handle, inode, path); + +return merge_done; +} + +/* +* This function tries to merge blocks from @path into @npath +*/ +static int ext4_ext_merge_blocks (handle_t *handle, +struct inode *inode, +struct ext4_ext_path *path, +struct ext4_ext_path *npath) +{ +unsigned int depth =ext_depth (inode); +int used, nused, free, i, k, err; +ext4_lblk_t next; + +if (path[depth].p_hdr == npath[depth].p_hdr) +return 0 ; + + used =le16_to_cpu (path[depth].p_hdr->eh_entries); + free =le16_to_cpu (npath[depth].p_hdr->eh_max) - +le16_to_cpu (npath[depth].p_hdr->eh_entries); +if (free < used) +return 0 ; + + err =ext4_ext_get_access (handle, inode, path + depth); +if (err) +return err; + err =ext4_ext_get_access (handle, inode, npath + depth); +if (err) +return err; + +/* move entries from the current leave to the next one */ + nused =le16_to_cpu (npath[depth].p_hdr->eh_entries); +memmove (EXT_FIRST_EXTENT (npath[depth].p_hdr) + used, +EXT_FIRST_EXTENT (npath[depth].p_hdr), + nused *sizeof (struct ext4_extent )); +memcpy (EXT_FIRST_EXTENT (npath[depth].p_hdr), +EXT_FIRST_EXTENT (path[depth].p_hdr), + used *sizeof (struct ext4_extent )); +le16_add_cpu (&npath[depth].p_hdr->eh_entries, used); +le16_add_cpu (&path[depth].p_hdr->eh_entries, -used); +ext4_ext_try_to_merge_right (inode, npath, +EXT_FIRST_EXTENT (npath[depth].p_hdr)); + + err =ext4_ext_dirty (handle, inode, path + depth); +if (err) +return err; + err =ext4_ext_dirty (handle, inode, npath + depth); +if (err) +return err; + +/* otherwise the index won't get corrected */ + npath[depth].p_ext =EXT_FIRST_EXTENT (npath[depth].p_hdr); + err =ext4_ext_correct_indexes (handle, inode, npath); +if (err) +return err; + +for (i = depth -1 ; i >=0 ; i--) { + + next =ext4_idx_pblock (path[i].p_idx); +ext4_free_blocks (handle, inode,NULL , next,1 , +EXT4_FREE_BLOCKS_METADATA | +EXT4_FREE_BLOCKS_FORGET ); + err =ext4_ext_get_access (handle, inode, path + i); +if (err) +return err; +le16_add_cpu (&path[i].p_hdr->eh_entries,-1 ); +if (le16_to_cpu (path[i].p_hdr->eh_entries) ==0 ) { +/* whole index block collapsed, go up */ +continue ; + } +/* remove index pointer */ + used =EXT_LAST_INDEX (path[i].p_hdr) - path[i].p_idx +1 ; +memmove (path[i].p_idx, path[i].p_idx +1 , + used *sizeof (struct ext4_extent_idx )); + + err =ext4_ext_dirty (handle, inode, path + i); +if (err) +return err; + +if (path[i].p_hdr == npath[i].p_hdr) +break ; + +/* try to move index pointers */ + used =le16_to_cpu (path[i].p_hdr->eh_entries); + free =le16_to_cpu (npath[i].p_hdr->eh_max) - +le16_to_cpu (npath[i].p_hdr->eh_entries); +if (used > free) +break ; + err =ext4_ext_get_access (handle, inode, npath + i); +if (err) +return err; +memmove (EXT_FIRST_INDEX (npath[i].p_hdr) + used, +EXT_FIRST_INDEX (npath[i].p_hdr), + npath[i].p_hdr->eh_entries *sizeof (struct ext4_extent_idx )); +memcpy (EXT_FIRST_INDEX (npath[i].p_hdr),EXT_FIRST_INDEX (path[i].p_hdr), + used *sizeof (struct ext4_extent_idx )); +le16_add_cpu (&path[i].p_hdr->eh_entries, -used); +le16_add_cpu (&npath[i].p_hdr->eh_entries, used); + err =ext4_ext_dirty (handle, inode, path + i); +if (err) +return err; + err =ext4_ext_dirty (handle, inode, npath + i); +if (err) +return err; + +/* correct index above */ +for (k = i; k >0 ; k--) { + err =ext4_ext_get_access (handle, inode, npath + k -1 ); +if (err) +return err; + npath[k-1 ].p_idx->ei_block = +EXT_FIRST_INDEX (npath[k].p_hdr)->ei_block; + err =ext4_ext_dirty (handle, inode, npath + k -1 ); +if (err) +return err; + } + } + +/* +* TODO: given we've got two paths, it should be possible to +* collapse those two blocks into the root one in some cases +*/ +return 1 ; +} + +static int ext4_ext_try_to_merge_blocks (handle_t *handle, +struct inode *inode, +struct ext4_ext_path *path) +{ +struct ext4_ext_path *npath =NULL ; +unsigned int depth =ext_depth (inode); +ext4_lblk_t next; +int used, rc =0 ; + +if (depth ==0 ) +return 0 ; + + used =le16_to_cpu (path[depth].p_hdr->eh_entries); +/* don't be too agressive as checking space in +* the next block is not free */ +if (used >ext4_ext_space_block (inode,0 ) /4 ) +return 0 ; + +/* try to merge to the next block */ + next =ext4_ext_next_leaf_block (path); +if (next ==EXT_MAX_BLOCKS ) +return 0 ; + npath =ext4_find_extent (inode, next,NULL ,0 ); +if (IS_ERR (npath)) +return 0 ; + rc =ext4_ext_merge_blocks (handle, inode, path, npath); +ext4_ext_drop_refs (npath); +kfree (npath); +if (rc) +return rc >0 ?0 : rc; + +/* try to merge with the previous block */ +if (EXT_FIRST_EXTENT (path[depth].p_hdr)->ee_block ==0 ) +return 0 ; + next =EXT_FIRST_EXTENT (path[depth].p_hdr)->ee_block -1 ; + npath =ext4_find_extent (inode, next,NULL ,0 ); +if (IS_ERR (npath)) +return 0 ; + rc =ext4_ext_merge_blocks (handle, inode, npath, path); +ext4_ext_drop_refs (npath); +kfree (npath); +return rc >0 ?0 : rc; }/* @@ -1976,6 +2145,7 @@ int ext4_ext_insert_extent(handle_t *handle, struct inode *inode,int depth, len, err;ext4_lblk_t next;int mb_flags =0 , unwritten; +int merged =0 ;if (gb_flags &EXT4_GET_BLOCKS_DELALLOC_RESERVE ) mb_flags |=EXT4_MB_DELALLOC_RESERVED ;@@ -2167,8 +2337,7 @@ int ext4_ext_insert_extent(handle_t *handle, struct inode *inode,merge:
/* try to merge extents */ if (!(gb_flags & EXT4_GET_BLOCKS_PRE_IO))fs/ext4/extents.c +1
-2-ext4_ext_try_to_merge (handle, inode, path, nearex); - + merged =ext4_ext_try_to_merge (handle, inode, path, nearex);/* time to correct all indexes above */ err = ext4_ext_correct_indexes(handle, inode, path);fs/ext4/extents.c +2
-0@@ -2176,6 +2345,8 @@ int ext4_ext_insert_extent(handle_t *handle, struct inode *inode, goto cleanup; err =ext4_ext_dirty (handle, inode, path + path->p_depth); +if (!err && merged) + err =ext4_ext_try_to_merge_blocks (handle, inode, path);cleanup:
ext4_free_ext_path(npath);fs/ext4/extents.c +4
-2@@ -3765,7 +3936,8 @@ static int ext4_convert_unwritten_extents_endio(handle_t *handle,/* note: ext4_ext_correct_indexes() isn't needed here because * borders are not changed */ -ext4_ext_try_to_merge (handle, inode, path, ex); +if (ext4_ext_try_to_merge (handle, inode, path, ex)) +ext4_ext_try_to_merge_blocks (handle, inode, path);/* Mark modified extent as dirty */ err =ext4_ext_dirty (handle, inode, path + path->p_depth);@@ -3828,7 +4000,8 @@ convert_initialized_extent(handle_t *handle, struct inode *inode,/* note: ext4_ext_correct_indexes() isn't needed here because * borders are not changed */ -ext4_ext_try_to_merge (handle, inode, path, ex); +if (ext4_ext_try_to_merge (handle, inode, path, ex)) +ext4_ext_try_to_merge_blocks (handle, inode, path);/* Mark modified extent as dirty */ err =ext4_ext_dirty (handle, inode, path + path->p_depth);fs/jbd2/transaction.c +1
-1@@ -513,6 +513,7 @@ handle_t *jbd2__journal_start(journal_t *journal, int nblocks, int rsv_blocks, } rsv_handle->h_reserved =1 ; rsv_handle->h_journal = journal; + rsv_handle->h_revoke_credits = revoke_records; handle->h_rsv_handle = rsv_handle; } handle->h_revoke_credits = revoke_records; --
Quoted 2 lines
2.40.1
Cheers, Andreas