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  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

Powered by blists - more mailing lists