Skip to content

RFC landlock: Use coalesced hashtable for merged domains

Tingmao Wang linux-security-module 1 version New

Get series with b4
b4 am [email protected]

Versions newest first

  1. v2 RFC Latest12 patches 0 repliesNew

Changes in v2 from the cover letter

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

Patches in v2 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/12landlock: Set the max rules limit in a domain to U16_MAX.security/landlock/limits.h+1 -10 replies
2/12landlock/domain: Define structure and macros for flat-array domainssecurity/landlock/domain.c security/landlock/domain.h+133 -00 replies
3/12landlock: Define coalesced hashtable and implement findingsecurity/landlock/coalesced_hash.h+130 -00 replies
4/12landlock/domain: Implement finding rulessecurity/landlock/domain.h+67 -00 replies
5/12landlock/coalesced_hash: Implement insertsecurity/landlock/coalesced_hash.h+265 -00 replies
6/12landlock/domain: Implement merging of a parent domain and a rulesetsecurity/landlock/domain.c security/landlock/ruleset.c security/landlock/ruleset.h+238 -160 replies
7/12landlock/domain: Define alloc and freesecurity/landlock/domain.c security/landlock/domain.h+134 -00 replies
8/12landlock/domain: Add landlock_domain_merge_rulesetsecurity/landlock/domain.c security/landlock/domain.h+245 -20 replies
9/12landlock: Update various code to use landlock_domainsecurity/landlock/audit.c security/landlock/cred.c security/landlock/cred.h +8 more+190 -1690 replies
10/12landlock: Remove unused codesecurity/landlock/ruleset.c security/landlock/ruleset.h+1 -2480 replies
11/12landlock/task: Fix incorrect BUILD_BUG_ON() in domain_is_scopedsecurity/landlock/task.c+4 -30 replies
12/12landlock: Use a hash function that does not involve divisionsecurity/landlock/coalesced_hash.h security/landlock/domain.c security/landlock/domain.h+177 -810 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v2 yet.

Read the v2 thread

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

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/[email protected]/
[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+)

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/[email protected]/

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

Signature · 1 line
2.49.0