linux-ext4 - Re: [PATCH 05/35] e2fsck: track directories to be rehashed with a bitmap

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 for Android: free password hash cracker in your pocket

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

Message-ID: <20150421022645.GC3238@thunk.org>
Date:	Mon, 20 Apr 2015 22:26:45 -0400
From:	Theodore Ts'o <tytso@....edu>
To:	"Darrick J. Wong" <darrick.wong@...cle.com>
Cc:	linux-ext4@...r.kernel.org
Subject: Re: [PATCH 05/35] e2fsck: track directories to be rehashed with a
 bitmap

On Wed, Apr 01, 2015 at 07:34:33PM -0700, Darrick J. Wong wrote:
> Use a bitmap to track which directories we want to rehash, since
> bitmaps will use less memory.  This enables us to clean up the
> rehash-all case to use inode_dir_map, and we can free the dirinfo
> memory sooner.
> 
> Signed-off-by: Darrick J. Wong <darrick.wong@...cle.com>

Um, how is it that bitmaps will use less memory?  Directories
generally don't use contiguous inode numbers (i.e., it's not that
often that inodes N-1. N, and N+1 will all be directoriess), and and
the rbtree data structure is going to have more pointer overhead
compared with the u32 list.

In the case of the bitarray representation, the memory usage is
nr_inodes / 8 in bytes.  The memory usage of the u32 list is (nr_dirs
* 4) bytes.  Given that the number of inodes is generally something
that we've massively provisioned, that's not all that likely.

Looking at some files systems I have handy, it's no contest:

Filesystem	nr_inodes / 8                nr_dirs * 4
/dev/sda3	1,176,576                    382,424
/dev/heap/u1	  655,360		      63,384

Using inode_dir_map for the rehash-all case is a good idea, but I'm
not sure it follows that we should ues a bitmap for the non-rehash-all
case.

					- Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html