linux-ext4 - Re: [RFC] LUS-10810 e2fsck: use bitmaps for in-use block map

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:   Mon, 2 May 2022 08:36:37 -0600
From:   Andreas Dilger <adilger@...ger.ca>
To:     Artem Blagodarenko <artem.blagodarenko@...il.com>
Cc:     linux-ext4 <linux-ext4@...r.kernel.org>,
        Artem Blagodarenko <artem.blagodarenko@....com>
Subject: Re: [RFC] LUS-10810 e2fsck: use bitmaps for in-use block map

On Apr 22, 2022, at 7:42 PM, Artem Blagodarenko <artem.blagodarenko@...il.com> wrote:
> 
> From: Artem Blagodarenko <artem.blagodarenko@....com>
> 
> EXT2FS_BMAP64_RBTREE is too expensive for fragmented prtition,
> that can lead to situation than e2fsck use swapfile.
> 
> This patch change EXT2FS_BMAP64_RBTREE to bitmap.
> 
> Marked as RFC because it must be descussed whether this flags
> should be changed by default or some additional option or
> a heuristic is needed to contol this flags.

Artem, I think switching over to a bitmap would be worse for the
case of relatively empty filesystems, and would likely increase
memory usage for many full filesystems as well.  For a very large
filesystem a full bitmap might take tens of GB of RAM per use.

I think a better (but more complex) solution would be to have a
hybrid model, where an rbtree is used for a group if it is more
efficient, but once there are too many fragments in a group and
it consumes as much memory than a bitmap (4KB) then it would be
flattened into a rbtree leaf that is a 4KB bitmap so it doesn't
keep expanding.  That would give the best of both worlds, but I
have no idea how easy/hard this would be to implement.

Cheers, Andreas

> signed-off-by: Artem Blagodarenko <artem.blagodarenko@....com>
> 
> Change-Id: I6a906b5e54cf40eaba82624d8e4c2b0f90132813
> ---
> e2fsck/pass1.c | 6 +++---
> 1 file changed, 3 insertions(+), 3 deletions(-)
> 
> diff --git a/e2fsck/pass1.c b/e2fsck/pass1.c
> index 26b9ab71..563dcdc5 100644
> --- a/e2fsck/pass1.c
> +++ b/e2fsck/pass1.c
> @@ -1247,7 +1247,7 @@ void e2fsck_pass1(e2fsck_t ctx)
> 		return;
> 	}
> 	pctx.errcode = e2fsck_allocate_subcluster_bitmap(fs,
> -			_("in-use block map"), EXT2FS_BMAP64_RBTREE,
> +			_("in-use block map"), EXT2FS_BMAP64_BITARRAY,
> 			"block_found_map", &ctx->block_found_map);
> 	if (pctx.errcode) {
> 		pctx.num = 1;
> @@ -1256,7 +1256,7 @@ void e2fsck_pass1(e2fsck_t ctx)
> 		return;
> 	}
> 	pctx.errcode = e2fsck_allocate_block_bitmap(fs,
> -			_("metadata block map"), EXT2FS_BMAP64_RBTREE,
> +			_("metadata block map"), EXT2FS_BMAP64_BITARRAY,
> 			"block_metadata_map", &ctx->block_metadata_map);
> 	if (pctx.errcode) {
> 		pctx.num = 1;
> @@ -2456,7 +2456,7 @@ static int check_ext_attr(e2fsck_t ctx, struct problem_context *pctx,
> 	if (!ctx->block_ea_map) {
> 		pctx->errcode = e2fsck_allocate_block_bitmap(fs,
> 					_("ext attr block map"),
> -					EXT2FS_BMAP64_RBTREE, "block_ea_map",
> +					EXT2FS_BMAP64_BITARRAY, "block_ea_map",
> 					&ctx->block_ea_map);
> 		if (pctx->errcode) {
> 			pctx->num = 2;
> --
> 2.27.0
> 


Cheers, Andreas






Download attachment "signature.asc" of type "application/pgp-signature" (874 bytes)