[RFC PATCH v2 00/12] landlock: Use coalesced hashtable for merged domains

[Tingmao Wang <m@maowtm.org>]

Hi,

This implements the proposed data structure from the last discussion on
hashtable domains [1], in which we store all the rules and layers of a
domain in one flat array.  But instead of doing binary search, we use a
hashtable lookup, which has performance benefits.  The goal here is both
to improve performance and also reduce Landlock's memory footprint as much
as we reasonably can.


struct landlock_domain
----------------------

This patch set creates entirely new structs to use for a merged domain,
instead of using landlock_ruleset and landlock_rule (although we still use
landlock_layer).

Since we are no longer allocating individual struct landlock_rule for each
rule, and also because this representation is more compact and does not
use any rbtree pointers, this should reduce the memory usage for a merged
domain.  In the current implementation, even if each rule only has one
layer, the struct landlock_rule would effectively take up 64 bytes due to
kalloc placing it in the next power-of-2 bucket.

While this is not completely done in this series yet, the hope is that we
can remove all code that deals with the old landlock_ruleset domain, and
simplify the landlock_ruleset and landlock_rule struct since they now only
need to represent an unmerged ruleset, which will only contain one layer.
This series already removes some existing ruleset merging code.


Hashtable implementation
------------------------

This patch set implements a "coalesced hashtable", which uses an array
instead of linked lists, and uses the array itself to store collisions, by
storing them in "unused" slots (since the existence of collisions
necessarily mean that some hashes are not used).  A more detailed
explanation of this algorithm is included in the commit message for patch
2 and 5.

The hashtable we've implemented here is a immutable-after-construction
table (technically one could probably still append to it with some care,
but in principle it should be construct-once), which fits the use case for
landlock - merge a domain once, then we just need fast read-only query.

Some research has not led me to finding any existing implementation of
such a coalesced hashtable in the kernel, therefore this series introduces
new code for this algorithm.  Currently it's placed within
security/landlock, but it is written in a generic way that if somebody
else wants to use it (for example, current users of binary search on a
fixed array?), they can probably do so relatively easily (aside from
needing to move this header outside of landlock).

Testing
-------

All selftests pass under UML.

I plan to implement Kunit tests for the hashtable (and maybe also the
domain) in the next version.


Benchmark overview
------------------

I ran benchmark with before/after using two workloads, on the same machine
and setup:

    1. run_microbench with different depth and number of extra rules using
    code in [2]

    2. A more "typical" workload I put together quickly, with 18
    reasonably logical rules, calling git status and the like repeatedly
    [3].
    (I've consistently used this same workload for benchmarking previous
    performance improvements patches, to reduce the chances of accidental
    cherry-picking)

Results for the "typical" workload

Comparing:                    before    after
  landlock_overhead:    avg = 34        34
                     median = 35        34          (-1)
  landlock_hook:        avg = 878       856   (ns)  (-2.5%)
                     median = 854       831   (ns)  (-2.7%)
  open_syscall:         avg = 2517      2485  (ns)  (-1.3%)
                     median = 2457      2425  (ns)  (-1.3%)

Results for a 100 rules test with 10 dirs to walk upwards:

with landlock: d = /1/2/3/4/5/6/7/8/9/ nb_extra_rules = 100:
  landlock_overhead:    avg = 15     15
                     median = 17     16          (-1)
  landlock_hook:        avg = 832    785   (ns)  (-5.6%)
                     median = 826    776   (ns)  (-6.1%)
  open_syscall:         avg = 5163   5001  (ns)  (-3.1%)
                     median = 4763   4847  (ns)  (+1.8%)

Note that the 100 rules benchmark has quite variable performance, and the
testing method probably meant that most of the time is spent in VFS
lookup.  (Mickaël has gave some suggestions for improvement which I've yet
to do)

The full results and .config used (basically Debian) can be found at
https://fileshare.maowtm.org/landlock/20250706/index.html


Outstanding TODOs
-----------------

- selftests for the coalesced hash table, and maybe also for the domain
- simplify struct landlock_ruleset and struct landlock_rule since they now
  only need to deal with one layer,
- Using the name "layer" to refer to individual struct landlock_layers is
  very confusing especially with names like num_layers - the next version
  should probably find a better name for it.


[1]: https://lore.kernel.org/all/20250526.quec3Dohsheu@digikod.net/
[2]: https://github.com/landlock-lsm/landlock-test-tools/pull/17
[3]: https://github.com/micromaomao/linux-dev/commit/f1865ce970af97ac3b6f4edf580529b8cdc66371

Patch based on mic/next (v6.16-rc2+)

Closes: https://github.com/landlock-lsm/linux/issues/1

Changes since v1:
- Entirely replaced the hlist-based hashtable with an array-based one.
- This time added support for net rules too.

v1: https://lore.kernel.org/all/cover.1747836146.git.m@maowtm.org/

Tingmao Wang (12):
  landlock: Set the max rules limit in a domain to U16_MAX.
  landlock/domain: Define structure and macros for flat-array domains
  landlock: Define coalesced hashtable and implement finding
  landlock/domain: Implement finding rules
  landlock/coalesced_hash: Implement insert
  landlock/domain: Implement merging of a parent domain and a ruleset
  landlock/domain: Define alloc and free
  landlock/domain: Add landlock_domain_merge_ruleset
  landlock: Update various code to use landlock_domain
  landlock: Remove unused code
  landlock/task: Fix incorrect BUILD_BUG_ON() in domain_is_scoped
  landlock: Use a hash function that does not involve division

 security/landlock/audit.c          |   8 +-
 security/landlock/coalesced_hash.h | 399 +++++++++++++++++
 security/landlock/cred.c           |  12 +-
 security/landlock/cred.h           |  14 +-
 security/landlock/domain.c         | 681 +++++++++++++++++++++++++++++
 security/landlock/domain.h         | 342 ++++++++++++++-
 security/landlock/fs.c             |  34 +-
 security/landlock/limits.h         |   2 +-
 security/landlock/net.c            |  12 +-
 security/landlock/ruleset.c        | 319 +-------------
 security/landlock/ruleset.h        |  71 +--
 security/landlock/syscalls.c       |   8 +-
 security/landlock/task.c           |  31 +-
 13 files changed, 1499 insertions(+), 434 deletions(-)
 create mode 100644 security/landlock/coalesced_hash.h


base-commit: 86fdfbade8bb09ce2be2ff334c743fe19815ceb2
-- 
2.49.0