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]
Message-ID: <CAHOvCC6Cwh=x_TJ3COgtOc9fkrdWQDn9fd3jEkZtN8QGaCpMZQ@mail.gmail.com>
Date: Wed, 7 Aug 2024 11:24:18 +0900
From: JaeJoon Jung <rgbi3307@...il.com>
To: lsahn@...akecorp.com
Cc: Linus Torvalds <torvalds@...ux-foundation.org>, Sasha Levin <levinsasha928@...il.com>, 
	"Liam R . Howlett" <Liam.Howlett@...cle.com>, Matthew Wilcox <willy@...radead.org>, 
	linux-kernel@...r.kernel.org, linux-mm@...ck.org, 
	maple-tree@...ts.infradead.org, linux-fsdevel@...r.kernel.org
Subject: Re: [PATCH v2 1/2] lib/htree: Add locking interface to new Hash Tree

Hello, Pedro Falcato
----------------------------
Thank you for your advice.
Hash Tree is a new implementation and does not have any users yet.
And it will likely take some time for many people to recognize and
demonstrate its superiority.

Hello, Darrick J. Wong
------------------------------
rhashtable was coded using the structure below,
struct rhash_head
struct rhashtable
It doesn't seem to be a Linux Kernel standard API.

And, as for the Rosebush you mentioned, I checked the related
information in the link below.
https://lore.kernel.org/lkml/20240222203726.1101861-1-willy@infradead.org/

I think "Matthew Wilcox" who developed this would be well aware of this.
Since he developed XArray which is currently running in the kernel, I
would appreciate his advice.


Hello, lsahn@...akecorp.com
------------------------------------------
The Hash Tree I implemented uses HTREE_HASH_KEY to keep the tree balanced.
You can check the macro below in include/linux/htree.h.

#define HTREE_HASH_KEY(idx, d, bits)    ( sizeof(idx) <= 4 ?    \
        (((u32)idx + d) * htgr32[d]) >> (32 - bits) :           \
        (((u64)idx + d) * htgr64[d]) >> (64 - bits) )

The hash keys are distributed using each GOLDEN RATIO value at each
depth of the tree.
The standard deviation of the hash key is less than 4.
The function that tests and computes this is _htree_hash_dev() in the
lib/htree-test.c

Thanks.
>From JaeJoon Jung

On Wed, 7 Aug 2024 at 10:42, <lsahn@...akecorp.com> wrote:
>
>
>
> > -----Original Message-----
> > From: owner-linux-mm@...ck.org <owner-linux-mm@...ck.org> On Behalf Of
> > JaeJoon Jung
> > Sent: Wednesday, August 7, 2024 9:22 AM
> > To: Greg Kroah-Hartman <gregkh@...uxfoundation.org>
> > Cc: Linus Torvalds <torvalds@...ux-foundation.org>; Sasha Levin
> > <levinsasha928@...il.com>; Liam R . Howlett <Liam.Howlett@...cle.com>;
> > Matthew Wilcox <willy@...radead.org>; linux-kernel@...r.kernel.org; linux-
> > mm@...ck.org; maple-tree@...ts.infradead.org; linux-
> > fsdevel@...r.kernel.org
> > Subject: Re: [PATCH v2 1/2] lib/htree: Add locking interface to new Hash
> > Tree
>
> ...
>
> > The Hash Tree I implemented manages the Tree with the characteristic
> > of a hash that is accessed in O(1).
> > Even if the tree gets deeper, the search time does not increase.
> > There is no rotation cost because the tree is kept balanced by hash key.
>
> How does it keep balancing?
>

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ