{"id":807453,"url":"http://patchwork.ozlabs.org/api/1.2/patches/807453/?format=json","web_url":"http://patchwork.ozlabs.org/project/linux-ext4/patch/1504079245-49002-2-git-send-email-adilger@dilger.ca/","project":{"id":8,"url":"http://patchwork.ozlabs.org/api/1.2/projects/8/?format=json","name":"Linux ext4 filesystem development","link_name":"linux-ext4","list_id":"linux-ext4.vger.kernel.org","list_email":"linux-ext4@vger.kernel.org","web_url":null,"scm_url":null,"webscm_url":null,"list_archive_url":"","list_archive_url_format":"","commit_url_format":""},"msgid":"<1504079245-49002-2-git-send-email-adilger@dilger.ca>","list_archive_url":null,"date":"2017-08-30T07:47:25","name":"[2/2] ext2fs: improve expand_dir performance","commit_ref":null,"pull_url":null,"state":"new","archived":true,"hash":"99d6d350ff23d918f93897906e1cce466368a8f3","submitter":{"id":4514,"url":"http://patchwork.ozlabs.org/api/1.2/people/4514/?format=json","name":"Andreas Dilger","email":"adilger@dilger.ca"},"delegate":null,"mbox":"http://patchwork.ozlabs.org/project/linux-ext4/patch/1504079245-49002-2-git-send-email-adilger@dilger.ca/mbox/","series":[{"id":539,"url":"http://patchwork.ozlabs.org/api/1.2/series/539/?format=json","web_url":"http://patchwork.ozlabs.org/project/linux-ext4/list/?series=539","date":"2017-08-30T07:47:24","name":"[1/2] e2fsck: set dir_nlink feature if large dir exists","version":1,"mbox":"http://patchwork.ozlabs.org/series/539/mbox/"}],"comments":"http://patchwork.ozlabs.org/api/patches/807453/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/807453/checks/","tags":{},"related":[],"headers":{"Return-Path":"","X-Original-To":"patchwork-incoming@ozlabs.org","Delivered-To":"patchwork-incoming@ozlabs.org","Authentication-Results":"ozlabs.org;\n\tspf=none (mailfrom) smtp.mailfrom=vger.kernel.org\n\t(client-ip=209.132.180.67; helo=vger.kernel.org;\n\tenvelope-from=linux-ext4-owner@vger.kernel.org;\n\treceiver=)","Received":["from vger.kernel.org (vger.kernel.org [209.132.180.67])\n\tby ozlabs.org (Postfix) with ESMTP id 3xhyJy6z4Xz9sQl\n\tfor ;\n\tWed, 30 Aug 2017 17:47:30 +1000 (AEST)","(majordomo@vger.kernel.org) by vger.kernel.org via listexpand\n\tid S1751319AbdH3Hr3 (ORCPT );\n\tWed, 30 Aug 2017 03:47:29 -0400","from smtp-out-so.shaw.ca ([64.59.136.139]:60430 \"EHLO\n\tsmtp-out-so.shaw.ca\" rhost-flags-OK-OK-OK-OK) by vger.kernel.org\n\twith ESMTP id S1751295AbdH3Hr1 (ORCPT\n\t); Wed, 30 Aug 2017 03:47:27 -0400","from cabot.adilger.int ([70.77.216.213]) by shaw.ca with SMTP\n\tid mxifdH92m8LPZmxigd0UKk; Wed, 30 Aug 2017 01:47:27 -0600"],"X-Authority-Analysis":"v=2.2 cv=e552ceh/ c=1 sm=1 tr=0\n\ta=BQvS1EmAg2ttxjPVUuc1UQ==:117 a=BQvS1EmAg2ttxjPVUuc1UQ==:17\n\ta=RPJ6JBhKAAAA:8\n\ta=ULcsCe1XLMSldBBj92kA:9 a=QhjkP-lwjAMRx4Pk:21 a=FRyFNhOFBSWwBmkO:21\n\ta=fa_un-3J20JGBB2Tu-mn:22","From":"Andreas Dilger ","To":"tytso@mit.edu","Cc":"linux-ext4@vger.kernel.org, Andreas Dilger ","Subject":"[PATCH 2/2] ext2fs: improve expand_dir performance","Date":"Wed, 30 Aug 2017 01:47:25 -0600","Message-Id":"<1504079245-49002-2-git-send-email-adilger@dilger.ca>","X-Mailer":"git-send-email 1.8.0","In-Reply-To":"<1504079245-49002-1-git-send-email-adilger@dilger.ca>","References":"<1504079245-49002-1-git-send-email-adilger@dilger.ca>","X-CMAE-Envelope":"MS4wfOVLdSgFkcwubjqwWM21YMO6qRGA66+mx15CwlV9fKnjNn5KqLAYNw0/bsfi1/pXExns9F67mmO+bzcVTW8HsPc9/l+BND+2puJ9F3XIFxknufX7YV2/\n\tztH6ZH993ppSG6579ImVVyNHeHfH5XY4vjKvOmCJHTxEpimCRPSyS4lipE6DvVIfET2mP711760BcxvxnOwDyOZ2ITZnS2zMAJiN3DZKEINlPCF7STdUKLET","Sender":"linux-ext4-owner@vger.kernel.org","Precedence":"bulk","List-ID":"","X-Mailing-List":"linux-ext4@vger.kernel.org"},"content":"Previously, ext2fs_expand_dir() in mke2fs and debugfs could\nonly add one block at a time after scanning the whole directory,\nwhich was very slow if a large number of directory leaf blocks\nare being added at once (in particular for the f_large_dir test).\n\nAdd a new ext2fs_expand_dir2() function that takes the number\nof blocks to add to the directory and add them all at once, and\ncall that from mke2fs (to create lost+found) and debugfs (with\nan optional 3rd argument to the \"expand_dir\" command).\n\nFix expand_dir_proc() to expand inline directories before trying\nto add more blocks, to distinguish between adding blocks and\nclusters, and not count added indirect/index blocks as leaves.\n\nHave create_lost_and_found() round up to a full bigalloc chunk,\nas there is little benefit if unused blocks in the same chunk\nare left \"free\" since they can't be used for anything else.\n\nThis speeds up f_large_dir with 65000 files from 4232s to 4141s.\n\nSigned-off-by: Andreas Dilger \n---\n debugfs/debugfs.8.in | 9 ++++++--\n debugfs/debugfs.c | 23 +++++++++++++++++----\n lib/ext2fs/expanddir.c | 53 ++++++++++++++++++++++++++++++++----------------\n lib/ext2fs/ext2fs.h | 2 ++\n misc/mke2fs.c | 27 +++++++++++++-----------\n tests/f_large_dir/script | 4 +---\n 6 files changed, 79 insertions(+), 39 deletions(-)","diff":"diff --git a/debugfs/debugfs.8.in b/debugfs/debugfs.8.in\nindex 87d487e..e3f54c1 100644\n--- a/debugfs/debugfs.8.in\n+++ b/debugfs/debugfs.8.in\n@@ -316,9 +316,14 @@ Remove the extended attribute\n .I attr_name\n from the file \\fIfilespec\\fR.\n .TP\n-.BI expand_dir \" filespec\"\n+.B expand_dir\n+.I filespec\n+.RI [ blocks_to_add ]\n Expand the directory\n-.IR filespec .\n+.I filespec\n+by\n+.I blocks_to_add\n+blocks, or 1 block if unspecified.\n .TP\n .BI fallocate \" filespec start_block [end_block]\n Allocate and map uninitialized blocks into \\fIfilespec\\fR between\ndiff --git a/debugfs/debugfs.c b/debugfs/debugfs.c\nindex 0a4b536..868cbbd 100644\n--- a/debugfs/debugfs.c\n+++ b/debugfs/debugfs.c\n@@ -1965,15 +1965,30 @@ void do_show_debugfs_params(int argc EXT2FS_ATTR((unused)),\n #ifndef READ_ONLY\n void do_expand_dir(int argc, char *argv[])\n {\n-\text2_ino_t inode;\n+\text2_ino_t ino;\n+\tint add_blocks;\n \tint retval;\n \n-\tif (common_inode_args_process(argc, argv, &inode, CHECK_FS_RW))\n+\tif (common_args_process(argc, argv, 2, 3, argv[0],\n+\t\t\t\t\" [blocks_to_add]\",\n+\t\t\t\tCHECK_FS_RW | CHECK_FS_BITMAPS))\n+\t\treturn;\n+\n+\tino = string_to_inode(argv[1]);\n+\tif (!ino)\n \t\treturn;\n \n-\tretval = ext2fs_expand_dir(current_fs, inode);\n+\tif (argc == 3) {\n+\t\tadd_blocks = parse_ulong(argv[2], argv[1], \"blocks_to_add\",\n+\t\t\t\t\t &retval);\n+\t\tif (retval)\n+\t\t\treturn;\n+\t} else {\n+\t\tadd_blocks = 1;\n+\t}\n+\tretval = ext2fs_expand_dir2(current_fs, ino, add_blocks);\n \tif (retval)\n-\t\tcom_err(\"ext2fs_expand_dir\", retval, 0);\n+\t\tcom_err(\"ext2fs_expand_dir2\", retval, 0);\n \treturn;\n }\n \ndiff --git a/lib/ext2fs/expanddir.c b/lib/ext2fs/expanddir.c\nindex 9f02312..d88861e 100644\n--- a/lib/ext2fs/expanddir.c\n+++ b/lib/ext2fs/expanddir.c\n@@ -21,11 +21,13 @@\n #include \"ext2fsP.h\"\n \n struct expand_dir_struct {\n-\tint\t\tdone;\n-\tint\t\tnewblocks;\n+\tunsigned\tdone:1;\n+\tunsigned\tclusters_added;\n \tblk64_t\t\tgoal;\n \terrcode_t\terr;\n \text2_ino_t\tdir;\n+\tunsigned\tblocks_to_add;\n+\tunsigned\tblocks_added;\n };\n \n static int expand_dir_proc(ext2_filsys\tfs,\n@@ -35,7 +37,7 @@ static int expand_dir_proc(ext2_filsys\tfs,\n \t\t\t int\t\tref_offset EXT2FS_ATTR((unused)),\n \t\t\t void\t\t*priv_data)\n {\n-\tstruct expand_dir_struct *es = (struct expand_dir_struct *) priv_data;\n+\tstruct expand_dir_struct *es = priv_data;\n \tblk64_t\tnew_blk;\n \tchar\t\t*block;\n \terrcode_t\tretval;\n@@ -46,30 +48,33 @@ static int expand_dir_proc(ext2_filsys\tfs,\n \t\treturn 0;\n \t}\n \tif (blockcnt &&\n-\t (EXT2FS_B2C(fs, es->goal) == EXT2FS_B2C(fs, es->goal+1)))\n-\t\tnew_blk = es->goal+1;\n-\telse {\n+\t (EXT2FS_B2C(fs, es->goal) == EXT2FS_B2C(fs, es->goal + 1))) {\n+\t\tnew_blk = es->goal + 1;\n+\t} else {\n \t\tes->goal &= ~EXT2FS_CLUSTER_MASK(fs);\n \t\tretval = ext2fs_new_block2(fs, es->goal, 0, &new_blk);\n \t\tif (retval) {\n \t\t\tes->err = retval;\n \t\t\treturn BLOCK_ABORT;\n \t\t}\n-\t\tes->newblocks++;\n+\t\tes->clusters_added++;\n \t\text2fs_block_alloc_stats2(fs, new_blk, +1);\n \t}\n \tif (blockcnt > 0) {\n+\t\tes->blocks_added++;\n \t\tretval = ext2fs_new_dir_block(fs, 0, 0, &block);\n \t\tif (retval) {\n \t\t\tes->err = retval;\n \t\t\treturn BLOCK_ABORT;\n \t\t}\n-\t\tes->done = 1;\n+\t\tes->done = (es->blocks_added >= es->blocks_to_add);\n \t\tretval = ext2fs_write_dir_block4(fs, new_blk, block, 0,\n \t\t\t\t\t\t es->dir);\n \t\text2fs_free_mem(&block);\n-\t} else\n+\t} else {\n+\t\t/* indirect or index block */\n \t\tretval = ext2fs_zero_blocks2(fs, new_blk, 1, NULL, NULL);\n+\t}\n \tif (blockcnt >= 0)\n \t\tes->goal = new_blk;\n \tif (retval) {\n@@ -84,10 +89,11 @@ static int expand_dir_proc(ext2_filsys\tfs,\n \t\treturn BLOCK_CHANGED;\n }\n \n-errcode_t ext2fs_expand_dir(ext2_filsys fs, ext2_ino_t dir)\n+errcode_t ext2fs_expand_dir2(ext2_filsys fs, ext2_ino_t dir,\n+\t\t\t unsigned blocks_to_add)\n {\n \terrcode_t\tretval;\n-\tstruct expand_dir_struct es;\n+\tstruct expand_dir_struct es = { 0 };\n \tstruct ext2_inode\tinode;\n \n \tEXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);\n@@ -98,6 +104,9 @@ errcode_t ext2fs_expand_dir(ext2_filsys fs, ext2_ino_t dir)\n \tif (!fs->block_map)\n \t\treturn EXT2_ET_NO_BLOCK_BITMAP;\n \n+\tif (blocks_to_add > fs->super->s_free_blocks_count)\n+\t\treturn EXT2_ET_DIR_NO_SPACE;\n+\n \tretval = ext2fs_check_directory(fs, dir);\n \tif (retval)\n \t\treturn retval;\n@@ -106,16 +115,19 @@ errcode_t ext2fs_expand_dir(ext2_filsys fs, ext2_ino_t dir)\n \tif (retval)\n \t\treturn retval;\n \n-\tes.done = 0;\n-\tes.err = 0;\n+\t/* expand inode inline data before starting iteration */\n+\tif (inode.i_flags & EXT4_INLINE_DATA_FL) {\n+\t\tretval = ext2fs_inline_data_expand(fs, dir);\n+\t\tif (retval)\n+\t\t\treturn retval;\n+\t\tblocks_to_add--;\n+\t}\n \tes.goal = ext2fs_find_inode_goal(fs, dir, &inode, 0);\n-\tes.newblocks = 0;\n \tes.dir = dir;\n+\tes.blocks_to_add = blocks_to_add;\n \n \tretval = ext2fs_block_iterate3(fs, dir, BLOCK_FLAG_APPEND,\n \t\t\t\t 0, expand_dir_proc, &es);\n-\tif (retval == EXT2_ET_INLINE_DATA_CANT_ITERATE)\n-\t\treturn ext2fs_inline_data_expand(fs, dir);\n \n \tif (es.err)\n \t\treturn es.err;\n@@ -129,8 +141,8 @@ errcode_t ext2fs_expand_dir(ext2_filsys fs, ext2_ino_t dir)\n \tif (retval)\n \t\treturn retval;\n \n-\tinode.i_size += fs->blocksize;\n-\text2fs_iblk_add_blocks(fs, &inode, es.newblocks);\n+\tinode.i_size += fs->blocksize * es.blocks_added;\n+\text2fs_iblk_add_blocks(fs, &inode, es.clusters_added);\n \n \tretval = ext2fs_write_inode(fs, dir, &inode);\n \tif (retval)\n@@ -138,3 +150,8 @@ errcode_t ext2fs_expand_dir(ext2_filsys fs, ext2_ino_t dir)\n \n \treturn 0;\n }\n+\n+errcode_t ext2fs_expand_dir(ext2_filsys fs, ext2_ino_t dir)\n+{\n+\treturn ext2fs_expand_dir2(fs, dir, 1);\n+}\ndiff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h\nindex b734f1a..0267660 100644\n--- a/lib/ext2fs/ext2fs.h\n+++ b/lib/ext2fs/ext2fs.h\n@@ -1194,6 +1194,8 @@ extern errcode_t ext2fs_dup_handle(ext2_filsys src, ext2_filsys *dest);\n \n /* expanddir.c */\n extern errcode_t ext2fs_expand_dir(ext2_filsys fs, ext2_ino_t dir);\n+extern errcode_t ext2fs_expand_dir2(ext2_filsys fs, ext2_ino_t dir,\n+\t\t\t\t unsigned blocks_to_add);\n \n /* ext_attr.c */\n extern __u32 ext2fs_ext_attr_hash_entry(struct ext2_ext_attr_entry *entry,\ndiff --git a/misc/mke2fs.c b/misc/mke2fs.c\nindex 85d88ed..2a83040 100644\n--- a/misc/mke2fs.c\n+++ b/misc/mke2fs.c\n@@ -507,18 +507,21 @@ static void create_lost_and_found(ext2_filsys fs)\n \t\texit(1);\n \t}\n \n-\tfor (i=1; i < EXT2_NDIR_BLOCKS; i++) {\n-\t\t/* Ensure that lost+found is at least 2 blocks, so we always\n-\t\t * test large empty blocks for big-block filesystems. */\n-\t\tif ((lpf_size += fs->blocksize) >= 16*1024 &&\n-\t\t lpf_size >= 2 * fs->blocksize)\n-\t\t\tbreak;\n-\t\tretval = ext2fs_expand_dir(fs, ino);\n-\t\tif (retval) {\n-\t\t\tcom_err(\"ext2fs_expand_dir\", retval, \"%s\",\n-\t\t\t\t_(\"while expanding /lost+found\"));\n-\t\t\texit(1);\n-\t\t}\n+\t/* Ensure that lost+found is at least 2 blocks, so we always\n+\t * test large empty blocks for big-block filesystems. */\n+\tlpf_size = EXT2_NDIR_BLOCKS;\n+\tif (lpf_size * fs->blocksize > 16 * 1024)\n+\t\tlpf_size = 16 * 1024 / fs->blocksize;\n+\tif (lpf_size < 2)\n+\t\tlpf_size = 2;\n+\n+\t/* round up size to full cluster, no point in making it smaller */\n+\tlpf_size = EXT2FS_C2B(fs, EXT2FS_B2C(fs, lpf_size - 1) + 1);\n+\tretval = ext2fs_expand_dir2(fs, ino, lpf_size - 1 /* initial block */);\n+\tif (retval) {\n+\t\tcom_err(\"ext2fs_expand_dir\", retval, \"%s\",\n+\t\t\t_(\"while expanding /lost+found\"));\n+\t\texit(1);\n \t}\n }\n \ndiff --git a/tests/f_large_dir/script b/tests/f_large_dir/script\nindex b25e106..1824778 100644\n--- a/tests/f_large_dir/script\n+++ b/tests/f_large_dir/script\n@@ -32,11 +32,9 @@ if [ $RC -eq 0 ]; then\n \techo \"cd /foo\"\n \ttouch $TMPFILE.tmp\n \techo \"write $TMPFILE.tmp foofile\"\n+\techo \"expand ./ $((DIRBLK))\"\n \ti=0\n \twhile test $i -lt $ENTRIES ; do\n-\t if test $((i % DIRENT_PER_LEAF)) -eq 0; then\n-\t \techo \"expand ./\"\n-\t fi\n \t if test $((i % 5000)) -eq 0 -a $SECONDS -ne $START; then\n \t\tELAPSED=$((SECONDS - START))\n \t\tRATE=$((i / ELAPSED))\n","prefixes":["2/2"]}