linux-kernel - [PATCH v2 0/5] Rosebush, a new hash table

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

Date: Tue, 25 Jun 2024 22:17:55 +0100
From: "Matthew Wilcox (Oracle)" <willy@...radead.org>
To: linux-kernel@...r.kernel.org
Cc: "Matthew Wilcox (Oracle)" <willy@...radead.org>,
	linux-fsdevel@...r.kernel.org,
	maple-tree@...ts.infradead.org
Subject: [PATCH v2 0/5] Rosebush, a new hash table

Rosebush is a resizing, scalable, cache-aware, RCU optimised hash table.

v2 has switched to fixed sized buckets.  That considerably simplifies
the code and removes the dilemma about whether to grow the bucket or
grow the table.  The layout of the bucket has changed to place all the
hashes at the start of the bucket, optimising lookups (as it improves
the chances that the hash we're looking for will be found in the first
cacheline).

Other changes:

 - Added rbh_destroy()
 - When we split a bucket, we now create two new buckets instead of
   only creating one and leaving the other one to be reallocated later
 - Added rbh_dump() to help debugging
 - Buildable in userspace as part of the radix tree testsuite
 - Dcache conversion

I suspect the dcache conversion probably doesn't work with detached
dentries.  But it should be good enough for someone to run a performance
benchmark ...

v1 can be found at
https://lore.kernel.org/all/20240222203726.1101861-1-willy@infradead.org/

This patch set can be found at
http://git.infradead.org/?p=users/willy/pagecache.git;a=shortlog;h=refs/heads/rosebush
aka
git://git.infradead.org/users/willy/pagecache.git rosebush

Matthew Wilcox (Oracle) (5):
  tools: Add kernel stubs needed for rosebush
  rosebush: Add new data structure
  rosebush: Add test suite
  tools: Add support for running rosebush tests in userspace
  dcache: Convert to use rosebush

 Documentation/core-api/index.rst         |   1 +
 Documentation/core-api/rosebush.rst      | 121 +++++
 MAINTAINERS                              |   8 +
 fs/dcache.c                              | 152 ++----
 include/linux/rosebush.h                 |  62 +++
 lib/Kconfig.debug                        |   3 +
 lib/Makefile                             |   3 +-
 lib/rosebush.c                           | 654 +++++++++++++++++++++++
 lib/test_rosebush.c                      | 140 +++++
 tools/include/linux/compiler.h           |   4 +
 tools/include/linux/compiler_types.h     |   2 +
 tools/include/linux/rosebush.h           |   1 +
 tools/include/linux/spinlock.h           |   2 +
 tools/include/linux/stddef.h             |   3 +
 tools/testing/radix-tree/.gitignore      |   1 +
 tools/testing/radix-tree/Makefile        |   6 +-
 tools/testing/radix-tree/kunit/test.h    |  20 +
 tools/testing/radix-tree/linux/kernel.h  |   2 +
 tools/testing/radix-tree/linux/vmalloc.h |  14 +
 tools/testing/radix-tree/rosebush.c      |  36 ++
 20 files changed, 1135 insertions(+), 100 deletions(-)
 create mode 100644 Documentation/core-api/rosebush.rst
 create mode 100644 include/linux/rosebush.h
 create mode 100644 lib/rosebush.c
 create mode 100644 lib/test_rosebush.c
 create mode 100644 tools/include/linux/rosebush.h
 create mode 100644 tools/include/linux/stddef.h
 create mode 100644 tools/testing/radix-tree/kunit/test.h
 create mode 100644 tools/testing/radix-tree/linux/vmalloc.h
 create mode 100644 tools/testing/radix-tree/rosebush.c

-- 
2.43.0