linux-ext4 - Re: Htree concept

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] [thread-next>] [day] [month] [year] [list]

Date:	Wed, 13 May 2015 17:18:54 -0400
From:	Theodore Ts'o <tytso@....edu>
To:	"U.Mutlu" <for-gmane@...luit.com>
Cc:	linux-ext4@...r.kernel.org
Subject: Re: Htree concept

On Wed, May 13, 2015 at 07:37:36PM +0200, U.Mutlu wrote:
> I think I slowly grasp how HTree works: it keeps a (rb/avl tree)
> b*tree-db (I guess it stores it on disk) of the hashes (as keys).

The reason for using hashes is it keeps the fanout of the tree very
high, which in turn keeps the depth of the tree very short.  This
means that we can do search a very large directory using at most three
disk reads (two levels of internal node, where each node can store up
to 340 hashes plus pointers the next level of the tree, plus a
directory leaf block).

> In contrast to that here my idea: keep the hdr blocks (ie. where the
> dir/file names are) always in a sorted order. Then a bsearch should be doable.
> This would eliminate the need for any b*tree-db usage.

The problem with using a binary search is (a) it's more expensive to
search each disk read divides the search space in half (in contrast,
in the best case using htree, the first disk read can divide the
search space by factor of 340), and (b) insertions are very expensive;
suppose you have a 400 megabyte directory, and you need to insert a
filename into the very beginning of the list.  You will have to
performance 800 megabytes of I/O to make room for directory entry, if
you want to keep all of the directory entries sorted.

Cheers,

					- 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