From 9f005a90f86fccdfb9b016e39a9e9eca3e8911b2 Mon Sep 17 00:00:00 2001
From: "Darrick J. Wong" <darrick.wong@oracle.com>
Date: Fri, 18 Jul 2014 15:54:30 -0700
Subject: [PATCH] e2fsck: collapse holes in extent-based directories

If we notice a hole in the block map of an extent-based directory,
offer to collapse the hole by decreasing the logical block # of the
extent.  This saves us from pass 3's inefficient strategy, which fills
the holes by mapping in a lot of empty directory blocks.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
---
 e2fsck/pass1.c            |  39 ++++++++++++++++++++++++++++++++++++++
 e2fsck/problem.c          |   5 +++++
 e2fsck/problem.h          |   3 +++
 tests/f_holedir2/expect.1 |   8 +++-----
 tests/f_holedir3/expect.1 |  13 +++++++++++++
 tests/f_holedir3/expect.2 |   7 +++++++
 tests/f_holedir3/image.gz | Bin 0 -> 3700 bytes
 tests/f_holedir3/name     |   2 ++
 8 files changed, 72 insertions(+), 5 deletions(-)
 create mode 100644 tests/f_holedir3/expect.1
 create mode 100644 tests/f_holedir3/expect.2
 create mode 100644 tests/f_holedir3/image.gz
 create mode 100644 tests/f_holedir3/name

diff --git a/e2fsck/pass1.c b/e2fsck/pass1.c
index cf36a086a..87e6d341d 100644
--- a/e2fsck/pass1.c
+++ b/e2fsck/pass1.c
@@ -1927,6 +1927,45 @@ report_problem:
 			}
 			pb->fragmented = 1;
 		}
+		/*
+		 * If we notice a gap in the logical block mappings of an
+		 * extent-mapped directory, offer to close the hole by
+		 * moving the logical block down, otherwise we'll go mad in
+		 * pass 3 allocating empty directory blocks to fill the hole.
+		 */
+		if (is_dir &&
+		    pb->last_block + 1 < (e2_blkcnt_t)extent.e_lblk) {
+			blk64_t new_lblk;
+
+			new_lblk = pb->last_block + 1;
+			if (EXT2FS_CLUSTER_RATIO(ctx->fs) > 1)
+				new_lblk = ((new_lblk +
+					     EXT2FS_CLUSTER_RATIO(ctx->fs)) &
+					    EXT2FS_CLUSTER_MASK(ctx->fs)) |
+					   (extent.e_lblk &
+					    EXT2FS_CLUSTER_MASK(ctx->fs));
+			pctx->blk = extent.e_lblk;
+			pctx->blk2 = new_lblk;
+			if (fix_problem(ctx, PR_1_COLLAPSE_DBLOCK, pctx)) {
+				extent.e_lblk = new_lblk;
+				pb->inode_modified = 1;
+				pctx->errcode = ext2fs_extent_replace(ehandle,
+								0, &extent);
+				if (pctx->errcode) {
+					pctx->errcode = 0;
+					goto alloc_later;
+				}
+				pctx->errcode = ext2fs_extent_fix_parents(ehandle);
+				if (pctx->errcode)
+					goto failed_add_dir_block;
+				pctx->errcode = ext2fs_extent_goto(ehandle,
+								extent.e_lblk);
+				if (pctx->errcode)
+					goto failed_add_dir_block;
+				last_lblk = extent.e_lblk + extent.e_len - 1;
+			}
+		}
+alloc_later:
 		while (is_dir && (++pb->last_db_block <
 				  (e2_blkcnt_t) extent.e_lblk)) {
 			pctx->errcode = ext2fs_add_dir_block2(ctx->fs->dblist,
diff --git a/e2fsck/problem.c b/e2fsck/problem.c
index 4c105bb29..837d11109 100644
--- a/e2fsck/problem.c
+++ b/e2fsck/problem.c
@@ -967,6 +967,11 @@ static struct e2fsck_problem problem_table[] = {
 	  PROMPT_CLEAR, 0 },
 
 
+	/* Directory inode block <block> should be at block <otherblock> */
+	{ PR_1_COLLAPSE_DBLOCK,
+	  N_("@d @i %i @b %b should be at @b %c.  "),
+	  PROMPT_FIX, 0 },
+
 	/* Pass 1b errors */
 
 	/* Pass 1B: Rescan for duplicate/bad blocks */
diff --git a/e2fsck/problem.h b/e2fsck/problem.h
index 6cb09cfbc..d3e66ad60 100644
--- a/e2fsck/problem.h
+++ b/e2fsck/problem.h
@@ -624,6 +624,9 @@ struct problem_context {
 /* Couldn't clone file (error) */
 #define PR_1D_CLONE_ERROR	0x013008
 
+/* Directory inode has a missing block (hole) */
+#define PR_1_COLLAPSE_DBLOCK		0x010072
+
 /*
  * Pass 2 errors
  */
diff --git a/tests/f_holedir2/expect.1 b/tests/f_holedir2/expect.1
index 5124f6178..455f4b065 100644
--- a/tests/f_holedir2/expect.1
+++ b/tests/f_holedir2/expect.1
@@ -1,21 +1,19 @@
 Pass 1: Checking inodes, blocks, and sizes
 Inode 12, i_size is 0, should be 5120.  Fix? yes
 
-Inode 13, i_size is 4096, should be 5120.  Fix? yes
+Directory inode 13 block 2 should be at block 1.  Fix? yes
 
 Pass 2: Checking directory structure
 Directory inode 12 has an unallocated block #3.  Allocate? yes
 
-Directory inode 13 has an unallocated block #1.  Allocate? yes
-
 Pass 3: Checking directory connectivity
 Pass 3A: Optimizing directories
 Pass 4: Checking reference counts
 Pass 5: Checking group summary information
-Free blocks count wrong for group #0 (79, counted=77).
+Free blocks count wrong for group #0 (78, counted=77).
 Fix? yes
 
-Free blocks count wrong (79, counted=77).
+Free blocks count wrong (78, counted=77).
 Fix? yes
 
 
diff --git a/tests/f_holedir3/expect.1 b/tests/f_holedir3/expect.1
new file mode 100644
index 000000000..074ca6c8c
--- /dev/null
+++ b/tests/f_holedir3/expect.1
@@ -0,0 +1,13 @@
+Pass 1: Checking inodes, blocks, and sizes
+Directory inode 12 block 5 should be at block 2.  Fix? yes
+
+Inode 12, i_size is 6144, should be 3072.  Fix? yes
+
+Pass 2: Checking directory structure
+Pass 3: Checking directory connectivity
+Pass 4: Checking reference counts
+Pass 5: Checking group summary information
+
+test_filesys: ***** FILE SYSTEM WAS MODIFIED *****
+test_filesys: 17/128 files (5.9% non-contiguous), 1093/2048 blocks
+Exit status is 1
diff --git a/tests/f_holedir3/expect.2 b/tests/f_holedir3/expect.2
new file mode 100644
index 000000000..b675e6df9
--- /dev/null
+++ b/tests/f_holedir3/expect.2
@@ -0,0 +1,7 @@
+Pass 1: Checking inodes, blocks, and sizes
+Pass 2: Checking directory structure
+Pass 3: Checking directory connectivity
+Pass 4: Checking reference counts
+Pass 5: Checking group summary information
+test_filesys: 17/128 files (5.9% non-contiguous), 1093/2048 blocks
+Exit status is 0
diff --git a/tests/f_holedir3/image.gz b/tests/f_holedir3/image.gz
new file mode 100644
index 0000000000000000000000000000000000000000..c5eeb37d2029fdf7d98d86548ebea0024f082b4e
GIT binary patch
literal 3700
zc-rmO|1;Zp9>DQ*dzQA-X1iC1E1S--(_M$|u~?#F%3`WSTa7RErM|RSr?F_$Ap7ZV
zOGksOwPd?WIIGV0MreFb-LB*+k|0PmByFR@5+RXqB%k-WySdr9nY%yWZajW?&wE}!
zzMt=T&l^RyKzuw)yZF|A#eyKiR%D0R@MN5A8_RYY@O8LyL3E@!J+ZytF!{A#24})=
zW#qiYV)$3F=ubv^HYmRp>+7^pp6|%(inJ%PE!>}B!h-|O<)vLe+;h;~8r@wid+B|I
zo>o86qExKa^*A^*&b2Mh34#iAy!A4TzC$A!^mIf2`mKrfK%qb0LNNN87h_>hACHNA
z9uW|ujI5CP(?<XLm#wXd(l)vT)(^(^7zwS_*!RezXrjf*B!f&a3_sthMXhfy)Lh2g
zQehi(kk?#WjruH}tLlqGLHTP_$YH|LCK(ym2Z<B9)^_SKrz9c7t%bJ2+A59u+BQ+`
zi7%$RuuJt`hk2L5Q)ht(oA$@ro(pyYonD-5Xs6J<*xJAy)PZ*AD-MIVMo#_;@$V9b
zS1gkhsvj`khvS^$#E&p3#M8$_eJe;}e5aLYWA2@8)qeY+vM*Nq%4v4<)sjPrT{y1J
z7mDH>uzZ|{+o82sDp1Ssc6@670#j$&|DP6SVGhMtHFgd;ana?G7$^10m|@p+$@?gT
zrHgmP{ial&c8K)lB~L2JkKsf`rA5bM81oFq8%-yBS)KmlnCs~pUfz*ha@T^AW{Yxc
zsNQC+qVInw;Qm2LzxHiTebUC1*xFXJFn)b5^c#0`_k?M-H3zAXe3P_+F>(48>eL5J
zka0(W$!*r~ib>z=vD0NmF<jhwnqCx=7kvBvItW$MMhr_3v3I}=98ix#Q#~&|y3=7{
zi%?C=hCMw}Vd^PwAnyA~wj>&M(+C>J!G#~TFV6Lupx^sv5@BN;sOXqQ#R6o1<tjL1
zB>?x;P>etxJw2gc>}1wH)HAS1$4OYYUh=V7!m^Q-TT9E)*L~G*GSUdRrv^+@7}yEo
zgMHo}aE`Ha5`aWATY%otQ9E+C^$A=f^z7ct*G53Oj5RJrx0^e<0qoG+k{K>@AxMAa
zJKYXcsx;08A(+K0oqs>86$1#m?gc<_FEJ2#U?vr?Ou&y|V<Hw<udO@~gVaQ!m2m;<
zLI>4Dc0b>O6Hkm&q0g5aeBko~jQ}ey3gx+y3Vjui6Rc!`&UXbBPqXD%LXPp2?@s~X
zH>*Q0N?ZZk>?8BM<5#7;g0LMd2dt-+nGu|`oU-UL2tQ<Er`%V<+8HVuHnAf8^=Cg&
zvF1x299<uudO`|<x)e?JK{^<9!<bxdgaDVp3NBY+HBE2A<RGz)S#nbjk;;ut@etup
zB@vJ#x&~B6;cXOrQ1Ph>Wt$JOZJObTo8EwuG<3Ba4UUr+S-OdpV%H0%=CxcnQoaQ#
zxIp;67W!~^(tY)9#D8_AvAJ-fmzmyAP45@2w1m%V+!w4KpJM+UKCiqHS~76vbC&GO
z-Mw`$>Bf!;+SfnRXSbR7(OnZ=>fCVaB$D7cCSfN_c~0Gu*S@9Zp566uDWg^}EwvF5
zj@^;=iCI4IF@s#aNPAL@&ac98dIWUSak2)5>CO*nQYrBPRifiIO>cZUMPxcW^TKe6
z(;C!puM0q1<&ocqvQnGDwX_1&9lTN3IY7z_FV@nE+|qT@-S)ida-Zj2#;4=i0)CYU
z^;vYhw2Lou<_?^plaEHdEfmhR$^Dp7()ndPW%F95!*tA}efF<L59I~_c|*(MQb45v
zvR-v=STH0cIDlr6wB`f*8QNHw9D0BDa^Qd(q?8-YITBWEU<;<Qh7TJ4nSlK}gYtB4
z-ao=<&gG^6iVP}EnbImha~m@X`?3=2nCJO?OpTkU<6k$SGRuf>!P$b0t^7?E98ut|
zfpqT;%M0>Y2RUHMtHjFRl9E}Q_OLpdHy`G~_aZsACSCuL>kG5In?QzCFaITFQP>(t
zu$gtiZZ~KVLf&k|&B3S=wX*e6&O?-=4<CEPT22U<k&|b}GkZ4|xF=PPOHVj;gQe_k
zm$i`gmn#f`ZT=@!=@`jK)T}iB)l>$Zn&|~}WsNYue)Cy|)HePGyXg>O&z?R1cXAnU
z;O+;fidfPdQ!82>&5y=gG`(((jvdx*oR$lBIC$t)$9J63tS@FZ$Gnct;yjoYi6@q{
z5xCL$B5J#-vw2M#GRfb4ZWuN94l>n?w{J?0UXsQ~xG`Tnc3IK}#E;Hvt-obXMo9}v
u&6YkS?So__$F)?3WOu=mL)3WkP#e}_ufv`_|4VL%=}{!xWM2g01mbU_4e{#$

literal 0
Hc-jL100001

diff --git a/tests/f_holedir3/name b/tests/f_holedir3/name
new file mode 100644
index 000000000..a526787c5
--- /dev/null
+++ b/tests/f_holedir3/name
@@ -0,0 +1,2 @@
+real directories with holes and zero i_size
+
-- 
2.47.2