linux-kernel - Re: [PATCH v2 1/2] lib/htree: Add locking interface to new Hash Tree

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: <CAHOvCC7OLfXSN-dExxSFrPACj3sd09TAgrjT1eC96idKirrVJw@mail.gmail.com>
Date: Wed, 7 Aug 2024 09:21:12 +0900
From: JaeJoon Jung <rgbi3307@...il.com>
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

Dear, Greg Kroah-Hartman

The representative data structures currently implemented in the Linux
kernel are as follows.

Linked List (include/linux/list.h)
Hash List (include/linux/hash.h, hashtable.h)
Red-Black Tree (lib/rbtree.c)
XArray (lib/xarray.c)
Maple Tree (lib/maple_tree.c)

They have their own characteristics and pros and cons.

Linked List: O(n)
Hash List: O(1) + O(n)
Red-Black Tree: O(log2(n)): child is 2: Rotation required to maintain
left-right balance
XArray: O(logm(n)): child is m: If the index is not dense, there is
memory waste.
Maple Tree: O(logm(n)): child is m: The structure for trees is large
and complex.

Since Linked List and Hash List are linear structures, the search time
increases as n increases.
Red-Black Trees are suitable for indices in the thousands range, as
the tree becomes deeper as n gets too large.
XArray is suitable for managing IDs and IDRs that are densely packed
with tens of thousands of indices.
Maple Tree is suitable for large indexes, but the algorithm for
managing the tree is too complex.

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.
The algorithm for managing the tree is simple.

Performance comparison when the number of indexes(nr) is 1M stored:
The numeric unit is cycles as calculated by get_cycles().

Performance  store    find    erase
---------------------------------------------
XArray            4          6        14

Maple Tree     7          8        23

Hash Tree      5          3        12
---------------------------------------------

Please check again considering the above.

On Tue, 6 Aug 2024 at 16:38, Greg Kroah-Hartman
<gregkh@...uxfoundation.org> wrote:
>
> On Tue, Aug 06, 2024 at 04:32:22PM +0900, JaeJoon Jung wrote:
> > Since I've been working on something called a new Hash Table, it may
> > not be needed in the kernel right now.
>
> We don't review, or accept, changes that are not actually needed in the
> kernel tree as that would be a huge waste of reviewer time and energy
> for no actual benefit.
>
> sorry,
>
> greg k-h