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

Date:	Thu, 14 May 2015 04:50:15 +0200
From:	"U.Mutlu" <for-gmane@...luit.com>
To:	linux-ext4@...r.kernel.org
Subject: Re: Htree concept

Theodore Ts'o wrote on 05/13/2015 11:18 PM:
> 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).

Yes, I see. I'll do similar in my prj, perhaps adding one more level,
ie. 3 reads to locate an item among about 10 million items (as said
just a toy-fs for fun :-), plus 1 more read for the item itself.

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

Yes, my initial idea to use bsearch leads to much more disk i/o.
Thx for the info.

-- 
cu
Uenal


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