[{"id":1751438,"web_url":"http://patchwork.ozlabs.org/comment/1751438/","msgid":"<3016732A-E5AA-4EE7-980A-05323CD346A6@dilger.ca>","list_archive_url":null,"date":"2017-08-18T18:45:21","subject":"Re: [PATCH] e2fsck: set dir_nlink feature if large dir exists","submitter":{"id":4514,"url":"http://patchwork.ozlabs.org/api/people/4514/","name":"Andreas Dilger","email":"adilger@dilger.ca"},"content":"On Aug 18, 2017, at 12:19 PM, Andreas Dilger wrote:\n> \n> If there is a directory with more than EXT2_LINK_MAX (65000)\n> subdirectories, but the DIR_NLINK feature is not set in the\n> superblock, the feature should be set before continuing on\n> to change the on-disk directory link count to 1.\n> \n> While most filesystems should have DIR_NLINK set (it was set\n> by default for all ext4 filesystems, and the kernel before\n> 4.12 automatically set it if the directory link count grew\n> too large), it is possible that this flag is lost due to disk\n> corruption or for an upgraded filesystem. We no longer want\n> the kernel to automatically enable this feature.\n> \n> Addresses: https://bugzilla.kernel.org/show_bug.cgi?id=196405\n> Signed-off-by: Andreas Dilger \n> ---\n\nNote that this is using the f_large_dir test for verification,\nsince it was already creating a directory with 48k entries in\nit and already took ages to run because directory processing\nin libext2fs is O(n^2) (it took about 2h to finish in my VM).\nThe alternative is storing a 100MB image file (though it may\nbe possible to compress it significantly).\n\nI'm working on a patch to improve the debugfs \"expand\" command\nso that it can insert multiple directory blocks at once, rather\nthan one-at-a-time (after a full directory scan). That at least\nfixes half of the problem.\n\nCheers, Andreas\n\n> e2fsck/pass4.c | 12 +++++++++-\n> e2fsck/problem.c | 5 ++++\n> e2fsck/problem.h | 3 +++\n> tests/f_large_dir/expect | 7 ++++--\n> tests/f_large_dir/script | 60 ++++++++++++++++++++++++++++++------------------\n> 5 files changed, 62 insertions(+), 25 deletions(-)\n> \n> diff --git a/e2fsck/pass4.c b/e2fsck/pass4.c\n> index 663f87a..d0ff8e9 100644\n> --- a/e2fsck/pass4.c\n> +++ b/e2fsck/pass4.c\n> @@ -170,6 +170,7 @@ void e2fsck_pass4(e2fsck_t ctx)\n> #endif\n> \tstruct problem_context\tpctx;\n> \t__u16\tlink_count, link_counted;\n> +\tint dir_nlink_fs;\n> \tchar\t*buf = 0;\n> \tdgrp_t\tgroup, maxgroup;\n> \n> @@ -193,6 +194,8 @@ void e2fsck_pass4(e2fsck_t ctx)\n> \tif (!(ctx->options & E2F_OPT_PREEN))\n> \t\tfix_problem(ctx, PR_4_PASS_HEADER, &pctx);\n> \n> +\tdir_nlink_fs = ext2fs_has_feature_dir_nlink(fs->super);\n> +\n> \tgroup = 0;\n> \tmaxgroup = fs->group_desc_count;\n> \tif (ctx->progress)\n> @@ -249,8 +252,15 @@ void e2fsck_pass4(e2fsck_t ctx)\n> \t\t\t\t\t &link_counted);\n> \t\t}\n> \t\tisdir = ext2fs_test_inode_bitmap2(ctx->inode_dir_map, i);\n> -\t\tif (isdir && (link_counted > EXT2_LINK_MAX))\n> +\t\tif (isdir && (link_counted > EXT2_LINK_MAX)) {\n> +\t\t\tif (!dir_nlink_fs &&\n> +\t\t\t fix_problem(ctx, PR_4_DIR_NLINK_FEATURE, &pctx)) {\n> +\t\t\t\text2fs_set_feature_dir_nlink(fs->super);\n> +\t\t\t\text2fs_mark_super_dirty(fs);\n> +\t\t\t\tdir_nlink_fs = 1;\n> +\t\t\t}\n> \t\t\tlink_counted = 1;\n> +\t\t}\n> \t\tif (link_counted != link_count) {\n> \t\t\te2fsck_read_inode_full(ctx, i, EXT2_INODE(inode),\n> \t\t\t\t\t inode_size, \"pass4\");\n> diff --git a/e2fsck/problem.c b/e2fsck/problem.c\n> index 9706933..25c1de9 100644\n> --- a/e2fsck/problem.c\n> +++ b/e2fsck/problem.c\n> @@ -1873,6 +1873,11 @@ static struct e2fsck_problem problem_table[] = {\n> \t N_(\"@a @i %i ref count is %N, @s %n. \"),\n> \t PROMPT_FIX, PR_PREEN_OK },\n> \n> +\t/* directory exceeds max links, but no DIR_NLINK feature in superblock*/\n> +\t{ PR_4_DIR_NLINK_FEATURE,\n> +\t N_(\"@d exceeds max links, but no DIR_NLINK feature in @S.\\n\"),\n> +\t PROMPT_FIX, 0 },\n> +\n> \t/* Pass 5 errors */\n> \n> \t/* Pass 5: Checking group summary information */\n> diff --git a/e2fsck/problem.h b/e2fsck/problem.h\n> index f30f8f0..07ed0a7 100644\n> --- a/e2fsck/problem.h\n> +++ b/e2fsck/problem.h\n> @@ -1134,6 +1134,9 @@ struct problem_context {\n> /* Extended attribute inode ref count wrong */\n> #define PR_4_EA_INODE_REF_COUNT\t\t0x040005\n> \n> +/* directory exceeds max links, but no DIR_NLINK feature in superblock */\n> +#define PR_4_DIR_NLINK_FEATURE\t\t0x040006\n> +\n> /*\n> * Pass 5 errors\n> */\n> diff --git a/tests/f_large_dir/expect b/tests/f_large_dir/expect\n> index b099460..4b9ca6f 100644\n> --- a/tests/f_large_dir/expect\n> +++ b/tests/f_large_dir/expect\n> @@ -3,10 +3,13 @@ Pass 2: Checking directory structure\n> Pass 3: Checking directory connectivity\n> Pass 3A: Optimizing directories\n> Pass 4: Checking reference counts\n> -Inode 13 ref count is 1, should be 47245. Fix? yes\n> +Directory exceeds max links, but no DIR_NLINK feature in superblock.\n> +Fix? yes\n> +\n> +Inode 12 ref count is 65012, should be 1. Fix? yes\n> \n> Pass 5: Checking group summary information\n> \n> test.img: ***** FILE SYSTEM WAS MODIFIED *****\n> -test.img: 13/115368 files (0.0% non-contiguous), 32817/460800 blocks\n> +test.img: 65023/65104 files (0.0% non-contiguous), 96668/100937 blocks\n> Exit status is 1\n> diff --git a/tests/f_large_dir/script b/tests/f_large_dir/script\n> index 0b5fdff..a10fe16 100644\n> --- a/tests/f_large_dir/script\n> +++ b/tests/f_large_dir/script\n> @@ -5,43 +5,59 @@ E2FSCK=../e2fsck/e2fsck\n> NAMELEN=255\n> DIRENT_SZ=8\n> BLOCKSZ=1024\n> +INODESZ=128\n> DIRENT_PER_LEAF=$((BLOCKSZ / (NAMELEN + DIRENT_SZ)))\n> HEADER=32\n> INDEX_SZ=8\n> INDEX_L1=$(((BLOCKSZ - HEADER) / INDEX_SZ))\n> INDEX_L2=$(((BLOCKSZ - DIRENT_SZ) / INDEX_SZ))\n> ENTRIES=$((INDEX_L1 * INDEX_L2 * DIRENT_PER_LEAF))\n> +DIRBLK=$((2 + INDEX_L1 * INDEX_L2))\n> +EXT4_LINK_MAX=65000\n> +[ $ENTRIES -lt $((EXT4_LINK_MAX + 10)) ] && ENTRIES=$((EXT4_LINK_MAX + 10))\n> +FSIZE=$(((DIRBLK + EXT4_LINK_MAX * ((BLOCKSZ + INODESZ) / BLOCKSZ)) * 5 / 4))\n> \n> -cp /dev/null $OUT\n> -$MKE2FS -b 1024 -O large_dir,uninit_bg,dir_nlink -F $TMPFILE 460800 \\\n> -\t> /dev/null 2>&1\n> +> $OUT\n> +$MKE2FS -b 1024 -O large_dir,uninit_bg -N $((ENTRIES + 50)) \\\n> +\t-I $INODESZ -F $TMPFILE $FSIZE > $OUT 2>&1\n> +RC=$?\n> +if [ $RC -eq 0 ]; then\n> {\n> -\techo \"feature large_dir\"\n> +\tSTART=$SECONDS\n> \techo \"mkdir /foo\"\n> \techo \"cd /foo\"\n> -\ttouch foofile\n> -\techo \"write foofile foofile\"\n> +\ttouch $TMPFILE.tmp\n> +\techo \"write $TMPFILE.tmp foofile\"\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> +\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 $i -gt 0 ; then\n> -\t\t>&2 echo \"$test_name: $i processed\"\n> +\t if test $((i % 5000)) -eq 0 -a $i -gt 0; then\n> +\t\tELAPSED=$((SECONDS - START))\n> +\t\tRATE=$((i / ELAPSED))\n> +\t\t>&2 echo \"$test_name: $i processed in ${ELAPSED}s @ $RATE/s\"\n> \t fi\n> -\t printf \"ln foofile %0255X\\n\" $i\n> -\t i=$(($i + 1))\n> +\t if test $i -lt $((EXT4_LINK_MAX + 10)); then\n> +\t\tprintf \"mkdir d%0254u\\n\" $i\n> +\t else\n> +\t\tprintf \"ln foofile f%0254u\\n\" $i\n> +\t fi\n> +\t i=$((i + 1))\n> \tdone\n> -} | $DEBUGFS -w -f /dev/stdin $TMPFILE > /dev/null 2>&1\n> -\n> -$E2FSCK -yfD $TMPFILE > $OUT.new 2>&1\n> -status=$?\n> -echo Exit status is $status >> $OUT.new\n> -sed -f $cmd_dir/filter.sed -e \"s;$TMPFILE;test.img;\" $OUT.new >> $OUT\n> -rm -f $OUT.new\n> +} | $DEBUGFS -w -f /dev/stdin $TMPFILE > $OUT\n> +\tRC=$?\n> +fi\n> +if [ $RC -eq 0 ]; then\n> +\t$E2FSCK -yfD $TMPFILE > $OUT.new 2>&1\n> +\tstatus=$?\n> +\techo \"Exit status is $status\" >> $OUT.new\n> +\tsed -f $cmd_dir/filter.sed -e \"s;$TMPFILE;test.img;\" $OUT.new > $OUT\n> +\trm -f $OUT.new\n> \n> -cmp -s $OUT $EXP\n> -RC=$?\n> +\tcmp -s $OUT $EXP\n> +\tRC=$?\n> +fi\n> if [ $RC -eq 0 ]; then\n> \techo \"$test_name: $test_description: ok\"\n> \ttouch $test_name.ok\n> --\n> 1.8.0\n> \n\n\nCheers, Andreas","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=)","ozlabs.org; dkim=pass (2048-bit key;\n\tunprotected) header.d=dilger-ca.20150623.gappssmtp.com\n\theader.i=@dilger-ca.20150623.gappssmtp.com\n\theader.b=\"zNURICSt\"; dkim-atps=neutral"],"Received":["from vger.kernel.org (vger.kernel.org [209.132.180.67])\n\tby ozlabs.org (Postfix) with ESMTP id 3xYsTm0lLyz9t3k\n\tfor ;\n\tSat, 19 Aug 2017 04:45:32 +1000 (AEST)","(majordomo@vger.kernel.org) by vger.kernel.org via listexpand\n\tid S1751126AbdHRSpa (ORCPT );\n\tFri, 18 Aug 2017 14:45:30 -0400","from mail-io0-f195.google.com ([209.85.223.195]:38746 \"EHLO\n\tmail-io0-f195.google.com\" rhost-flags-OK-OK-OK-OK) by vger.kernel.org\n\twith ESMTP id S1750971AbdHRSpa (ORCPT\n\t); Fri, 18 Aug 2017 14:45:30 -0400","by mail-io0-f195.google.com with SMTP id g71so29480ioe.5\n\tfor ;\n\tFri, 18 Aug 2017 11:45:30 -0700 (PDT)","from cabot-wlan.adilger.int (S0106a84e3fe4b223.cg.shawcable.net.\n\t[70.77.216.213]) by smtp.gmail.com with ESMTPSA id\n\tq68sm2807100iof.79.2017.08.18.11.45.27\n\t(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);\n\tFri, 18 Aug 2017 11:45:27 -0700 (PDT)"],"DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n\td=dilger-ca.20150623.gappssmtp.com; s=20150623;\n\th=from:message-id:mime-version:subject:date:in-reply-to:cc:to\n\t:references; bh=RnWGg8mQBqjKGyZtZ19dK3qmY7sWlPn/opsfUOGn4jE=;\n\tb=zNURICStvKiRv6H7VyIsbqO/g2UffImnw5reOwWNhwJ0SH7TaxivbIZ17tpmmgbDkW\n\tuKqPSduB2ArEv2HwVQHTXozXiicjzqEfze76MbVmY3D0rTnsJe0CKH4M2GeZW5YlK4Ym\n\tj9rnd2lDNuXwJHowMF4e97lhqSqqy8NEz4rfc0/CqPzshMpKtyLLceXyux/Uji5BiD1b\n\ttuMDeMV0KnQ/8n/cmt9oVsFE41ctDrMBFwwd/UUbaM8qt+GiY84CpZkk4NDTwBPWUedQ\n\tQrp3E9+uCeJxx33yM0BioyiTaz117MhoitrFhTNouvWEp3uwd2fJdcOWiFaf9fgrCXkp\n\tJnGg==","X-Google-DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n\td=1e100.net; s=20161025;\n\th=x-gm-message-state:from:message-id:mime-version:subject:date\n\t:in-reply-to:cc:to:references;\n\tbh=RnWGg8mQBqjKGyZtZ19dK3qmY7sWlPn/opsfUOGn4jE=;\n\tb=hOaN2LTGxkx6La4mAwcV1MQPkbM0n5eGmUv8AVHN+DoNebkty2rZ0v6Lngoc9RiKd6\n\tUzJSTZuvIZX6S6ioVbu3OSXJ3Wfpxb3SA5rJ74N+YXYUI+sS1ro+Sl9FoGmLEXOKwo5g\n\tHfk1LU+8Grnd1gUuDS1NuvnPnf7NvFb8L9SZFnugvSQS+JiugqwbNKSMtxfAbhO3m8OD\n\tIIyn3pxEZnod/BwPPy5Hgex34+DhuQSV8uB3Ss/fmJEn0v6nxYfy55IdwhNGv4nSDkcg\n\tffxsEcWFXyFtnyJuHaf9ha8MprNezy7vM7lpjHZdXpi4e1d6W8+/7z4a7EIHERhd92Sp\n\t1DVw==","X-Gm-Message-State":"AHYfb5itXUy6Om/s9MJc5581B5YAurffJFKNlZAFGgt5+BFoMAjfLIHF\n\tiecJ9yrFUof8HZhC","X-Received":"by 10.107.16.75 with SMTP id y72mr9012790ioi.117.1503081929643; \n\tFri, 18 Aug 2017 11:45:29 -0700 (PDT)","From":"Andreas Dilger ","Message-Id":"<3016732A-E5AA-4EE7-980A-05323CD346A6@dilger.ca>","Content-Type":"multipart/signed;\n\tboundary=\"Apple-Mail=_5E84B4BC-E542-4482-98C7-95AECE9244F2\";\n\tprotocol=\"application/pgp-signature\"; micalg=pgp-sha1","Mime-Version":"1.0 (Mac OS X Mail 10.3 \\(3273\\))","Subject":"Re: [PATCH] e2fsck: set dir_nlink feature if large dir exists","Date":"Fri, 18 Aug 2017 12:45:21 -0600","In-Reply-To":"<1503080382-37376-1-git-send-email-adilger@dilger.ca>","Cc":"Ext4 Developers List ","To":"Theodore Ts'o ","References":"<1503080382-37376-1-git-send-email-adilger@dilger.ca>","X-Mailer":"Apple Mail (2.3273)","Sender":"linux-ext4-owner@vger.kernel.org","Precedence":"bulk","List-ID":"","X-Mailing-List":"linux-ext4@vger.kernel.org"}},{"id":1759818,"web_url":"http://patchwork.ozlabs.org/comment/1759818/","msgid":"<20170830022000.b7mgzksytvcwirx5@thunk.org>","list_archive_url":null,"date":"2017-08-30T02:20:00","subject":"Re: e2fsck: set dir_nlink feature if large dir exists","submitter":{"id":350,"url":"http://patchwork.ozlabs.org/api/people/350/","name":"Theodore Tso","email":"tytso@mit.edu"},"content":"On Fri, Aug 18, 2017 at 12:19:42PM -0600, Andreas Dilger wrote:\n> If there is a directory with more than EXT2_LINK_MAX (65000)\n> subdirectories, but the DIR_NLINK feature is not set in the\n> superblock, the feature should be set before continuing on\n> to change the on-disk directory link count to 1.\n> \n> While most filesystems should have DIR_NLINK set (it was set\n> by default for all ext4 filesystems, and the kernel before\n> 4.12 automatically set it if the directory link count grew\n> too large), it is possible that this flag is lost due to disk\n> corruption or for an upgraded filesystem. We no longer want\n> the kernel to automatically enable this feature.\n> \n> Addresses: https://bugzilla.kernel.org/show_bug.cgi?id=196405\n> Signed-off-by: Andreas Dilger \n\nThe f_large_dir test is now failing after I apply this patch:\n\ndebugfs 1.43.6 (29-Aug-2017)\n./test_one: 38: /usr/projects/e2fsprogs/e2fsprogs/tests/f_large_dir/script: arithmetic expression: division by zero: \"i / ELAPSED\"\nf_large_dir: optimize 3 level htree directories: failed\n\n\t\t\t\t\t\t- Ted","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=)","ozlabs.org; dkim=pass (1024-bit key;\n\tunprotected) header.d=thunk.org header.i=@thunk.org\n\theader.b=\"Oirhdu0F\"; dkim-atps=neutral"],"Received":["from vger.kernel.org (vger.kernel.org [209.132.180.67])\n\tby ozlabs.org (Postfix) with ESMTP id 3xhq384WkBz9sP5\n\tfor ;\n\tWed, 30 Aug 2017 12:20:04 +1000 (AEST)","(majordomo@vger.kernel.org) by vger.kernel.org via listexpand\n\tid S1751801AbdH3CUD (ORCPT );\n\tTue, 29 Aug 2017 22:20:03 -0400","from imap.thunk.org ([74.207.234.97]:39378 \"EHLO imap.thunk.org\"\n\trhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP\n\tid S1751669AbdH3CUD (ORCPT );\n\tTue, 29 Aug 2017 22:20:03 -0400","from root (helo=callcc.thunk.org)\n\tby imap.thunk.org with local-esmtp (Exim 4.84_2)\n\t(envelope-from )\n\tid 1dmsbp-0001Xn-Oz; Wed, 30 Aug 2017 02:20:01 +0000","by callcc.thunk.org (Postfix, from userid 15806)\n\tid 9B839C00846; Tue, 29 Aug 2017 22:20:00 -0400 (EDT)"],"DKIM-Signature":"v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=thunk.org;\n\ts=ef5046eb; \n\th=In-Reply-To:Content-Type:MIME-Version:References:Message-ID:Subject:Cc:To:From:Date;\n\tbh=QI1TpZ6vDjQFvQnLdubJHOAXtznP3/gXioxvETIwVvg=; \n\tb=Oirhdu0Fy2Fods4eGqTxISk0gY0AJ1z6KqCkXRsXTGCqe2iH6i8B/jb6f6PpaclkuY3FHqRdt6UmIIDfzpvzAqkGGn/CEUTedVTGPdBSFf4kWuvLZw8b4Cxsnx85tOsjQWsgp/p2+PYOa3RqOcVX5aduOWR6VI6D5t+PjSrl0Cc=;","Date":"Tue, 29 Aug 2017 22:20:00 -0400","From":"Theodore Ts'o ","To":"Andreas Dilger ","Cc":"linux-ext4@vger.kernel.org","Subject":"Re: e2fsck: set dir_nlink feature if large dir exists","Message-ID":"<20170830022000.b7mgzksytvcwirx5@thunk.org>","References":"<1503080382-37376-1-git-send-email-adilger@dilger.ca>","MIME-Version":"1.0","Content-Type":"text/plain; charset=us-ascii","Content-Disposition":"inline","In-Reply-To":"<1503080382-37376-1-git-send-email-adilger@dilger.ca>","User-Agent":"NeoMutt/20170609 (1.8.3)","X-SA-Exim-Connect-IP":"","X-SA-Exim-Mail-From":"tytso@thunk.org","X-SA-Exim-Scanned":"No (on imap.thunk.org); SAEximRunCond expanded to false","Sender":"linux-ext4-owner@vger.kernel.org","Precedence":"bulk","List-ID":"","X-Mailing-List":"linux-ext4@vger.kernel.org"}},{"id":1759935,"web_url":"http://patchwork.ozlabs.org/comment/1759935/","msgid":"<604C57FC-C3A6-478F-BDA6-E8550555C70F@dilger.ca>","list_archive_url":null,"date":"2017-08-30T07:43:30","subject":"Re: e2fsck: set dir_nlink feature if large dir exists","submitter":{"id":4514,"url":"http://patchwork.ozlabs.org/api/people/4514/","name":"Andreas Dilger","email":"adilger@dilger.ca"},"content":"> On Aug 29, 2017, at 8:20 PM, Theodore Ts'o wrote:\n> \n> On Fri, Aug 18, 2017 at 12:19:42PM -0600, Andreas Dilger wrote:\n>> If there is a directory with more than EXT2_LINK_MAX (65000)\n>> subdirectories, but the DIR_NLINK feature is not set in the\n>> superblock, the feature should be set before continuing on\n>> to change the on-disk directory link count to 1.\n>> \n>> While most filesystems should have DIR_NLINK set (it was set\n>> by default for all ext4 filesystems, and the kernel before\n>> 4.12 automatically set it if the directory link count grew\n>> too large), it is possible that this flag is lost due to disk\n>> corruption or for an upgraded filesystem. We no longer want\n>> the kernel to automatically enable this feature.\n>> \n>> Addresses: https://bugzilla.kernel.org/show_bug.cgi?id=196405\n>> Signed-off-by: Andreas Dilger \n> \n> The f_large_dir test is now failing after I apply this patch:\n> \n> debugfs 1.43.6 (29-Aug-2017)\n> ./test_one: 38: /usr/projects/e2fsprogs/e2fsprogs/tests/f_large_dir/script: arithmetic expression: division by zero: \"i / ELAPSED\"\n> f_large_dir: optimize 3 level htree directories: failed\n\nYou must have a faster test system than I do...\n\nI can send an updated patch with a fix for this, as well as the\nimprovement for expand_dir as previously discussed.\n\nOn a related note, I was trying to implement the optimization for\nmore efficient ext2fs_link() insertion, but this has proven to be\nmuch more complex than I expected. I was thinking I would just\ncall the link_proc() function directly to handle insertion of the\nnew name, using block number of the previous caller. However, this\nfunction depends on the directory leaf buffers having been read\nfrom disk, and being passed a dirent pointer to the free space after\nbeing called through a series of callback indirections.\n\nI thought it would be a bit cleaner to call ext2fs_process_dir_block()\n(despite the warning that this function is for internal use only)\nwith the previously saved block numbers, but that also depends on\nthe dir_context state being initialzed, which didn't seem very clean.\n\nAm I doing down the wrong road here?\n\nCheers, Andreas","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=)","ozlabs.org; dkim=pass (2048-bit key;\n\tunprotected) header.d=dilger-ca.20150623.gappssmtp.com\n\theader.i=@dilger-ca.20150623.gappssmtp.com\n\theader.b=\"TfLrNhw5\"; dkim-atps=neutral"],"Received":["from vger.kernel.org (vger.kernel.org [209.132.180.67])\n\tby ozlabs.org (Postfix) with ESMTP id 3xhyDW2PRHz9s7F\n\tfor ;\n\tWed, 30 Aug 2017 17:43:39 +1000 (AEST)","(majordomo@vger.kernel.org) by vger.kernel.org via listexpand\n\tid S1751332AbdH3Hni (ORCPT );\n\tWed, 30 Aug 2017 03:43:38 -0400","from mail-io0-f194.google.com ([209.85.223.194]:33105 \"EHLO\n\tmail-io0-f194.google.com\" rhost-flags-OK-OK-OK-OK) by vger.kernel.org\n\twith ESMTP id S1751298AbdH3Hni (ORCPT\n\t); Wed, 30 Aug 2017 03:43:38 -0400","by mail-io0-f194.google.com with SMTP id s101so531385ioe.0\n\tfor ;\n\tWed, 30 Aug 2017 00:43:37 -0700 (PDT)","from cabot-wlan.adilger.int (S0106a84e3fe4b223.cg.shawcable.net.\n\t[70.77.216.213]) by smtp.gmail.com with ESMTPSA id\n\ti81sm1868600itb.22.2017.08.30.00.43.34\n\t(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);\n\tWed, 30 Aug 2017 00:43:35 -0700 (PDT)"],"DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n\td=dilger-ca.20150623.gappssmtp.com; s=20150623;\n\th=from:message-id:mime-version:subject:date:in-reply-to:cc:to\n\t:references; bh=sgldadJT35GPfcCmBNCb5Suwwa3n44Tk7AtEuRtaYe8=;\n\tb=TfLrNhw5Tluah+heCV+DCbM/b1rVOXmwZDf2/H9JCi08QvfdcUYlXAqfvi1bs2qNNE\n\tPrzjnifQI5N4+tylrDotbo7i06mlMu7E6S0lH4JdFnWaoPUhC59wvwI2p4VMElntoPjC\n\t1udWOM1EfTYHQ7vfPKH54f5nfFEyLRtW8Q0qOmF4YTOXxZPuyLlIllynYQe7UwEUj17g\n\tdrvprTRb8jul243Au/jvO+zOcHNV5ypA9sF8mc5/1wkiUMzi2r9svAKwDG6brU+wDcav\n\tpUrPtR1hZp9LlbEKgRpjR92R4xqt/rsy37X3p1r7mTBfbn5TRSLDnQ7ACaklIVJG0wW4\n\t6elw==","X-Google-DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n\td=1e100.net; s=20161025;\n\th=x-gm-message-state:from:message-id:mime-version:subject:date\n\t:in-reply-to:cc:to:references;\n\tbh=sgldadJT35GPfcCmBNCb5Suwwa3n44Tk7AtEuRtaYe8=;\n\tb=qHqYo1WlNrOAYF1qd1E4rKHtPipEy054vjao5RgBE7xtWeVpWM+rGOLWCPjWtICE47\n\t9Mz7feMLiDgVcG7/FK5j41XZj5lc4vkwfv9VRR+jv+llvSqdNCLgNxs5K0wU4I1wFGyx\n\tuKnV3oOLecVzpKekZ/6d49GkKNSTITtnLY2TKgj4q+Gw3icpU8NCgBdIYbrWwOSxo1lT\n\tSpvWJ5WFIH6kOCnrONsCeuklZraLbh+grbJ5UcuXxkczUBw0DFAd8+kSajIq79VX0m7I\n\tdDBlnAEBvvd0hqYlpEt6pA3v0z3eCGDBZ0v5yC0rz5E32H1nA+rr7uBH4X7GPMOh5f/y\n\tAy2A==","X-Gm-Message-State":"AHPjjUhzMsUlkwdV70iHqm/qcKMTeoFm4jLnjeR4dL72lrK/K+JZOB5Z\n\tXa02p4ouyOiGf/Aq","X-Received":"by 10.107.28.78 with SMTP id c75mr467333ioc.307.1504079017275;\n\tWed, 30 Aug 2017 00:43:37 -0700 (PDT)","From":"Andreas Dilger ","Message-Id":"<604C57FC-C3A6-478F-BDA6-E8550555C70F@dilger.ca>","Content-Type":"multipart/signed;\n\tboundary=\"Apple-Mail=_924DAB50-016B-46DF-801E-4349059A839C\";\n\tprotocol=\"application/pgp-signature\"; micalg=pgp-sha1","Mime-Version":"1.0 (Mac OS X Mail 10.3 \\(3273\\))","Subject":"Re: e2fsck: set dir_nlink feature if large dir exists","Date":"Wed, 30 Aug 2017 01:43:30 -0600","In-Reply-To":"<20170830022000.b7mgzksytvcwirx5@thunk.org>","Cc":"linux-ext4@vger.kernel.org","To":"Theodore Ts'o ","References":"<1503080382-37376-1-git-send-email-adilger@dilger.ca>\n\t<20170830022000.b7mgzksytvcwirx5@thunk.org>","X-Mailer":"Apple Mail (2.3273)","Sender":"linux-ext4-owner@vger.kernel.org","Precedence":"bulk","List-ID":"","X-Mailing-List":"linux-ext4@vger.kernel.org"}},{"id":1760269,"web_url":"http://patchwork.ozlabs.org/comment/1760269/","msgid":"<20170830151332.2ikr5dfox3aeebyd@thunk.org>","list_archive_url":null,"date":"2017-08-30T15:13:32","subject":"Re: e2fsck: set dir_nlink feature if large dir exists","submitter":{"id":350,"url":"http://patchwork.ozlabs.org/api/people/350/","name":"Theodore Tso","email":"tytso@mit.edu"},"content":"On Wed, Aug 30, 2017 at 01:43:30AM -0600, Andreas Dilger wrote:\n> > The f_large_dir test is now failing after I apply this patch:\n> > \n> > debugfs 1.43.6 (29-Aug-2017)\n> > ./test_one: 38: /usr/projects/e2fsprogs/e2fsprogs/tests/f_large_dir/script: arithmetic expression: division by zero: \"i / ELAPSED\"\n> > f_large_dir: optimize 3 level htree directories: failed\n> \n> You must have a faster test system than I do...\n\nI'm using a ramdisk for /tmp. I suspect that's what is making all the\ndifference. Otherwise it's just a normal Lenovo T470 laptop....\n\n> On a related note, I was trying to implement the optimization for\n> more efficient ext2fs_link() insertion, but this has proven to be\n> much more complex than I expected. I was thinking I would just\n> call the link_proc() function directly to handle insertion of the\n> new name, using block number of the previous caller. However, this\n> function depends on the directory leaf buffers having been read\n> from disk, and being passed a dirent pointer to the free space after\n> being called through a series of callback indirections.\n\nI think it's more trouble than it's worth to preseve the existing\nlink_proc() function. I'd recommend out to be just what is necessary\nto do the directory entry insert, and make that a helper function\nwhich is called by link_proc() and the shortcut handling code in\next2fs_link().\n\nCheers,\n\n\t\t\t\t\t\t- Ted","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=)","ozlabs.org; dkim=pass (1024-bit key;\n\tunprotected) header.d=thunk.org header.i=@thunk.org\n\theader.b=\"mz3YJc34\"; dkim-atps=neutral"],"Received":["from vger.kernel.org (vger.kernel.org [209.132.180.67])\n\tby ozlabs.org (Postfix) with ESMTP id 3xj8Cg428xz9sN7\n\tfor ;\n\tThu, 31 Aug 2017 01:13:35 +1000 (AEST)","(majordomo@vger.kernel.org) by vger.kernel.org via listexpand\n\tid S1751409AbdH3PNe (ORCPT );\n\tWed, 30 Aug 2017 11:13:34 -0400","from imap.thunk.org ([74.207.234.97]:41822 \"EHLO imap.thunk.org\"\n\trhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP\n\tid S1751332AbdH3PNe (ORCPT );\n\tWed, 30 Aug 2017 11:13:34 -0400","from root (helo=callcc.thunk.org)\n\tby imap.thunk.org with local-esmtp (Exim 4.84_2)\n\t(envelope-from )\n\tid 1dn4gP-0003lw-Da; Wed, 30 Aug 2017 15:13:33 +0000","by callcc.thunk.org (Postfix, from userid 15806)\n\tid 7ABD2C0061A; Wed, 30 Aug 2017 11:13:32 -0400 (EDT)"],"DKIM-Signature":"v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=thunk.org;\n\ts=ef5046eb; \n\th=In-Reply-To:Content-Type:MIME-Version:References:Message-ID:Subject:Cc:To:From:Date;\n\tbh=CK10lhqCjmyALgtZrHwU+UlbpKiTrjMWMX7CNqT2uxA=; \n\tb=mz3YJc34HPzYbw3cAGTq05d9HYYdIcWu5JBkqK5L/5BC4VQmsLSvGRPAUpWkwAbHEYjs2w/Lq4Nk7n7TsANTk3g3mx8vyX6BYNNNkMuSbVmCqoLVt7j8Cn0FsCTKwAl6D7bYzklfBvtpRP+fzfnUkEEFZd3yz+9GouD7qGwKMmY=;","Date":"Wed, 30 Aug 2017 11:13:32 -0400","From":"Theodore Ts'o ","To":"Andreas Dilger ","Cc":"linux-ext4@vger.kernel.org","Subject":"Re: e2fsck: set dir_nlink feature if large dir exists","Message-ID":"<20170830151332.2ikr5dfox3aeebyd@thunk.org>","References":"<1503080382-37376-1-git-send-email-adilger@dilger.ca>\n\t<20170830022000.b7mgzksytvcwirx5@thunk.org>\n\t<604C57FC-C3A6-478F-BDA6-E8550555C70F@dilger.ca>","MIME-Version":"1.0","Content-Type":"text/plain; charset=us-ascii","Content-Disposition":"inline","In-Reply-To":"<604C57FC-C3A6-478F-BDA6-E8550555C70F@dilger.ca>","User-Agent":"NeoMutt/20170609 (1.8.3)","X-SA-Exim-Connect-IP":"","X-SA-Exim-Mail-From":"tytso@thunk.org","X-SA-Exim-Scanned":"No (on imap.thunk.org); SAEximRunCond expanded to false","Sender":"linux-ext4-owner@vger.kernel.org","Precedence":"bulk","List-ID":"","X-Mailing-List":"linux-ext4@vger.kernel.org"}},{"id":1761245,"web_url":"http://patchwork.ozlabs.org/comment/1761245/","msgid":"<6FF8BA29-74A3-483D-A194-C5AD3A4E3BF2@dilger.ca>","list_archive_url":null,"date":"2017-08-31T18:17:59","subject":"Re: e2fsck: set dir_nlink feature if large dir exists","submitter":{"id":4514,"url":"http://patchwork.ozlabs.org/api/people/4514/","name":"Andreas Dilger","email":"adilger@dilger.ca"},"content":"On Aug 30, 2017, at 9:13 AM, Theodore Ts'o wrote:\n> \n> On Wed, Aug 30, 2017 at 01:43:30AM -0600, Andreas Dilger wrote:\n>> On a related note, I was trying to implement the optimization for\n>> more efficient ext2fs_link() insertion, but this has proven to be\n>> much more complex than I expected. I was thinking I would just\n>> call the link_proc() function directly to handle insertion of the\n>> new name, using block number of the previous caller. However, this\n>> function depends on the directory leaf buffers having been read\n>> from disk, and being passed a dirent pointer to the free space after\n>> being called through a series of callback indirections.\n> \n> I think it's more trouble than it's worth to preseve the existing\n> link_proc() function. I'd recommend out to be just what is necessary\n> to do the directory entry insert, and make that a helper function\n> which is called by link_proc() and the shortcut handling code in\n> ext2fs_link().\n\nI looked at implementing it this way, but unfortunately that doesn't\nappear workable since ext2fs_link() never gets the block numbers to\nbe able to do this. I'd essentially have to reimplement all of the\nblock and directory leaf processing in ext2fs_dir_iterate2() to get\nfigure out where to store the first entries in the directory.\n\nWhat I'm looking at now is add a new ext2fs_dir_iterate3() function\nthat passes *blocknr and blockcnt to the link_proc() and unlink_proc()\ncallback functions so they can be stored in struct_ext2_filsys, and\nused to shortcut the iteration in ext2fs_link() for multiple inserts.\nIt is added to unlink_proc() so that we can reset the saved state if\nentries are being deleted.\n\nCheers, Andreas","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=)","ozlabs.org; dkim=pass (2048-bit key;\n\tunprotected) header.d=dilger-ca.20150623.gappssmtp.com\n\theader.i=@dilger-ca.20150623.gappssmtp.com\n\theader.b=\"BjBahamk\"; dkim-atps=neutral"],"Received":["from vger.kernel.org (vger.kernel.org [209.132.180.67])\n\tby ozlabs.org (Postfix) with ESMTP id 3xjrGF3rb1z9s7c\n\tfor ;\n\tFri, 1 Sep 2017 04:18:13 +1000 (AEST)","(majordomo@vger.kernel.org) by vger.kernel.org via listexpand\n\tid S1751264AbdHaSSM (ORCPT );\n\tThu, 31 Aug 2017 14:18:12 -0400","from mail-io0-f181.google.com ([209.85.223.181]:36740 \"EHLO\n\tmail-io0-f181.google.com\" rhost-flags-OK-OK-OK-OK) by vger.kernel.org\n\twith ESMTP id S1750911AbdHaSSL (ORCPT\n\t); Thu, 31 Aug 2017 14:18:11 -0400","by mail-io0-f181.google.com with SMTP id f99so3371210ioi.3\n\tfor ;\n\tThu, 31 Aug 2017 11:18:11 -0700 (PDT)","from cabot-wlan.adilger.int (S0106a84e3fe4b223.cg.shawcable.net.\n\t[70.77.216.213]) by smtp.gmail.com with ESMTPSA id\n\ta139sm366634ita.3.2017.08.31.11.18.08\n\t(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);\n\tThu, 31 Aug 2017 11:18:09 -0700 (PDT)"],"DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n\td=dilger-ca.20150623.gappssmtp.com; s=20150623;\n\th=from:message-id:mime-version:subject:date:in-reply-to:cc:to\n\t:references; bh=D7lV3HLM1BFakMO+rOL1OKOISfR3COJnR5MFaJbuO8c=;\n\tb=BjBahamkjFsG+sOq7VFaD3jh4FIwNwG5w0Hjm68t4EJMn4RmOy6jT7kazCqd1bbVoH\n\tQnC2YSYHsJVf3PYjdTZxBYu3xv3x1Lm+j7i+1TFbLE9RzUIHeT4GyDaEFiFbeoz5m9EH\n\t4A2v6dTTEsxvtqCqFw1Za6flGRf4ME2SFDD/a3BaYyIkE2Jkv0AAtyOVlwtSHE4KZuuY\n\t+NX0iX/xKDb/1V5pbfAXYXN2oKy5SKRYcyZXa5EfNEZ7WucbBmWk6wdPv+OSb7QNY/F/\n\tvpLIPwgrwbTaJToatijrZSTKjQ5ERf5gWJodvVMNEMbpCO8xuLOLW6QBW8htcSDZ8Fwx\n\tDDFw==","X-Google-DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n\td=1e100.net; s=20161025;\n\th=x-gm-message-state:from:message-id:mime-version:subject:date\n\t:in-reply-to:cc:to:references;\n\tbh=D7lV3HLM1BFakMO+rOL1OKOISfR3COJnR5MFaJbuO8c=;\n\tb=Kq/wNmdGuRVJ4g7detqgSx2qOvuktABa0Zjs5daZ3SlUlakeMuy+W3vfk35fr/s3ki\n\tYBjJGB4wzLrLScLlsm09uN62MamClSHxpaEUIq+cGWF+9ABWfxbs3Nx78PVuElXdTiNC\n\tOqy5uZvmEmjdn2wSllbpmpfyvdptGxW0U6E+TgWtXU1ygB9/U7MgSo+mtEOWXrvhnPrH\n\tk4626ljPDyc/jBcQzvFO5dnAS3REXCUMRZZhtGMSUMJDWGKupWQ9SEFiqi3fI3uqt5LC\n\tpZj13PxOewQneUmnmUSElqZA0zFODfWUhEFHBXEb9iNLBVY+54rKJ5s7k0490ZexOTHk\n\t8mdQ==","X-Gm-Message-State":"AHPjjUgT/0cykVdgoylohmdOZ1gk1hLX0Po4wZw/Cqj0vrwLxV9Cuznv\n\tKEBtEObQirFr+7Ix","X-Google-Smtp-Source":"ADKCNb5m0lfcvG5aMdOZXnGhuoANh4RdTCkSMte6NllYhrxH317VJCJOJIxeZ3ZjP47GgsiaJSJwSQ==","X-Received":"by 10.107.152.197 with SMTP id\n\ta188mr5938359ioe.302.1504203490710; \n\tThu, 31 Aug 2017 11:18:10 -0700 (PDT)","From":"Andreas Dilger ","Message-Id":"<6FF8BA29-74A3-483D-A194-C5AD3A4E3BF2@dilger.ca>","Content-Type":"multipart/signed;\n\tboundary=\"Apple-Mail=_D6320DDB-5460-4383-BEAC-292B2CADB05B\";\n\tprotocol=\"application/pgp-signature\"; micalg=pgp-sha1","Mime-Version":"1.0 (Mac OS X Mail 10.3 \\(3273\\))","Subject":"Re: e2fsck: set dir_nlink feature if large dir exists","Date":"Thu, 31 Aug 2017 12:17:59 -0600","In-Reply-To":"<20170830151332.2ikr5dfox3aeebyd@thunk.org>","Cc":"Ext4 Developers List ","To":"Theodore Ts'o ","References":"<1503080382-37376-1-git-send-email-adilger@dilger.ca>\n\t<20170830022000.b7mgzksytvcwirx5@thunk.org>\n\t<604C57FC-C3A6-478F-BDA6-E8550555C70F@dilger.ca>\n\t<20170830151332.2ikr5dfox3aeebyd@thunk.org>","X-Mailer":"Apple Mail (2.3273)","Sender":"linux-ext4-owner@vger.kernel.org","Precedence":"bulk","List-ID":"","X-Mailing-List":"linux-ext4@vger.kernel.org"}}]