landlock: Use hashtable for merged domains
Subsystems (2)
Hi Mickaël,
This is a set of (incomplete) patches for the "domain hashtable" work. While this is still a WIP, I'm sending it now as per our discussion. You can take a look and see if the approach needs correcting / if we want to go ahead with using hashtable.
Currently only implemented for fs access.
This set of changes is also available on the landlock-hashmap branch of
https://github.com/micromaomao/linux-dev.git
struct landlock_domain
----------------------
One of the major thing I'm not sure about in this patch is the fact that I've decided to create a standalone struct landlock_domain, instead of re-using landlock_ruleset. My original hope was that it might help make the code a bit clearer - struct landlock_ruleset would just be for unmerged rulesets (and it can use rbtree if we still wants to), and we can use this new type for domains (and add new fields and locks to it that wouldn't be on a ruleset, for the mutable domains / supervisor work).
I also wanted to split the logic of dealing with rules in a merged domain (hence needing to copy multiple layers etc) out of create_rule and insert_rule, and simply these functions (especially insert_rule) by letting them just deal with unmerged rulesets (so only one layer) - the logic for merged domains would be different anyway since it's no longer a rbtree walk (but something like landlock_hash_upsert in patch 8 instead).
However, looking back at it, I'm not sure if creating this landlock_domain was actually a good idea. Going down this route eventually I will just have to move all the domain-related logic from using ruleset to using landlock_domain. If we decide to use hashtable for unmerged rulesets too (not done in this patch, and need more thoughts on how that would work), then separating this out is even less value.
Regardless, the relevant code in this patch should still be easily portable to just extend landlock_ruleset with hashtables, so I'm happy to do that instead in the next version.
Hashtable implementation
------------------------
Since I couldn't find a suitable existing wrapper for runtime-sized (but fixed after creation) hashtables, this patch uses a newly hand-rolled implementation. It's not very complex so this might be fine, but there is also rhashtable which would be especially suitable if we want to use hash table for unmerged rulesets too. See patch 2 message for details.
Testing
-------
selftests/landlock/fs_tests all passes under KASAN, lockdep etc. Other tests showed no obvious issues, but base and net fails due to missing config (no MPTCP, no CONFIG_ASYMMETRIC_KEY_TYPE i.e. keyctl)
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 https://github.com/landlock-lsm/landlock-test-tools/pull/17
2. A more "typical" workload I put together quickly, calling git status and the like repeatedly:
https://github.com/torvalds/linux/commit/f1865ce970af97ac3b6f4edf580529b8cdc66371
On the "typical" workload, which has 2 layers and ~15 rules, we have:
Comparing: orig hashtable (% change)
landlock_overhead:
(this is the % of time spent in landlock hook in the open syscall)
avg = 34 33 (-2.9%)
median = 34 33 (-2.9%) landlock_hook: avg = 837 775 (-7.4%) (unit: ns)
median = 813 748 (-8.0%) (unit: ns) open_syscall: avg = 2429 2324 (-4.3%) (unit: ns)
median = 2370 2265 (-4.4%) (unit: ns)Using the microbench script, for an extreme case on a path beneath 28 directories and with 10000 rules:
Comparing: orig hashtable (% change)
landlock_overhead: avg = 27 24 (-11.1%)
median = 29 25 (-13.8%)
landlock_hook: avg = 1913 1577 (-17.6%)
median = 1884 1544 (-18.0%)
open_syscall: avg = 6775 6259 (-7.6%)
median = 6666 6115 (-8.3%)The full results can be found at
https://fileshare.maowtm.org/landlock/20250521/index.html
Tingmao Wang (10):
landlock: Add some debug output
landlock/hash: define (dynamic, non-resizable) hash table helpers landlock/hash: Use linear search for small tables landlock/ruleset: Rename and extract create_rule
Add hlist_node member to struct landlock_rule landlock/domain: Define landlock_domain
landlock: Add the new domain to landlock_cred_security
landlock: Construct the inode hashtable in the new landlock_domain landlock/fs: Use the new hashtable-based domain to find inode rules
landlock: Debug print inode hashtable in landlock_merge_ruleset2
security/landlock/cred.c | 8 +- security/landlock/cred.h | 1 + security/landlock/domain.c | 145 +++++++++++++++++ security/landlock/domain.h | 45 ++++++ security/landlock/fs.c | 107 +++++++++---- security/landlock/fs.h | 1 + security/landlock/hash.h | 294 +++++++++++++++++++++++++++++++++++ security/landlock/ruleset.c | 80 +--------- security/landlock/ruleset.h | 99 +++++++++++- security/landlock/syscalls.c | 35 +++++ 10 files changed, 702 insertions(+), 113 deletions(-) create mode 100644 security/landlock/hash.h
base-commit: 3039ed432745f8fdf5cbb43fdc60b2e1aad624c1 --
2.49.0
RFC PATCH 1/10 landlock: Add some debug output
They are behind #ifdef DEBUG for now as iterating over all the rules / each access bits might make it slower (even if dynamic pr_debug makes the print itself nop).
--- security/landlock/fs.c | 47 ++++++++++++++++++++++++++++++++++++ security/landlock/fs.h | 1 + security/landlock/syscalls.c | 26 ++++++++++++++++++++ 3 files changed, 74 insertions(+)
security/landlock/fs.c +47 -0
@@ -772,6 +772,10 @@ static bool is_access_to_paths_allowed(layer_mask_t (*layer_masks_child1)[LANDLOCK_NUM_ACCESS_FS ] =NULL , (*layer_masks_child2)[LANDLOCK_NUM_ACCESS_FS ] =NULL ; +#ifdef DEBUG +layer_mask_t all_layers = (1 << domain->num_layers) -1 ; +#endif +if (!access_request_parent1 && !access_request_parent2)return true;
@@ -800,6 +804,14 @@ static bool is_access_to_paths_allowed( access_masked_parent1 = access_masked_parent2 =landlock_union_access_masks (domain).fs; is_dom_check = true; + +#ifdef DEBUG +pr_debug ( +"check access to path %pd4 for access request p1 %x p2 %x:\n" , + path->dentry, access_request_parent1, + access_request_parent2); +#endif + }else {if (WARN_ON_ONCE (dentry_child1 || dentry_child2))return false;
@@ -807,7 +819,15 @@ static bool is_access_to_paths_allowed( access_masked_parent1 = access_request_parent1; access_masked_parent2 = access_request_parent2; is_dom_check = false; + +#ifdef DEBUG +pr_debug ("check access to path %pd4 for access request %x:\n" , + path->dentry, access_request_parent1); +#endif } +#ifdef DEBUG +pr_debug (" (need layer mask %x)" , all_layers); +#endif if (unlikely (dentry_child1)) { landlock_unmask_layers(
@@ -892,6 +912,33 @@ static bool is_access_to_paths_allowed( layer_masks_parent2, ARRAY_SIZE(*layer_masks_parent2)); +#ifdef DEBUG + { +rcu_read_lock (); +pr_debug (" %pd: ino %lu (%p), rule: %s, allow: %s\n" , + walker_path.dentry, + walker_path.dentry->d_inode->i_ino, + walker_path.dentry->d_inode, + rule ?"exists" :"does not exist" , + allowed_parent1 ?"yes" :"no" ); +unsigned long access_masked = access_masked_parent1; +unsigned long access_bit; +if (rule) { +for_each_set_bit ( + access_bit, &access_masked, +ARRAY_SIZE (*layer_masks_parent1)) { +pr_debug ( +" access %x allowed by layer mask %d\n" , + (1 << access_bit), + (~(*layer_masks_parent1) + [access_bit]) & + all_layers); + } + } +rcu_read_unlock (); + } +#endif +/* Stops when a rule from each layer grants access. */ if (allowed_parent1 && allowed_parent2)break ;
security/landlock/fs.h +1 -0
@@ -15,6 +15,7 @@#include <linux/init.h> #include <linux/rcupdate.h> +#include "common.h" #include "access.h" #include "cred.h" #include "ruleset.h"
security/landlock/syscalls.c +26 -0
@@ -559,6 +559,32 @@ SYSCALL_DEFINE2(landlock_restrict_self, const int, ruleset_fd, const __u32, new_dom->hierarchy->log_status =LANDLOCK_LOG_DISABLED ;#endif /* CONFIG_AUDIT */ +#ifdef DEBUG +pr_debug ("%s[%d] restricting self with landlock\n" , current->comm, + current->pid); +struct rb_node *node; +pr_debug ("inode tree:\n" ); +for (node =rb_first (&new_dom->root_inode); node; + node =rb_next (node)) { +const struct landlock_rule *rule = + rb_entry(node, struct landlock_rule, node); +spinlock_t *lock = &rule->key.object->lock; +rcu_read_lock (); +spin_lock (lock); +struct inode *inode = rule->key.object->underobj; +if (inode) +pr_debug (" rule: ino %lu (%p)\n" , inode->i_ino, inode); +else +pr_debug (" rule: inode released\n" ); +for (size_t i =0 ; i < rule->num_layers; i++) { +pr_debug (" layer %u: access %x\n" , + rule->layers[i].level, rule->layers[i].access); + } +spin_unlock (lock); +rcu_read_unlock (); + } +#endif /* DEBUG */ +/* Replaces the old (prepared) domain. */ landlock_put_ruleset (new_llcred->domain); new_llcred->domain = new_dom;
Signature · 1 line
2.49.0
RFC PATCH 2/10 landlock/hash: define (dynamic, non-resizable) hash table helpers
In reply to Tingmao WangWhile there is already include/linux/hash.h, it relies on the static size of the array as the size of the hash table, and thus is inconvenient to use for this case where we dynamically compute how many slots we need.
There is also the relativistic hash tables in rhashtable.h which supports dynamic resizes etc, but is more complicated and might be slower to access?
However, on second thought, I'm wondering if we should just use hash tables for both domain and a not-yet-merged ruleset anyway (which saves us from having a union in landlock_rule). If we do that then we should indeed just use rhashtable.
--- security/landlock/hash.h | 117 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 117 insertions(+) create mode 100644 security/landlock/hash.h
security/landlock/hash.h new file +117 -0
@@ -0,0 +1,117 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +/* +* Landlock - Domain hashtable mainpulation +* +* Copyright © 2025 Tingmao Wang <[email protected]> +*/ + +#ifndef _SECURITY_LANDLOCK_HASH_H +#define _SECURITY_LANDLOCK_HASH_H + +#include <linux/slab.h> +#include <linux/hash.h> + +#include "ruleset.h" + +struct landlock_hashtable { +struct hlist_head *hlist; + +/** +* @hash_bits: Number of bits in this hash index (i.e. hlist has +* 2^this many elements). +*/ +int hash_bits; +}; + +#define landlock_hash_for_each (rule, ht, i) \ + for (i = 0; i < (1ULL << (ht)->hash_bits); i += 1) \ + hlist_for_each_entry(rule, &(ht)->hlist[i], hlist) + +#define landlock_hash_for_each_safe (rule, tmp, ht, i) \ + for (i = 0; i < (1ULL << (ht)->hash_bits); i += 1) \ + hlist_for_each_entry_safe(rule, tmp, &(ht)->hlist[i], hlist) + +static inline int landlock_hash_init (const size_t expected_num_entries, +struct landlock_hashtable *out_ht) +{ +size_t table_sz =1 ; +int hash_bits =0 ; + +if (likely (expected_num_entries >0 )) { + table_sz =roundup_pow_of_two (expected_num_entries); + hash_bits =fls_long (table_sz -1 ); + } + +/* +* We allocate a table even if expected_num_entries == 0 to avoid +* unnecessary branching in lookup code +*/ + + out_ht->hash_bits = hash_bits; + out_ht->hlist =kcalloc (table_sz,sizeof (struct hlist_head ), +GFP_KERNEL_ACCOUNT ); +if (!out_ht->hlist) { +return -ENOMEM ; + } + +return 0 ; +} + +static inline void landlock_hash_free (struct landlock_hashtable *ht, +const enum landlock_key_type key_type) +{ +struct landlock_rule *rule; +struct hlist_node *tmp; +size_t i; + +if (key_type ==LANDLOCK_KEY_INODE ) +might_sleep (); + +if (!ht->hlist) +return ; + +landlock_hash_for_each_safe (rule, tmp, ht, i) + { +free_rule (rule, key_type); + } +kfree (ht->hlist); + ht->hlist =NULL ; +} + +static inline u32 landlock_hash_key (const union landlock_key key, +const int hash_bits) +{ +return hash_ptr ((void *)key.data, hash_bits); +} + +static inline struct landlock_rule * +landlock_hash_find (const struct landlock_hashtable *const ht, +const union landlock_key key) +{ +struct hlist_head *head; +struct landlock_rule *rule; + + head = &ht->hlist[landlock_hash_key (key, ht->hash_bits)]; + +hlist_for_each_entry (rule, head, hlist) { +if (rule->key.data == key.data) +return rule; + } + +return NULL ; +} + +/** +* @landlock_hash_count - Return number of entries in the hashtable. +*/ +static inline size_t landlock_hash_count (const struct landlock_hashtable *ht) +{ +size_t num_entries =0 ; +struct landlock_rule *rule; +size_t i; +landlock_hash_for_each (rule, ht, i) + { + num_entries +=1 ; + } +return num_entries; +}
Signature · 1 line
2.49.0
Mickaël Salaün
maintainerRe: [RFC PATCH 02/10] landlock/hash: define (dynamic, non-resizable) hash table helpers
Quoted 11 lines · Tingmao Wang
While there is already
include/linux/hash.h, it relies on the static size of the array as the size of the hash table, and thus is inconvenient to use for this case where we dynamically compute how many slots we need.There is also the relativistic hash tables in
rhashtable.hwhich supports dynamic resizes etc, but is more complicated and might be slower to access?However, on second thought, I'm wondering if we should just use hash tables for both domain and a not-yet-merged ruleset anyway (which saves us from having a union in
landlock_rule). If we do that then we should indeed just use rhashtable.
Thinking more about it, the important properties are that we can have a lot of domains/tables (i.e. sandboxed processes) with a few entries/rules (e.g. ~30 rules seems reasonable for now). We should then try to minimize the total amount of memory while still making access checks quick. As you noted, the cost of hashing should also not be ignored.
Instead of a hash table per domain, what about flat arrays with binary search? Here is a proposal:
struct landlock_domain_index {
union landlock_key key;
u32 shift; // value to add to this array's index to jump to the set
// of mapped landlock_layer
u32 num_layers;
}; // 128-bit (or 96-bit) alligned// Theoretical landlock_domain
struct landlock_domain {
struct landlock_hierarchy *hierarchy;
union {
// See landlock_ruleset's union
};
u32 num_fs; // number of FS indexes
u32 num_net; // number of net indexes
struct access_masks access_masks[];
struct landlock_domain_index fs_indexes[num_fs];
struct landlock_layer fs_layers[sum of FS rules' layers];
struct landlock_domain_index net_indexes[num_net];
struct landlock_layer net_layers[sum of net rules' layers];
};// Real landlock_domain
struct landlock_domain {
struct landlock_hierarchy *hierarchy;
union {
// See landlock_ruleset's union
};
u32 num_fs; // number of FS indexes
u32 num_net; // number of net indexes
u32 rules[]; // underlying typed arrays accessed via helpers
};The landlock_domain is a contiguously allocated memory buffer containing variable-size arrays improving locality. Another advantage is that we would not get any potential allocation errors once the buffer is allocated which should simplify domain creation. Also, we avoid the union in landlock_rule (patch 5) and only use landlock_rule in landlock_ruleset.
An alternative approach would be to use a hash table instead of the array (extending landlock_domain_index with a pointer/shift to the next collision) but still with this big buffer. I'm not sure the perf impact would be noticable but it might be worse a try.
Quoted 13 lines
Signed-off-by Tingmao Wang <[email protected]>--- security/landlock/hash.h | 117 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 117 insertions(+) create mode 100644 security/landlock/hash.hsecurity/landlock/hash.h new file +0
-0
security/landlock/hash.h line 3
Quoted 3 lines
security/landlock/hash.h new file +3
-0@@ -0,0 +1,117 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +/* +* Landlock - Domain hashtable mainpulation
typo
Quoted 4 lines
security/landlock/hash.h new file +4
-0+* +* Copyright © 2025 Tingmao Wang <[email protected]> +*/ +
security/landlock/hash.h line 17
Quoted 10 lines
security/landlock/hash.h new file +10
-0+#ifndef _SECURITY_LANDLOCK_HASH_H +#define _SECURITY_LANDLOCK_HASH_H + +#include <linux/slab.h> +#include <linux/hash.h> + +#include "ruleset.h" + +struct landlock_hashtable { + struct hlist_head *hlist;
A simple linked-list would be enough.
Quoted 10 lines
security/landlock/hash.h new file +10
-0+ +/** +* @hash_bits: Number of bits in this hash index (i.e. hlist has +* 2^this many elements). +*/ +int hash_bits; +}; + +#define landlock_hash_for_each (rule, ht, i) \ + for (i = 0; i < (1ULL << (ht)->hash_bits); i += 1) \
security/landlock/hash.h line 37
Quoted 10 lines
security/landlock/hash.h new file +10
-0+ hlist_for_each_entry(rule, &(ht)->hlist[i], hlist) + +#define landlock_hash_for_each_safe (rule, tmp, ht, i) \ + for (i = 0; i < (1ULL << (ht)->hash_bits); i += 1) \ + hlist_for_each_entry_safe(rule, tmp, &(ht)->hlist[i], hlist) + +static inline int landlock_hash_init (const size_t expected_num_entries, +struct landlock_hashtable *out_ht) +{ +size_t table_sz =1 ;
Please use variables with full name when they are not too big:table_size in this case.
security/landlock/hash.h line 41
Quoted 4 lines
security/landlock/hash.h new file +4
-0+int hash_bits =0 ; + +if (likely (expected_num_entries >0 )) { + table_sz =roundup_pow_of_two (expected_num_entries);
With roundup_pow_of_two() we'll get a few collisions but a big table. What would be the impact of using roundup_pow_of_two() instead to have a compact hash table (with more collisions)?
Quoted 80 lines
security/landlock/hash.h new file +76
-0+ hash_bits =fls_long (table_sz -1 ); + } + +/* +* We allocate a table even if expected_num_entries == 0 to avoid +* unnecessary branching in lookup code +*/ + + out_ht->hash_bits = hash_bits; + out_ht->hlist =kcalloc (table_sz,sizeof (struct hlist_head ), +GFP_KERNEL_ACCOUNT ); +if (!out_ht->hlist) { +return -ENOMEM ; + } + +return 0 ; +} + +static inline void landlock_hash_free (struct landlock_hashtable *ht, +const enum landlock_key_type key_type) +{ +struct landlock_rule *rule; +struct hlist_node *tmp; +size_t i; + +if (key_type ==LANDLOCK_KEY_INODE ) +might_sleep (); + +if (!ht->hlist) +return ; + +landlock_hash_for_each_safe (rule, tmp, ht, i) + { +free_rule (rule, key_type); + } +kfree (ht->hlist); + ht->hlist =NULL ; +} + +static inline u32 landlock_hash_key (const union landlock_key key, +const int hash_bits) +{ +return hash_ptr ((void *)key.data, hash_bits); +} + +static inline struct landlock_rule * +landlock_hash_find (const struct landlock_hashtable *const ht, +const union landlock_key key) +{ +struct hlist_head *head; +struct landlock_rule *rule; + + head = &ht->hlist[landlock_hash_key (key, ht->hash_bits)]; + +hlist_for_each_entry (rule, head, hlist) { +if (rule->key.data == key.data) +return rule; + } + +return NULL ; +} + +/** +* @landlock_hash_count - Return number of entries in the hashtable. +*/ +static inline size_t landlock_hash_count (const struct landlock_hashtable *ht) +{ +size_t num_entries =0 ; +struct landlock_rule *rule; +size_t i; +landlock_hash_for_each (rule, ht, i) + { + num_entries +=1 ; + } +return num_entries; +}Signature · 1 line
2.49.0
Re: [RFC PATCH 02/10] landlock/hash: define (dynamic, non-resizable) hash table helpers
Quoted 20 lines · Mickaël Salaün
Quoted 11 lines · Tingmao Wang
While there is already
include/linux/hash.h, it relies on the static size of the array as the size of the hash table, and thus is inconvenient to use for this case where we dynamically compute how many slots we need.There is also the relativistic hash tables in
rhashtable.hwhich supports dynamic resizes etc, but is more complicated and might be slower to access?However, on second thought, I'm wondering if we should just use hash tables for both domain and a not-yet-merged ruleset anyway (which saves us from having a union in
landlock_rule). If we do that then we should indeed just use rhashtable.Thinking more about it, the important properties are that we can have a lot of domains/tables (i.e. sandboxed processes) with a few entries/rules (e.g. ~30 rules seems reasonable for now). We should then try to minimize the total amount of memory while still making access checks quick. As you noted, the cost of hashing should also not be ignored.
Quoted 2 lines
Instead of a hash table per domain, what about flat arrays with binary search? Here is a proposal:
I think this makes sense in terms of reducing memory footprint.
My understanding of the Slab allocator is that objects are allocated in power-of-two sized caches, so with a single-layer, 44 bytes landlock_rule, we will still use 64 bytes. Putting them in an array, especially with your proposed structure, would reduce this.
I also checked how the allocations actually are distributed in the current implementation. Dumping the addresses of the landlock_rule objects allocated and sorting them by the address, we see:
# env LL_FS_RO=/usr:/bin:/etc:/lib:/sys:/dev:/home/mao/.config:/home/mao/linux LL_FS_RW=/tmp:/proc:/dev/tty:/dev/null:/dev/zero \
Quoted 1 line
./sandboxer bash
Executing the sandboxed command...
bash: /home/mao/.bashrc: Permission denied
mao@linux-devbox-vm:~$ cat /proc/dump_landlock_domain
Ruleset: ffff9268489451e0
Inode tree:
ffff92684e767100: inode 5374060 in fs ext4
ffff92684e767380 (+640 (rule itself was 44 bytes)): inode 2883604 in fs ext4
ffff92684e767440 (+192 (rule itself was 44 bytes)): inode 2883992 in fs ext4
ffff92684e767580 (+320 (rule itself was 44 bytes)): inode 11 in fs devtmpfs
ffff92684e767740 (+448 (rule itself was 44 bytes)): inode 5377989 in fs ext4
ffff92684e767800 (+192 (rule itself was 44 bytes)): inode 1 in fs devtmpfs
ffff92684e7678c0 (+192 (rule itself was 44 bytes)): inode 1 in fs tmpfs
ffff92684e767980 (+192 (rule itself was 44 bytes)): inode 6 in fs devtmpfs
ffff92684e767b40 (+448 (rule itself was 44 bytes)): inode 4 in fs devtmpfs
ffff92684e767bc0 (+128 (rule itself was 44 bytes)): inode 2883585 in fs ext4
ffff92684e767c40 (+128 (rule itself was 44 bytes)): inode 1 in fs sysfs
ffff92684e767cc0 (+128 (rule itself was 44 bytes)): inode 6815745 in fs ext4
ffff92684e767f80 (+704 (rule itself was 44 bytes)): inode 1 in fs procNote: source code for this at
https://github.com/micromaomao/linux-dev/commit/16c318fcbc64c23b87ca67836771f710d0d0ccf1
(this is a typical result out of several repeat runs) (KASLR etc disabled, no_hash_pointers)
Because all landlock rules are copied at domain creation time, I previously thought that they are likely to be allocated close together (perhaps there will be some fragmentation due to a ruleset extending an existing rule in the parent domain), but it looks like they are still spreaded out a bit for some reason, and if the allocations are sparse during domain creation time, this situation won't fix itself and could slow down all access checks. (Maybe on a single core system, with nothing else touching the kmem cache when the domain is being merged, they would be allocated together?)
I'm not sure about the performance of binary search vs rbtrees. I can see that the improved locality should help, but going by my benchmark of the hashtable domains, I'm not sure how much of a difference it make, and whether it would be worth the added complexity. I could try implementing this flat array + binary search approach and run the existing benchmarks on it tho (but as of writing this I haven't).
Quoted 5 lines
struct landlock_domain_index {
union landlock_key key;
u32 shift; // value to add to this array's index to jump to the set
// of mapped landlock_layerCan you clarify the comment? Is it the index into the layers array, or are you suggesting adding the index of the current landlock_domain_index with this shift value, and use that to index into the layers array?
While it's probably an unlikely situation, what if there are more than 2^29 rules, each having 16 layers? I think that would overflow this u32 even if it is an offset, and this is allowed as LANDLOCK_MAX_NUM_RULES is currently defined as U32_MAX.
(Unrelated to this patch, but I think once we have the supervise feature in, I can see a (probably badly implemented) supervisor getting close to this limit if the sandboxed application creates / delete and recreates lots of temporary files under /tmp)
Quoted 2 lines
u32 num_layers; }; // 128-bit (or 96-bit) alligned
I guess this has to be 128 bits aligned if we have an u32 num_layers. Because we allow 16 layers, if we make it an u16, it would actually need to be the number of layers minus 1. However maybe that is overcomplicating it and we should just make this 128 bits aligned (otherwise we have to deal with unaligned reads of the landlock_key->object too).
Quoted 15 lines
// Theoretical
landlock_domainstruct landlock_domain { struct landlock_hierarchy *hierarchy; union { // See landlock_ruleset's union }; u32 num_fs; // number of FS indexes u32 num_net; // number of net indexes struct access_masks access_masks[]; struct landlock_domain_index fs_indexes[num_fs]; struct landlock_layer fs_layers[sum of FS rules' layers]; struct landlock_domain_index net_indexes[num_net]; struct landlock_layer net_layers[sum of net rules' layers]; };
(Unrelated to this patch specifically, but I would probably like to use this domain struct for the mutable part of a domain as well later. In that case the hierarchy pointer would be unused.)
Quoted 12 lines
// Real
landlock_domainstruct landlock_domain { struct landlock_hierarchy *hierarchy; union { // See landlock_ruleset's union }; u32 num_fs; // number of FS indexes u32 num_net; // number of net indexes u32 rules[]; // underlying typed arrays accessed via helpers };
Quoted 6 lines
The
landlock_domainis a contiguously allocated memory buffer containing variable-size arrays improving locality. Another advantage is that we would not get any potential allocation errors once the buffer is allocated which should simplify domain creation. Also, we avoid the union inlandlock_rule(patch 5) and only uselandlock_ruleinlandlock_ruleset.
I think doing this definitely has positives especially in terms of memory, however I'm worried about the complexity here. Since we will have to do various index calculation and use it to access variable-sized arrays, I'm somewhat afraid that any mistake could end up either leaking kernel pointers, or at worst, memory corruption.
We should probably have a len_rules, and check (WARN_ON_ONCE and if fails returns -EINVAL) that any computed indices lies within range before accessing it.
Quoted 5 lines
An alternative approach would be to use a hash table instead of the array (extending
landlock_domain_indexwith a pointer/shift to the next collision) but still with this big buffer. I'm not sure the perf impact would be noticable but it might be worse a try.
I can give that a try too and measure benchmarks.
BTW, going by the direction this discussion is going, I assume we're on board with a separate landlock_domain, and don't plan to change how unmerged landlock_ruleset are stored (at least for now)? If so I can probably start work on quiet rules, removing access bits / rules by intersect, etc as discussed in
https://github.com/landlock-lsm/linux/issues/44#issuecomment-2876500918
Quoted 8 lines
Quoted 8 lines
Signed-off-by Tingmao Wang <[email protected]>--- security/landlock/hash.h | 117 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 117 insertions(+) create mode 100644 security/landlock/hash.h
Quoted 11 lines
security/landlock/hash.h line 3
Quoted 9 lines
security/landlock/hash.h new file +3
-0@@ -0,0 +1,117 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +/* +* Landlock - Domain hashtable mainpulation typo
ack
Quoted 17 lines
Quoted 5 lines
security/landlock/hash.h new file +4
-0+* +* Copyright © 2025 Tingmao Wang <[email protected]> +*/ +security/landlock/hash.h line 17
Quoted 10 lines
security/landlock/hash.h new file +10
-0+#ifndef _SECURITY_LANDLOCK_HASH_H +#define _SECURITY_LANDLOCK_HASH_H + +#include <linux/slab.h> +#include <linux/hash.h> + +#include "ruleset.h" + +struct landlock_hashtable { + struct hlist_head *hlist;A simple linked-list would be enough.
I'm not sure I understand what you meant by a "simple linked-list" - do you mean like an array of landlock_rules, each itself is part of a linked list of all the rules that hashed to the same key?
Anyway, since we identified a flat array approach (whether we hash or binary search), I'm gonna try that instead.
Quoted 25 lines
Quoted 11 lines
security/landlock/hash.h new file +10
-0+ +/** +* @hash_bits: Number of bits in this hash index (i.e. hlist has +* 2^this many elements). +*/ +int hash_bits; +}; + +#define landlock_hash_for_each (rule, ht, i) \ + for (i = 0; i < (1ULL << (ht)->hash_bits); i += 1) \security/landlock/hash.h line 37
Quoted 10 lines
security/landlock/hash.h new file +10
-0+ hlist_for_each_entry(rule, &(ht)->hlist[i], hlist) + +#define landlock_hash_for_each_safe (rule, tmp, ht, i) \ + for (i = 0; i < (1ULL << (ht)->hash_bits); i += 1) \ + hlist_for_each_entry_safe(rule, tmp, &(ht)->hlist[i], hlist) + +static inline int landlock_hash_init (const size_t expected_num_entries, +struct landlock_hashtable *out_ht) +{ +size_t table_sz =1 ;Please use variables with full name when they are not too big:
table_sizein this case.
Quoted 8 lines
security/landlock/hash.h line 41
Quoted 4 lines
security/landlock/hash.h new file +4
-0+int hash_bits =0 ; + +if (likely (expected_num_entries >0 )) { + table_sz =roundup_pow_of_two (expected_num_entries);With
roundup_pow_of_two()we'll get a few collisions but a big table. What would be the impact of usingroundup_pow_of_two()instead to have a compact hash table (with more collisions)?
I assume you meant using rounddown_pow_of_two - I can give it a quick test too with the flat array approach.
Quoted 81 lines
Quoted 81 lines
security/landlock/hash.h new file +76
-1+ hash_bits =fls_long (table_sz -1 ); + } + +/* +* We allocate a table even if expected_num_entries == 0 to avoid +* unnecessary branching in lookup code +*/ + + out_ht->hash_bits = hash_bits; + out_ht->hlist =kcalloc (table_sz,sizeof (struct hlist_head ), +GFP_KERNEL_ACCOUNT ); +if (!out_ht->hlist) { +return -ENOMEM ; + } + +return 0 ; +} + +static inline void landlock_hash_free (struct landlock_hashtable *ht, +const enum landlock_key_type key_type) +{ +struct landlock_rule *rule; +struct hlist_node *tmp; +size_t i; + +if (key_type ==LANDLOCK_KEY_INODE ) +might_sleep (); + +if (!ht->hlist) +return ; + +landlock_hash_for_each_safe (rule, tmp, ht, i) + { +free_rule (rule, key_type); + } +kfree (ht->hlist); + ht->hlist =NULL ; +} + +static inline u32 landlock_hash_key (const union landlock_key key, +const int hash_bits) +{ +return hash_ptr ((void *)key.data, hash_bits); +} + +static inline struct landlock_rule * +landlock_hash_find (const struct landlock_hashtable *const ht, +const union landlock_key key) +{ +struct hlist_head *head; +struct landlock_rule *rule; + + head = &ht->hlist[landlock_hash_key (key, ht->hash_bits)]; + +hlist_for_each_entry (rule, head, hlist) { +if (rule->key.data == key.data) +return rule; + } + +return NULL ; +} + +/** +* @landlock_hash_count - Return number of entries in the hashtable. +*/ +static inline size_t landlock_hash_count (const struct landlock_hashtable *ht) +{ +size_t num_entries =0 ; +struct landlock_rule *rule; +size_t i; +landlock_hash_for_each (rule, ht, i) + { + num_entries +=1 ; + } +return num_entries; +} --2.49.0
Re: [RFC PATCH 02/10] landlock/hash: define (dynamic, non-resizable) hash table helpers
Quoted 56 lines · Tingmao Wang
Quoted 20 lines · Mickaël Salaün
Quoted 11 lines · Tingmao Wang
While there is already
include/linux/hash.h, it relies on the static size of the array as the size of the hash table, and thus is inconvenient to use for this case where we dynamically compute how many slots we need.There is also the relativistic hash tables in
rhashtable.hwhich supports dynamic resizes etc, but is more complicated and might be slower to access?However, on second thought, I'm wondering if we should just use hash tables for both domain and a not-yet-merged ruleset anyway (which saves us from having a union in
landlock_rule). If we do that then we should indeed just use rhashtable.Thinking more about it, the important properties are that we can have a lot of domains/tables (i.e. sandboxed processes) with a few entries/rules (e.g. ~30 rules seems reasonable for now). We should then try to minimize the total amount of memory while still making access checks quick. As you noted, the cost of hashing should also not be ignored.
Quoted 2 lines
Instead of a hash table per domain, what about flat arrays with binary search? Here is a proposal:
I think this makes sense in terms of reducing memory footprint.
My understanding of the Slab allocator is that objects are allocated in power-of-two sized caches, so with a single-layer, 44 bytes
landlock_rule, we will still use 64 bytes. Putting them in an array, especially with your proposed structure, would reduce this.I also checked how the allocations actually are distributed in the current implementation. Dumping the addresses of the
landlock_ruleobjects allocated and sorting them by the address, we see:# env LL_FS_RO=/usr:/bin:/etc:/lib:/sys:/dev:/home/mao/.config:/home/mao/linux LL_FS_RW=/tmp:/proc:/dev/tty:/dev/null:/dev/zero \Quoted 1 line
./sandboxer bash
Executing the sandboxed command...
bash:/home/mao/.bashrc: Permission deniedmao@linux-devbox-vm:~$ cat /proc/dump_landlock_domain Ruleset: ffff9268489451e0 Inode tree: ffff92684e767100: inode 5374060 in fs ext4 ffff92684e767380 (+640 (rule itself was 44 bytes)): inode 2883604 in fs ext4 ffff92684e767440 (+192 (rule itself was 44 bytes)): inode 2883992 in fs ext4 ffff92684e767580 (+320 (rule itself was 44 bytes)): inode 11 in fs devtmpfs ffff92684e767740 (+448 (rule itself was 44 bytes)): inode 5377989 in fs ext4 ffff92684e767800 (+192 (rule itself was 44 bytes)): inode 1 in fs devtmpfs ffff92684e7678c0 (+192 (rule itself was 44 bytes)): inode 1 in fs tmpfs ffff92684e767980 (+192 (rule itself was 44 bytes)): inode 6 in fs devtmpfs ffff92684e767b40 (+448 (rule itself was 44 bytes)): inode 4 in fs devtmpfs ffff92684e767bc0 (+128 (rule itself was 44 bytes)): inode 2883585 in fs ext4 ffff92684e767c40 (+128 (rule itself was 44 bytes)): inode 1 in fs sysfs ffff92684e767cc0 (+128 (rule itself was 44 bytes)): inode 6815745 in fs ext4 ffff92684e767f80 (+704 (rule itself was 44 bytes)): inode 1 in fs proc
Quoted 5 lines
Note: source code for this at
https://github.com/micromaomao/linux-dev/commit/16c318fcbc64c23b87ca67836771f710d0d0ccf1(this is a typical result out of several repeat runs) (KASLR etc disabled,
no_hash_pointers)
Sorry I meant KASAN, KASLR is intact here.
Quoted 278 lines
Because all landlock rules are copied at domain creation time, I previously thought that they are likely to be allocated close together (perhaps there will be some fragmentation due to a ruleset extending an existing rule in the parent domain), but it looks like they are still spreaded out a bit for some reason, and if the allocations are sparse during domain creation time, this situation won't fix itself and could slow down all access checks. (Maybe on a single core system, with nothing else touching the kmem cache when the domain is being merged, they would be allocated together?)
I'm not sure about the performance of binary search vs rbtrees. I can see that the improved locality should help, but going by my benchmark of the hashtable domains, I'm not sure how much of a difference it make, and whether it would be worth the added complexity. I could try implementing this flat array + binary search approach and run the existing benchmarks on it tho (but as of writing this I haven't).
Quoted 5 lines
struct landlock_domain_index { union landlock_key key; u32 shift; // value to add to this array's index to jump to the set // of mapped landlock_layerCan you clarify the comment? Is it the index into the layers array, or are you suggesting adding the index of the current
landlock_domain_indexwith this shift value, and use that to index into the layers array?While it's probably an unlikely situation, what if there are more than 2^29 rules, each having 16 layers? I think that would overflow this u32 even if it is an offset, and this is allowed as
LANDLOCK_MAX_NUM_RULESis currently defined asU32_MAX.(Unrelated to this patch, but I think once we have the supervise feature in, I can see a (probably badly implemented) supervisor getting close to this limit if the sandboxed application creates / delete and recreates lots of temporary files under /tmp)
Quoted 2 lines
u32 num_layers; }; // 128-bit (or 96-bit) allignedI guess this has to be 128 bits aligned if we have an u32
num_layers. Because we allow 16 layers, if we make it an u16, it would actually need to be the number of layers minus 1. However maybe that is overcomplicating it and we should just make this 128 bits aligned (otherwise we have to deal with unaligned reads of thelandlock_key->objecttoo).Quoted 15 lines
// Theoretical
landlock_domainstruct landlock_domain { struct landlock_hierarchy *hierarchy; union { // See landlock_ruleset's union }; u32 num_fs; // number of FS indexes u32 num_net; // number of net indexes struct access_masks access_masks[]; struct landlock_domain_index fs_indexes[num_fs]; struct landlock_layer fs_layers[sum of FS rules' layers]; struct landlock_domain_index net_indexes[num_net]; struct landlock_layer net_layers[sum of net rules' layers]; };(Unrelated to this patch specifically, but I would probably like to use this domain struct for the mutable part of a domain as well later. In that case the hierarchy pointer would be unused.)
Quoted 12 lines
// Real
landlock_domainstruct landlock_domain { struct landlock_hierarchy *hierarchy; union { // See landlock_ruleset's union }; u32 num_fs; // number of FS indexes u32 num_net; // number of net indexes u32 rules[]; // underlying typed arrays accessed via helpers };Quoted 6 lines
The
landlock_domainis a contiguously allocated memory buffer containing variable-size arrays improving locality. Another advantage is that we would not get any potential allocation errors once the buffer is allocated which should simplify domain creation. Also, we avoid the union inlandlock_rule(patch 5) and only uselandlock_ruleinlandlock_ruleset.I think doing this definitely has positives especially in terms of memory, however I'm worried about the complexity here. Since we will have to do various index calculation and use it to access variable-sized arrays, I'm somewhat afraid that any mistake could end up either leaking kernel pointers, or at worst, memory corruption.
We should probably have a
len_rules, and check (WARN_ON_ONCEand if fails returns-EINVAL) that any computed indices lies within range before accessing it.Quoted 5 lines
An alternative approach would be to use a hash table instead of the array (extending
landlock_domain_indexwith a pointer/shift to the next collision) but still with this big buffer. I'm not sure the perf impact would be noticable but it might be worse a try.I can give that a try too and measure benchmarks.
BTW, going by the direction this discussion is going, I assume we're on board with a separate
landlock_domain, and don't plan to change how unmergedlandlock_rulesetare stored (at least for now)? If so I can probably start work on quiet rules, removing access bits / rules by intersect, etc as discussed in
https://github.com/landlock-lsm/linux/issues/44#issuecomment-2876500918Quoted 8 lines
Quoted 8 lines
Signed-off-by Tingmao Wang <[email protected]>--- security/landlock/hash.h | 117 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 117 insertions(+) create mode 100644 security/landlock/hash.hQuoted 11 lines
security/landlock/hash.h line 3
Quoted 9 lines
security/landlock/hash.h new file +3
-0@@ -0,0 +1,117 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +/* +* Landlock - Domain hashtable mainpulation typo
ack
Quoted 17 lines
Quoted 5 lines
security/landlock/hash.h new file +4
-0+* +* Copyright © 2025 Tingmao Wang <[email protected]> +*/ +security/landlock/hash.h line 17
Quoted 10 lines
security/landlock/hash.h new file +10
-0+#ifndef _SECURITY_LANDLOCK_HASH_H +#define _SECURITY_LANDLOCK_HASH_H + +#include <linux/slab.h> +#include <linux/hash.h> + +#include "ruleset.h" + +struct landlock_hashtable { + struct hlist_head *hlist;A simple linked-list would be enough.
I'm not sure I understand what you meant by a "simple linked-list" - do you mean like an array of
landlock_rules, each itself is part of a linked list of all the rules that hashed to the same key?Anyway, since we identified a flat array approach (whether we hash or binary search), I'm gonna try that instead.
Quoted 25 lines
Quoted 11 lines
security/landlock/hash.h new file +10
-0+ +/** +* @hash_bits: Number of bits in this hash index (i.e. hlist has +* 2^this many elements). +*/ +int hash_bits; +}; + +#define landlock_hash_for_each (rule, ht, i) \ + for (i = 0; i < (1ULL << (ht)->hash_bits); i += 1) \security/landlock/hash.h line 37
Quoted 10 lines
security/landlock/hash.h new file +10
-0+ hlist_for_each_entry(rule, &(ht)->hlist[i], hlist) + +#define landlock_hash_for_each_safe (rule, tmp, ht, i) \ + for (i = 0; i < (1ULL << (ht)->hash_bits); i += 1) \ + hlist_for_each_entry_safe(rule, tmp, &(ht)->hlist[i], hlist) + +static inline int landlock_hash_init (const size_t expected_num_entries, +struct landlock_hashtable *out_ht) +{ +size_t table_sz =1 ;Please use variables with full name when they are not too big:
table_sizein this case.Quoted 8 lines
security/landlock/hash.h line 41
Quoted 4 lines
security/landlock/hash.h new file +4
-0+int hash_bits =0 ; + +if (likely (expected_num_entries >0 )) { + table_sz =roundup_pow_of_two (expected_num_entries);With
roundup_pow_of_two()we'll get a few collisions but a big table. What would be the impact of usingroundup_pow_of_two()instead to have a compact hash table (with more collisions)?I assume you meant using
rounddown_pow_of_two- I can give it a quick test too with the flat array approach.Quoted 81 lines
Quoted 81 lines
security/landlock/hash.h new file +76
-1+ hash_bits =fls_long (table_sz -1 ); + } + +/* +* We allocate a table even if expected_num_entries == 0 to avoid +* unnecessary branching in lookup code +*/ + + out_ht->hash_bits = hash_bits; + out_ht->hlist =kcalloc (table_sz,sizeof (struct hlist_head ), +GFP_KERNEL_ACCOUNT ); +if (!out_ht->hlist) { +return -ENOMEM ; + } + +return 0 ; +} + +static inline void landlock_hash_free (struct landlock_hashtable *ht, +const enum landlock_key_type key_type) +{ +struct landlock_rule *rule; +struct hlist_node *tmp; +size_t i; + +if (key_type ==LANDLOCK_KEY_INODE ) +might_sleep (); + +if (!ht->hlist) +return ; + +landlock_hash_for_each_safe (rule, tmp, ht, i) + { +free_rule (rule, key_type); + } +kfree (ht->hlist); + ht->hlist =NULL ; +} + +static inline u32 landlock_hash_key (const union landlock_key key, +const int hash_bits) +{ +return hash_ptr ((void *)key.data, hash_bits); +} + +static inline struct landlock_rule * +landlock_hash_find (const struct landlock_hashtable *const ht, +const union landlock_key key) +{ +struct hlist_head *head; +struct landlock_rule *rule; + + head = &ht->hlist[landlock_hash_key (key, ht->hash_bits)]; + +hlist_for_each_entry (rule, head, hlist) { +if (rule->key.data == key.data) +return rule; + } + +return NULL ; +} + +/** +* @landlock_hash_count - Return number of entries in the hashtable. +*/ +static inline size_t landlock_hash_count (const struct landlock_hashtable *ht) +{ +size_t num_entries =0 ; +struct landlock_rule *rule; +size_t i; +landlock_hash_for_each (rule, ht, i) + { + num_entries +=1 ; + } +return num_entries; +} --2.49.0
Mickaël Salaün
maintainerRe: [RFC PATCH 02/10] landlock/hash: define (dynamic, non-resizable) hash table helpers
In reply to Tingmao WangQuoted 72 lines · Tingmao Wang
Quoted 20 lines · Mickaël Salaün
Quoted 11 lines · Tingmao Wang
While there is already
include/linux/hash.h, it relies on the static size of the array as the size of the hash table, and thus is inconvenient to use for this case where we dynamically compute how many slots we need.There is also the relativistic hash tables in
rhashtable.hwhich supports dynamic resizes etc, but is more complicated and might be slower to access?However, on second thought, I'm wondering if we should just use hash tables for both domain and a not-yet-merged ruleset anyway (which saves us from having a union in
landlock_rule). If we do that then we should indeed just use rhashtable.Thinking more about it, the important properties are that we can have a lot of domains/tables (i.e. sandboxed processes) with a few entries/rules (e.g. ~30 rules seems reasonable for now). We should then try to minimize the total amount of memory while still making access checks quick. As you noted, the cost of hashing should also not be ignored.
Quoted 2 lines
Instead of a hash table per domain, what about flat arrays with binary search? Here is a proposal:
I think this makes sense in terms of reducing memory footprint.
My understanding of the Slab allocator is that objects are allocated in power-of-two sized caches, so with a single-layer, 44 bytes
landlock_rule, we will still use 64 bytes. Putting them in an array, especially with your proposed structure, would reduce this.I also checked how the allocations actually are distributed in the current implementation. Dumping the addresses of the
landlock_ruleobjects allocated and sorting them by the address, we see:# env LL_FS_RO=/usr:/bin:/etc:/lib:/sys:/dev:/home/mao/.config:/home/mao/linux LL_FS_RW=/tmp:/proc:/dev/tty:/dev/null:/dev/zero \Quoted 1 line
./sandboxer bash
Executing the sandboxed command...
bash:/home/mao/.bashrc: Permission deniedmao@linux-devbox-vm:~$ cat /proc/dump_landlock_domain Ruleset: ffff9268489451e0 Inode tree: ffff92684e767100: inode 5374060 in fs ext4 ffff92684e767380 (+640 (rule itself was 44 bytes)): inode 2883604 in fs ext4 ffff92684e767440 (+192 (rule itself was 44 bytes)): inode 2883992 in fs ext4 ffff92684e767580 (+320 (rule itself was 44 bytes)): inode 11 in fs devtmpfs ffff92684e767740 (+448 (rule itself was 44 bytes)): inode 5377989 in fs ext4 ffff92684e767800 (+192 (rule itself was 44 bytes)): inode 1 in fs devtmpfs ffff92684e7678c0 (+192 (rule itself was 44 bytes)): inode 1 in fs tmpfs ffff92684e767980 (+192 (rule itself was 44 bytes)): inode 6 in fs devtmpfs ffff92684e767b40 (+448 (rule itself was 44 bytes)): inode 4 in fs devtmpfs ffff92684e767bc0 (+128 (rule itself was 44 bytes)): inode 2883585 in fs ext4 ffff92684e767c40 (+128 (rule itself was 44 bytes)): inode 1 in fs sysfs ffff92684e767cc0 (+128 (rule itself was 44 bytes)): inode 6815745 in fs ext4 ffff92684e767f80 (+704 (rule itself was 44 bytes)): inode 1 in fs procNote: source code for this at
https://github.com/micromaomao/linux-dev/commit/16c318fcbc64c23b87ca67836771f710d0d0ccf1(this is a typical result out of several repeat runs) (KASLR etc disabled,
no_hash_pointers)Because all landlock rules are copied at domain creation time, I previously thought that they are likely to be allocated close together (perhaps there will be some fragmentation due to a ruleset extending an existing rule in the parent domain), but it looks like they are still spreaded out a bit for some reason, and if the allocations are sparse during domain creation time, this situation won't fix itself and could slow down all access checks. (Maybe on a single core system, with nothing else touching the kmem cache when the domain is being merged, they would be allocated together?)
Quoted 6 lines
I'm not sure about the performance of binary search vs rbtrees. I can see that the improved locality should help, but going by my benchmark of the hashtable domains, I'm not sure how much of a difference it make, and whether it would be worth the added complexity. I could try implementing this flat array + binary search approach and run the existing benchmarks on it tho (but as of writing this I haven't).
Yes, I think binary search would be enough, taking into account the cache.
Quoted 10 lines
Quoted 6 lines
struct landlock_domain_index { union landlock_key key; u32 shift; // value to add to this array's index to jump to the set // of mapped landlock_layerCan you clarify the comment? Is it the index into the layers array, or are you suggesting adding the index of the current
landlock_domain_indexwith this shift value, and use that to index into the layers array?
I was suggesting the later but thinking out loud this doesn't help much, we can just use an "u32 rule_index" (instead of the "shift") to jump to the layers array.
Quoted 5 lines
While it's probably an unlikely situation, what if there are more than 2^29 rules, each having 16 layers? I think that would overflow this u32 even if it is an offset, and this is allowed as
LANDLOCK_MAX_NUM_RULESis currently defined asU32_MAX.
Correct. We can either use u64 or reduce the maximum number of rules. I think LANDLOCK_MAX_NUM_RULES set to U16_MAX would be much more than the worse practical case. Even if one buggy policy tries to add one rule per network port, that will be OK. We could even reasonably test this limit. We'll need to backport this change but I'm OK with that.
Quoted 9 lines
(Unrelated to this patch, but I think once we have the supervise feature in, I can see a (probably badly implemented) supervisor getting close to this limit if the sandboxed application creates / delete and recreates lots of temporary files under /tmp)
Quoted 2 lines
u32 num_layers; }; // 128-bit (or 96-bit) alligned
Quoted 6 lines
I guess this has to be 128 bits aligned if we have an u32
num_layers. Because we allow 16 layers, if we make it an u16, it would actually need to be the number of layers minus 1. However maybe that is overcomplicating it and we should just make this 128 bits aligned (otherwise we have to deal with unaligned reads of thelandlock_key->objecttoo).
I was thinking about the size on a 32-bit architecture.
Quoted 17 lines
Quoted 16 lines
// Theoretical
landlock_domainstruct landlock_domain { struct landlock_hierarchy *hierarchy; union { // See landlock_ruleset's union }; u32 num_fs; // number of FS indexes u32 num_net; // number of net indexes struct access_masks access_masks[]; struct landlock_domain_index fs_indexes[num_fs]; struct landlock_layer fs_layers[sum of FS rules' layers]; struct landlock_domain_index net_indexes[num_net]; struct landlock_layer net_layers[sum of net rules' layers]; };
Quoted 3 lines
(Unrelated to this patch specifically, but I would probably like to use this domain struct for the mutable part of a domain as well later. In that case the hierarchy pointer would be unused.)
OK, you can create two types.
Quoted 20 lines
Quoted 13 lines
// Real
landlock_domainstruct landlock_domain { struct landlock_hierarchy *hierarchy; union { // See landlock_ruleset's union }; u32 num_fs; // number of FS indexes u32 num_net; // number of net indexes u32 rules[]; // underlying typed arrays accessed via helpers };Quoted 6 lines
The
landlock_domainis a contiguously allocated memory buffer containing variable-size arrays improving locality. Another advantage is that we would not get any potential allocation errors once the buffer is allocated which should simplify domain creation. Also, we avoid the union inlandlock_rule(patch 5) and only uselandlock_ruleinlandlock_ruleset.
Quoted 5 lines
I think doing this definitely has positives especially in terms of memory, however I'm worried about the complexity here. Since we will have to do various index calculation and use it to access variable-sized arrays, I'm somewhat afraid that any mistake could end up either leaking kernel pointers, or at worst, memory corruption.
Yes, packing this is a bit complex. We could allocate a buffer and use pointers+lenght but I'm not sure it will be safer. Any other suggestion?
Quoted 4 lines
We should probably have a
len_rules, and check (WARN_ON_ONCEand if fails returns-EINVAL) that any computed indices lies within range before accessing it.
Definitely.
Quoted 8 lines
Quoted 6 lines
An alternative approach would be to use a hash table instead of the array (extending
landlock_domain_indexwith a pointer/shift to the next collision) but still with this big buffer. I'm not sure the perf impact would be noticable but it might be worse a try.I can give that a try too and measure benchmarks.
What worries me about hash tables is the size they can take. With Landlock, we can have a lot of domains, and we should try to keep them as small as possible. I don't think a small hash table with a lot of potential collisions would perform better than a binary search. I suggest you ignore this hash table unless you want to compare performance (with a hash table + extra the same size as a flat array).
Quoted 4 lines
BTW, going by the direction this discussion is going, I assume we're on board with a separate
landlock_domain, and don't plan to change how unmergedlandlock_rulesetare stored (at least for now)?
Yes, let's focus on the domain data structure. The ruleset's rbtree works fine and is not a performance issue.
Quoted 4 lines
If so I can
probably start work on quiet rules, removing access bits / rules by intersect, etc as discussed in
https://github.com/landlock-lsm/linux/issues/44#issuecomment-2876500918
Yes please.
Quoted 41 lines
Quoted 9 lines
Quoted 9 lines
Signed-off-by Tingmao Wang <[email protected]>--- security/landlock/hash.h | 117 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 117 insertions(+) create mode 100644 security/landlock/hash.hQuoted 11 lines
security/landlock/hash.h line 3
Quoted 9 lines
security/landlock/hash.h new file +3
-0@@ -0,0 +1,117 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +/* +* Landlock - Domain hashtable mainpulation typo
ack
Quoted 17 lines
Quoted 5 lines
security/landlock/hash.h new file +4
-0+* +* Copyright © 2025 Tingmao Wang <[email protected]> +*/ +security/landlock/hash.h line 17
Quoted 10 lines
security/landlock/hash.h new file +10
-0+#ifndef _SECURITY_LANDLOCK_HASH_H +#define _SECURITY_LANDLOCK_HASH_H + +#include <linux/slab.h> +#include <linux/hash.h> + +#include "ruleset.h" + +struct landlock_hashtable { + struct hlist_head *hlist;A simple linked-list would be enough.
Quoted 3 lines
I'm not sure I understand what you meant by a "simple linked-list" - do you mean like an array of
landlock_rules, each itself is part of a linked list of all the rules that hashed to the same key?
hlist_node has two pointers but we would only need one here.
Quoted 3 lines
Anyway, since we identified a flat array approach (whether we hash or binary search), I'm gonna try that instead.
Right
Quoted 35 lines
Quoted 26 lines
Quoted 12 lines
security/landlock/hash.h new file +10
-0+ +/** +* @hash_bits: Number of bits in this hash index (i.e. hlist has +* 2^this many elements). +*/ +int hash_bits; +}; + +#define landlock_hash_for_each (rule, ht, i) \ + for (i = 0; i < (1ULL << (ht)->hash_bits); i += 1) \security/landlock/hash.h line 37
Quoted 10 lines
security/landlock/hash.h new file +10
-0+ hlist_for_each_entry(rule, &(ht)->hlist[i], hlist) + +#define landlock_hash_for_each_safe (rule, tmp, ht, i) \ + for (i = 0; i < (1ULL << (ht)->hash_bits); i += 1) \ + hlist_for_each_entry_safe(rule, tmp, &(ht)->hlist[i], hlist) + +static inline int landlock_hash_init (const size_t expected_num_entries, +struct landlock_hashtable *out_ht) +{ +size_t table_sz =1 ;Please use variables with full name when they are not too big:
table_sizein this case.Quoted 8 lines
security/landlock/hash.h line 41
Quoted 4 lines
security/landlock/hash.h new file +4
-0+int hash_bits =0 ; + +if (likely (expected_num_entries >0 )) { + table_sz =roundup_pow_of_two (expected_num_entries);With
roundup_pow_of_two()we'll get a few collisions but a big table. What would be the impact of usingroundup_pow_of_two()instead to have a compact hash table (with more collisions)?
Quoted 2 lines
I assume you meant using
rounddown_pow_of_two- I can give it a quick test too with the flat array approach.
Yes, I meant rounddown_pow_of_two, but I don't think it will outperform the (small) flat array.
RFC PATCH 3/10 landlock/hash: Use linear search for small tables
In reply to Tingmao WangThe cost of hashing is too significant when there's only a small number of entries. For that we might as well just walk the hlist. The optimal threshold can be determined imperically which I will do later.
--- security/landlock/hash.h | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-)
security/landlock/hash.h +11 -1
@@ -13,6 +13,8 @@#include "ruleset.h" +#define LANDLOCK_HASH_LINEAR_THRESHOLD 4 +struct landlock_hashtable {struct hlist_head *hlist;
@@ -37,7 +39,11 @@ static inline int landlock_hash_init(const size_t expected_num_entries,size_t table_sz =1 ;int hash_bits =0 ; -if (likely (expected_num_entries >0 )) { +/* +* For small tables, we just have one slot, essentially making lookups +* a linear search. Doing a hash for small tables is not worth it. +*/ +if (expected_num_entries >LANDLOCK_HASH_LINEAR_THRESHOLD ) { table_sz =roundup_pow_of_two (expected_num_entries); hash_bits =fls_long (table_sz -1 ); }
@@ -81,6 +87,10 @@ static inline void landlock_hash_free(struct landlock_hashtable *ht,static inline u32 landlock_hash_key (const union landlock_key key,const int hash_bits) { +if (hash_bits ==0 ) { +return 0 ; + } +return hash_ptr ((void *)key.data, hash_bits); }
Signature · 1 line
2.49.0
RFC PATCH 4/10 landlock/ruleset: Rename and extract create_rule
In reply to Tingmao WangTo be used in domain.h in a later patch
--- security/landlock/ruleset.c | 80 +------------------------------------ security/landlock/ruleset.h | 77 +++++++++++++++++++++++++++++++++++ 2 files changed, 79 insertions(+), 78 deletions(-)
security/landlock/ruleset.c +2 -78
@@ -77,71 +77,6 @@ landlock_create_ruleset(const access_mask_t fs_access_mask,return new_ruleset; } -static void build_check_rule (void ) -{ -const struct landlock_rule rule = { - .num_layers = ~0 , - }; - -BUILD_BUG_ON (rule.num_layers <LANDLOCK_MAX_NUM_LAYERS ); -} - -static bool is_object_pointer (const enum landlock_key_type key_type) -{ -switch (key_type) { -case LANDLOCK_KEY_INODE : -return true; - -#if IS_ENABLED (CONFIG_INET ) -case LANDLOCK_KEY_NET_PORT : -return false; -#endif /* IS_ENABLED(CONFIG_INET) */ - -default : -WARN_ON_ONCE (1 ); -return false; - } -} - -static struct landlock_rule * -create_rule (const struct landlock_id id, -const struct landlock_layer (*const layers)[],const u32 num_layers, -const struct landlock_layer *const new_layer) -{ -struct landlock_rule *new_rule; -u32 new_num_layers; - -build_check_rule (); -if (new_layer) { -/* Should already be checked by landlock_merge_ruleset(). */ -if (WARN_ON_ONCE (num_layers >=LANDLOCK_MAX_NUM_LAYERS )) -return ERR_PTR (-E2BIG ); - new_num_layers = num_layers +1 ; - }else { - new_num_layers = num_layers; - } - new_rule =kzalloc (struct_size (new_rule, layers, new_num_layers), -GFP_KERNEL_ACCOUNT ); -if (!new_rule) -return ERR_PTR (-ENOMEM ); -RB_CLEAR_NODE (&new_rule->node); -if (is_object_pointer (id.type)) { -/* This should have been caught by insert_rule(). */ -WARN_ON_ONCE (!id.key.object); -landlock_get_object (id.key.object); - } - - new_rule->key = id.key; - new_rule->num_layers = new_num_layers; -/* Copies the original layer stack. */ -memcpy (new_rule->layers, layers, -flex_array_size (new_rule, layers, num_layers)); -if (new_layer) -/* Adds a copy of @new_layer on the layer stack. */ - new_rule->layers[new_rule->num_layers -1 ] = *new_layer; -return new_rule; -} -static struct rb_root *get_root (struct landlock_ruleset *const ruleset,const enum landlock_key_type key_type) {
@@ -160,17 +95,6 @@ static struct rb_root *get_root(struct landlock_ruleset *const ruleset, } } -static void free_rule (struct landlock_rule *const rule, -const enum landlock_key_type key_type) -{ -might_sleep (); -if (!rule) -return ; -if (is_object_pointer (key_type)) -landlock_put_object (rule->key.object); -kfree (rule); -} -static void build_check_ruleset (void ) {const struct landlock_ruleset ruleset = {
@@ -261,7 +185,7 @@ static int insert_rule(struct landlock_ruleset *const ruleset,* Intersects access rights when it is a merge between a * ruleset and a domain. */ - new_rule =create_rule (id, &this->layers, this->num_layers, + new_rule =landlock_create_rule (id, &this->layers, this->num_layers, &(*layers)[0 ]);if (IS_ERR (new_rule))return PTR_ERR (new_rule);
@@ -274,7 +198,7 @@ static int insert_rule(struct landlock_ruleset *const ruleset,build_check_ruleset ();if (ruleset->num_rules >=LANDLOCK_MAX_NUM_RULES )return -E2BIG ; - new_rule =create_rule (id, layers, num_layers,NULL ); + new_rule =landlock_create_rule (id, layers, num_layers,NULL );if (IS_ERR (new_rule))return PTR_ERR (new_rule);rb_link_node (&new_rule->node, parent_node, walker_node);
security/landlock/ruleset.h +77 -0
83 lines not on this page · raw message
Signature · 1 line
2.49.0
RFC PATCH 5/10 Add hlist_node member to struct landlock_rule
In reply to Tingmao WangThis is to prepare for the new domain. Since a rule can only be in either a ruleset (rbtree based) or a landlock_domain (hashtable based), we can make the node/hlist member of a union. For now let create_rule initialize is as before.
(Alternatively, if we use hashtable for both cases, then we save 8 bytes per each rule, but then we will need some kind of resizable hashtable)
(Maybe we should use the relativistic hash tables after all?)
--- security/landlock/ruleset.h | 20 ++++++++++++++++---- 1 file changed, 16 insertions(+), 4 deletions(-)
security/landlock/ruleset.h +16 -4
@@ -87,10 +87,16 @@ struct landlock_id {* struct landlock_rule - Access rights tied to an object */ struct landlock_rule { -/** -* @node: Node in the ruleset's red-black tree. -*/ -struct rb_node node; +union { +/** +* @node: Node in the ruleset's red-black tree. +*/ +struct rb_node node; +/** +* @hlist: Node in the domain's hash table. +*/ +struct hlist_node hlist; + };/** * @key: A union to identify either a kernel object (e.g. an inode) or * a raw data value (e.g. a network socket port). This is used as a key
@@ -248,7 +254,13 @@ landlock_create_rule(const struct landlock_id id, GFP_KERNEL_ACCOUNT);if (!new_rule)return ERR_PTR (-ENOMEM ); + +/* +* We assume the rule will be in a rbtree for now - in the +* landlock_domain case caller can init the hlist afterward +*/ RB_CLEAR_NODE (&new_rule->node); +if (is_object_pointer (id.type)) {/* This should have been caught by insert_rule(). */ WARN_ON_ONCE (!id.key.object);
Signature · 1 line
2.49.0
RFC PATCH 6/10 landlock/domain: Define landlock_domain
In reply to Tingmao WangThis will eventually take the role of landlock_ruleset (and maybe landlock_hirearchy?), but for now it is just the inode rules hashtable.
--- security/landlock/domain.c | 36 ++++++++++++++++++++++++++++++++++++ security/landlock/domain.h | 27 +++++++++++++++++++++++++++ 2 files changed, 63 insertions(+)
security/landlock/domain.c +36 -0
@@ -5,6 +5,7 @@* Copyright © 2016-2020 Mickaël Salaün <[email protected]> * Copyright © 2018-2020 ANSSI * Copyright © 2024-2025 Microsoft Corporation +* Copyright © 2025 Tingmao Wang <[email protected]> */ #include <kunit/test.h>
@@ -24,6 +25,41 @@#include "domain.h" #include "id.h" +struct landlock_domain *landlock_alloc_domain (size_t num_inode_entries, +u16 num_layers) +{ +struct landlock_domain *new_domain = +kzalloc (sizeof (struct landlock_domain ),GFP_KERNEL_ACCOUNT ); + +if (!new_domain) +return NULL ; +refcount_set (&new_domain->usage,1 ); + new_domain->num_layers = num_layers; +if (landlock_hash_init (num_inode_entries, &new_domain->inode_table)) { +kfree (new_domain); +return NULL ; + } + +return new_domain; +} + +static void free_domain (struct landlock_domain *const domain) +{ +might_sleep (); + +landlock_hash_free (&domain->inode_table,LANDLOCK_KEY_INODE ); +kfree (domain); +} + +void landlock_put_domain (struct landlock_domain *const domain) +{ +might_sleep (); + +if (domain &&refcount_dec_and_test (&domain->usage)) { +free_domain (domain); + } +} +#ifdef CONFIG_AUDIT /**
security/landlock/domain.h +27 -0
@@ -5,6 +5,7 @@* Copyright © 2016-2020 Mickaël Salaün <[email protected]> * Copyright © 2018-2020 ANSSI * Copyright © 2024-2025 Microsoft Corporation +* Copyright © 2025 Tingmao Wang <[email protected]> */ #ifndef _SECURITY_LANDLOCK_DOMAIN_H
@@ -20,6 +21,32 @@#include "access.h" #include "audit.h" +#include "hash.h" + +struct landlock_domain { +struct landlock_hashtable inode_table; + +/** +* @usage: Reference count for this struct. +*/ +refcount_t usage; + +/** +* @num_layers: Number of layers in this domain. +*/ +u16 num_layers; +}; + +struct landlock_domain *landlock_alloc_domain (size_t num_inode_entries, +u16 num_layers); + +static inline void landlock_get_domain (struct landlock_domain *const domain) +{ +if (domain) +refcount_inc (&domain->usage); +} + +void landlock_put_domain (struct landlock_domain *const domain);enum landlock_log_status {LANDLOCK_LOG_PENDING =0 ,
Signature · 1 line
2.49.0
RFC PATCH 7/10 landlock: Add the new domain to landlock_cred_security
In reply to Tingmao WangWe add a new field domain2 that will eventually replace the old struct landlock_ruleset domain. Also add get/put to appropriate places where this struct is copied/freed.
In a future patch, this domain2 will be renamed to domain.
--- security/landlock/cred.c | 8 ++++---- security/landlock/cred.h | 1 + security/landlock/domain.c | 17 +++++++++++++++++ security/landlock/domain.h | 32 +++++++++++++++++++++++--------- security/landlock/fs.c | 5 +++++ 5 files changed, 50 insertions(+), 13 deletions(-)
security/landlock/cred.c +4 -4
@@ -13,6 +13,7 @@#include "common.h" #include "cred.h" +#include "domain.h" #include "ruleset.h" #include "setup.h"
@@ -24,6 +25,7 @@ static void hook_cred_transfer(struct cred *const new,if (old_llcred->domain) {landlock_get_ruleset (old_llcred->domain); +landlock_get_domain (old_llcred->domain2); *landlock_cred (new) = *old_llcred; } }
@@ -37,10 +39,8 @@ static int hook_cred_prepare(struct cred *const new,static void hook_cred_free (struct cred *const cred) { -struct landlock_ruleset *const dom =landlock_cred (cred)->domain; - -if (dom) -landlock_put_ruleset_deferred (dom); +landlock_put_ruleset_deferred (landlock_cred (cred)->domain); +landlock_put_domain_deferred (landlock_cred (cred)->domain2); }#ifdef CONFIG_AUDIT
security/landlock/cred.h +1 -0
@@ -32,6 +32,7 @@ struct landlock_cred_security {* @domain: Immutable ruleset enforced on a task. */ struct landlock_ruleset *domain; +struct landlock_domain *domain2;#ifdef CONFIG_AUDIT /**
security/landlock/domain.c +17 -0
@@ -60,6 +60,23 @@ void landlock_put_domain(struct landlock_domain *const domain) } } +static void free_domain_work (struct work_struct *const work) +{ +struct landlock_domain *domain; + + domain = container_of(work, struct landlock_domain, work_free); +free_domain (domain); +} + +/* Only called by hook_cred_free(). */ +void landlock_put_domain_deferred (struct landlock_domain *const domain) +{ +if (domain &&refcount_dec_and_test (&domain->usage)) { +INIT_WORK (&domain->work_free, free_domain_work); +schedule_work (&domain->work_free); + } +} +#ifdef CONFIG_AUDIT /**
security/landlock/domain.h +23 -9
@@ -18,6 +18,7 @@#include <linux/refcount.h> #include <linux/sched.h> #include <linux/slab.h> +#include <linux/workqueue.h> #include "access.h" #include "audit.h"
@@ -26,15 +27,26 @@struct landlock_domain {struct landlock_hashtable inode_table; -/** -* @usage: Reference count for this struct. -*/ -refcount_t usage; - -/** -* @num_layers: Number of layers in this domain. -*/ -u16 num_layers; +union { +/** +* @work_free: Enables to free a ruleset within a lockless +* section. This is only used by +* landlock_put_domain_deferred() when @usage reaches zero. +*/ +struct work_struct work_free; + +struct { +/** +* @usage: Reference count for this struct. +*/ +refcount_t usage; + +/** +* @num_layers: Number of layers in this domain. +*/ +u16 num_layers; + }; + }; }; struct landlock_domain *landlock_alloc_domain(size_t num_inode_entries,
@@ -48,6 +60,8 @@ static inline void landlock_get_domain(struct landlock_domain *const domain)void landlock_put_domain (struct landlock_domain *const domain); +void landlock_put_domain_deferred (struct landlock_domain *const domain); +enum landlock_log_status {LANDLOCK_LOG_PENDING =0 ,LANDLOCK_LOG_RECORDED ,
security/landlock/fs.c +5 -0
@@ -1844,6 +1844,7 @@ static bool control_current_fowner(struct fown_struct *const fown)static void hook_file_set_fowner (struct file *file) {struct landlock_ruleset *prev_dom; +struct landlock_domain *prev_dom2;struct landlock_cred_security fown_subject = {};size_t fown_layer =0 ;
@@ -1856,11 +1857,13 @@ static void hook_file_set_fowner(struct file *file) current_cred(), signal_scope, &fown_layer);if (new_subject) {landlock_get_ruleset (new_subject->domain); +landlock_get_domain (new_subject->domain2); fown_subject = *new_subject; } } prev_dom =landlock_file (file)->fown_subject.domain; + prev_dom2 =landlock_file (file)->fown_subject.domain2;landlock_file (file)->fown_subject = fown_subject;#ifdef CONFIG_AUDIT landlock_file (file)->fown_layer = fown_layer;
@@ -1868,11 +1871,13 @@ static void hook_file_set_fowner(struct file *file)/* May be called in an RCU read-side critical section. */ landlock_put_ruleset_deferred (prev_dom); +landlock_put_domain_deferred (prev_dom2); }static void hook_file_free_security (struct file *file) {landlock_put_ruleset_deferred (landlock_file (file)->fown_subject.domain); +landlock_put_domain_deferred (landlock_file (file)->fown_subject.domain2); }static struct security_hook_list landlock_hooks[]__ro_after_init = {
Signature · 1 line
2.49.0
RFC PATCH 8/10 landlock: Construct the inode hashtable in the new landlock_domain
In reply to Tingmao WangSince we can't get rid of the old landlock_merge_ruleset yet, we call our new thing landlock_merge_ruleset2.
--- security/landlock/domain.c | 87 +++++++++++++++++++++++++++++ security/landlock/domain.h | 4 ++ security/landlock/hash.h | 105 +++++++++++++++++++++++++++++++++++ security/landlock/ruleset.h | 2 +- security/landlock/syscalls.c | 9 +++ 5 files changed, 206 insertions(+), 1 deletion(-)
security/landlock/domain.c +87 -0
@@ -77,6 +77,93 @@ void landlock_put_domain_deferred(struct landlock_domain *const domain) } } +/** +* @curr_table may be NULL. +*/ +static int merge_domain_table (const enum landlock_key_type key_type, +const struct landlock_hashtable *const curr_table, +struct landlock_hashtable *const new_table, +struct landlock_layer new_layer, +const struct rb_root *ruleset_rb_root) +{ +int err; +struct landlock_rule *iter, *iter2; + +if (curr_table) { + err =landlock_hash_clone (new_table, curr_table, key_type); +if (err) { +return err; + } + } + +/* Merge in new rules */ +rbtree_postorder_for_each_entry_safe (iter, iter2, ruleset_rb_root, + node) { +WARN_ON_ONCE (iter->layers[0 ].level !=0 ); +WARN_ON_ONCE (iter->num_layers !=1 ); + new_layer.access = iter->layers[0 ].access; + + err =landlock_hash_upsert (new_table, iter->key, key_type, + new_layer); +if (err) { +return err; + } + } + +return 0 ; +} + +/** +* @landlock_merge_ruleset2 - Merge a ruleset with a (possibly NULL) +* domain, and return a new merged domain. +*/ +struct landlock_domain * +landlock_merge_ruleset2 (const struct landlock_domain *curr_domain, +const struct landlock_ruleset *next_ruleset) +{ +size_t num_inodes =0 ; +int err; +struct landlock_domain *new_domain; +struct landlock_layer new_layer = { + .level =1 , + }; +struct landlock_rule *iter, *iter2; + +if (WARN_ON_ONCE (!next_ruleset)) { +return ERR_PTR (-EINVAL ); + } + +if (curr_domain) { + new_layer.level = curr_domain->num_layers +1 ; + num_inodes =landlock_hash_count (&curr_domain->inode_table); + } + +/* Find new expected size of inode table */ +rbtree_postorder_for_each_entry_safe (iter, iter2, + &next_ruleset->root_inode, node) { +if (!curr_domain || +landlock_hash_find (&curr_domain->inode_table, iter->key) == +NULL ) { + num_inodes +=1 ; + } + } + + new_domain =landlock_alloc_domain (num_inodes, new_layer.level); +if (!new_domain) +return ERR_PTR (-ENOMEM ); + + err =merge_domain_table (LANDLOCK_KEY_INODE , + curr_domain ? &curr_domain->inode_table :NULL , + &new_domain->inode_table, new_layer, + &next_ruleset->root_inode); +if (err) { +landlock_put_domain (new_domain); +return ERR_PTR (err); + } + +return new_domain; +} +#ifdef CONFIG_AUDIT /**
security/landlock/domain.h +4 -0
@@ -62,6 +62,10 @@ void landlock_put_domain(struct landlock_domain *const domain);void landlock_put_domain_deferred (struct landlock_domain *const domain); +struct landlock_domain * +landlock_merge_ruleset2 (const struct landlock_domain *curr_domain, +const struct landlock_ruleset *new_ruleset); +enum landlock_log_status {LANDLOCK_LOG_PENDING =0 ,LANDLOCK_LOG_RECORDED ,
security/landlock/hash.h +105 -0
114 lines not on this page · raw message
security/landlock/ruleset.h +1 -1
@@ -27,7 +27,7 @@ struct landlock_hierarchy;*/ struct landlock_layer {/** -* @level: Position of this layer in the layer stack. +* @level: Position of this layer in the layer stack. Starts from 1. */ u16 level;/**
security/landlock/syscalls.c +9 -0
@@ -483,6 +483,7 @@ SYSCALL_DEFINE2(landlock_restrict_self, const int, ruleset_fd, const __u32, *ruleset __free(landlock_put_ruleset) = NULL;struct cred *new_cred;struct landlock_cred_security *new_llcred; +struct landlock_domain *new_domain2;bool __maybe_unused log_same_exec, log_new_exec, log_subdomains, prev_log_subdomains;
@@ -551,6 +552,12 @@ SYSCALL_DEFINE2(landlock_restrict_self, const int, ruleset_fd, const __u32,abort_creds (new_cred);return PTR_ERR (new_dom); } + new_domain2 =landlock_merge_ruleset2 (new_llcred->domain2, ruleset); +if (IS_ERR (new_domain2)) { +landlock_put_ruleset (new_dom); +abort_creds (new_cred); +return PTR_ERR (new_domain2); + }#ifdef CONFIG_AUDIT new_dom->hierarchy->log_same_exec = log_same_exec;
@@ -588,6 +595,8 @@ SYSCALL_DEFINE2(landlock_restrict_self, const int, ruleset_fd, const __u32,/* Replaces the old (prepared) domain. */ landlock_put_ruleset (new_llcred->domain); new_llcred->domain = new_dom; +landlock_put_domain (new_llcred->domain2); + new_llcred->domain2 = new_domain2;#ifdef CONFIG_AUDIT new_llcred->domain_exec |=BIT (new_dom->num_layers -1 );
Signature · 1 line
2.49.0
Mickaël Salaün
maintainerRe: [RFC PATCH 08/10] landlock: Construct the inode hashtable in the new landlock_domain
Quoted 18 lines · Tingmao Wang
Since we can't get rid of the old
landlock_merge_rulesetyet, we call our new thinglandlock_merge_ruleset2.Signed-off-by Tingmao Wang <[email protected]>--- security/landlock/domain.c | 87 +++++++++++++++++++++++++++++ security/landlock/domain.h | 4 ++ security/landlock/hash.h | 105 +++++++++++++++++++++++++++++++++++ security/landlock/ruleset.h | 2 +- security/landlock/syscalls.c | 9 +++ 5 files changed, 206 insertions(+), 1 deletion(-)security/landlock/ruleset.h +0
-0
security/landlock/ruleset.h struct landlock_hierarchy; · line 30
Quoted 5 lines
security/landlock/ruleset.h +1
-1@@ -27,7 +27,7 @@ struct landlock_hierarchy;*/ struct landlock_layer {/** -* @level: Position of this layer in the layer stack. +* @level: Position of this layer in the layer stack. Starts from 1.
Feel free to send a standalone patch with improved doc, I'll merge it directly.
Quoted 3 lines
security/landlock/ruleset.h +0
-0*/ u16 level;/**
Re: [RFC PATCH 08/10] landlock: Construct the inode hashtable in the new landlock_domain
Quoted 14 lines · Mickaël Salaün
Quoted 11 lines · Tingmao Wang
Since we can't get rid of the old
landlock_merge_rulesetyet, we call our new thinglandlock_merge_ruleset2.Signed-off-by Tingmao Wang <[email protected]>--- security/landlock/domain.c | 87 +++++++++++++++++++++++++++++ security/landlock/domain.h | 4 ++ security/landlock/hash.h | 105 +++++++++++++++++++++++++++++++++++ security/landlock/ruleset.h | 2 +- security/landlock/syscalls.c | 9 +++ 5 files changed, 206 insertions(+), 1 deletion(-)
Quoted 13 lines
security/landlock/ruleset.h struct landlock_hierarchy; · line 30
Quoted 10 lines
security/landlock/ruleset.h +1
-1@@ -27,7 +27,7 @@ struct landlock_hierarchy;*/ struct landlock_layer {/** -* @level: Position of this layer in the layer stack. +* @level: Position of this layer in the layer stack. Starts from 1. Feel free to send a standalone patch with improved doc, I'll merge it directly.
(I've done this and will remove this change from this series.)
Quoted 4 lines
Quoted 4 lines
security/landlock/ruleset.h +0
-0*/ u16 level;/**
RFC PATCH 9/10 landlock/fs: Use the new hashtable-based domain to find inode rules
In reply to Tingmao Wang--- security/landlock/fs.c | 55 ++++++++++++++++++++++-------------------- 1 file changed, 29 insertions(+), 26 deletions(-)
security/landlock/fs.c +29 -26
@@ -7,6 +7,7 @@* Copyright © 2021-2025 Microsoft Corporation * Copyright © 2022 Günther Noack <[email protected]> * Copyright © 2023-2024 Google LLC +* Copyright © 2025 Tingmao Wang <[email protected]> */ #include <asm/ioctls.h>
@@ -361,14 +362,12 @@ int landlock_append_fs_rule(struct landlock_ruleset *const ruleset,* Returns NULL if no rule is found or if @dentry is negative. */ static const struct landlock_rule * -find_rule (const struct landlock_ruleset *const domain, +find_rule (const struct landlock_domain *const domain,const struct dentry *const dentry) {const struct landlock_rule *rule;const struct inode *inode; -struct landlock_id id = { - .type =LANDLOCK_KEY_INODE , - }; +union landlock_key key;/* Ignores nonexistent leafs. */ if (d_is_negative (dentry))
@@ -376,8 +375,8 @@ find_rule(const struct landlock_ruleset *const domain, inode =d_backing_inode (dentry);rcu_read_lock (); - id.key.object =rcu_dereference (landlock_inode (inode)->object); - rule =landlock_find_rule (domain, id); + key.object =rcu_dereference (landlock_inode (inode)->object); + rule =landlock_hash_find (&domain->inode_table, key);rcu_read_unlock ();return rule; }
@@ -753,6 +752,7 @@ static void test_is_eacces_with_write(struct kunit *const test)*/ static bool is_access_to_paths_allowed( const struct landlock_ruleset *const domain, + const struct landlock_domain *const domain2, const struct path *const path, const access_mask_t access_request_parent1, layer_mask_t (*const layer_masks_parent1)[LANDLOCK_NUM_ACCESS_FS],
@@ -831,7 +831,7 @@ static bool is_access_to_paths_allowed(if (unlikely (dentry_child1)) { landlock_unmask_layers( - find_rule(domain, dentry_child1), + find_rule(domain2, dentry_child1), landlock_init_layer_masks( domain, LANDLOCK_MASK_ACCESS_FS, &_layer_masks_child1, LANDLOCK_KEY_INODE),
@@ -841,7 +841,7 @@ static bool is_access_to_paths_allowed( }if (unlikely (dentry_child2)) { landlock_unmask_layers( - find_rule(domain, dentry_child2), + find_rule(domain2, dentry_child2), landlock_init_layer_masks( domain, LANDLOCK_MASK_ACCESS_FS, &_layer_masks_child2, LANDLOCK_KEY_INODE),
@@ -900,7 +900,7 @@ static bool is_access_to_paths_allowed(break ; } - rule =find_rule (domain, walker_path.dentry); + rule =find_rule (domain2, walker_path.dentry); allowed_parent1 = allowed_parent1 || landlock_unmask_layers( rule, access_masked_parent1,
@@ -1012,9 +1012,9 @@ static int current_check_access_path(const struct path *const path, access_request =landlock_init_layer_masks (subject->domain, access_request, &layer_masks,LANDLOCK_KEY_INODE ); -if (is_access_to_paths_allowed (subject->domain, path, access_request, - &layer_masks, &request,NULL ,0 ,NULL , -NULL ,NULL )) +if (is_access_to_paths_allowed (subject->domain, subject->domain2, path, + access_request, &layer_masks, &request, +NULL ,0 ,NULL ,NULL ,NULL ))return 0 ;landlock_log_denial (subject, &request);
@@ -1077,6 +1077,7 @@ static access_mask_t maybe_remove(const struct dentry *const dentry)*/ static bool collect_domain_accesses (const struct landlock_ruleset *const domain, +const struct landlock_domain *const domain2,const struct dentry *const mnt_root,struct dentry *dir,layer_mask_t (*const layer_masks_dom)[LANDLOCK_NUM_ACCESS_FS ]) {
@@ -1097,7 +1098,7 @@ static bool collect_domain_accesses(struct dentry *parent_dentry;/* Gets all layers allowing all domain accesses. */ -if (landlock_unmask_layers (find_rule (domain, dir), access_dom, +if (landlock_unmask_layers (find_rule (domain2, dir), access_dom, layer_masks_dom,ARRAY_SIZE (*layer_masks_dom))) {/*
@@ -1218,10 +1219,10 @@ static int current_check_refer_path(struct dentry *const old_dentry, subject->domain, access_request_parent1 | access_request_parent2, &layer_masks_parent1, LANDLOCK_KEY_INODE); -if (is_access_to_paths_allowed (subject->domain, new_dir, - access_request_parent1, - &layer_masks_parent1, &request1, -NULL ,0 ,NULL ,NULL ,NULL )) +if (is_access_to_paths_allowed ( + subject->domain, subject->domain2, new_dir, + access_request_parent1, &layer_masks_parent1, + &request1,NULL ,0 ,NULL ,NULL ,NULL ))return 0 ;landlock_log_denial (subject, &request1);
@@ -1245,11 +1246,13 @@ static int current_check_refer_path(struct dentry *const old_dentry, old_dentry->d_parent;/* new_dir->dentry is equal to new_dentry->d_parent */ - allow_parent1 =collect_domain_accesses (subject->domain, mnt_dir.dentry, - old_parent, + allow_parent1 =collect_domain_accesses (subject->domain, + subject->domain2, + mnt_dir.dentry, old_parent, &layer_masks_parent1); - allow_parent2 =collect_domain_accesses (subject->domain, mnt_dir.dentry, - new_dir->dentry, + allow_parent2 =collect_domain_accesses (subject->domain, + subject->domain2, + mnt_dir.dentry, new_dir->dentry, &layer_masks_parent2);if (allow_parent1 && allow_parent2)
@@ -1262,10 +1265,10 @@ static int current_check_refer_path(struct dentry *const old_dentry,* destination parent access rights. */ if (is_access_to_paths_allowed ( - subject->domain, &mnt_dir, access_request_parent1, - &layer_masks_parent1, &request1, old_dentry, - access_request_parent2, &layer_masks_parent2, &request2, - exchange ? new_dentry :NULL )) + subject->domain, subject->domain2, &mnt_dir, + access_request_parent1, &layer_masks_parent1, &request1, + old_dentry, access_request_parent2, &layer_masks_parent2, + &request2, exchange ? new_dentry :NULL ))return 0 ;if (request1.access) {
@@ -1689,7 +1692,7 @@ static int hook_file_open(struct file *const file) full_access_request = open_access_request | optional_access; if (is_access_to_paths_allowed( - subject->domain, &file->f_path, + subject->domain, subject->domain2, &file->f_path, landlock_init_layer_masks(subject->domain, full_access_request, &layer_masks, LANDLOCK_KEY_INODE),
Signature · 1 line
2.49.0
RFC PATCH 10/10 landlock: Debug print inode hashtable in landlock_merge_ruleset2
In reply to Tingmao Wang--- security/landlock/domain.c | 5 +++ security/landlock/hash.h | 62 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 67 insertions(+)
security/landlock/domain.c +5 -0
@@ -161,6 +161,11 @@ landlock_merge_ruleset2(const struct landlock_domain *curr_domain,return ERR_PTR (err); } +#ifdef DEBUG +pr_debug ("landlock_merge_ruleset2: inode hash table:\n" ); +landlock_hash_debug_print (&new_domain->inode_table,LANDLOCK_KEY_INODE ); +#endif /* DEBUG */ +return new_domain; }
security/landlock/hash.h +62 -0
66 lines not on this page · raw message
Signature · 1 line
2.49.0
Mickaël Salaün
maintainerQuoted 11 lines · Tingmao Wang
Hi Mickaël,
This is a set of (incomplete) patches for the "domain hashtable" work. While this is still a WIP, I'm sending it now as per our discussion. You can take a look and see if the approach needs correcting / if we want to go ahead with using hashtable.
Currently only implemented for fs access.
This set of changes is also available on the landlock-hashmap branch of
https://github.com/micromaomao/linux-dev.git
Thanks for these patches and the related benchmarks!
Quoted 27 lines
struct
landlock_domain
----------------------One of the major thing I'm not sure about in this patch is the fact that I've decided to create a standalone
struct landlock_domain, instead of re-usinglandlock_ruleset. My original hope was that it might help make the code a bit clearer - structlandlock_rulesetwould just be for unmerged rulesets (and it can use rbtree if we still wants to), and we can use this new type for domains (and add new fields and locks to it that wouldn't be on a ruleset, for the mutable domains / supervisor work).I also wanted to split the logic of dealing with rules in a merged domain (hence needing to copy multiple layers etc) out of
create_ruleandinsert_rule, and simply these functions (especiallyinsert_rule) by letting them just deal with unmerged rulesets (so only one layer) - the logic for merged domains would be different anyway since it's no longer a rbtree walk (but something likelandlock_hash_upsertin patch 8 instead).However, looking back at it, I'm not sure if creating this
landlock_domainwas actually a good idea. Going down this route eventually I will just have to move all the domain-related logic from using ruleset to usinglandlock_domain. If we decide to use hashtable for unmerged rulesets too (not done in this patch, and need more thoughts on how that would work), then separating this out is even less value.
Quoted 3 lines
Regardless, the relevant code in this patch should still be easily portable to just extend
landlock_rulesetwith hashtables, so I'm happy to do that instead in the next version.
I think a dedicated struct landlock_domain has value: clearer API, smaller domain's size, optimizations. In the current implementation of the hash table, the domain's size increases in most cases because of the table's size. We also still have scattered rules and at least two pointer dereferencing (if no hash collision): landlock_hashtable.hlist, and hlist_node.first. This could be avoided with a compact flat structure, using a hash table or just an array with sorted keys. See a new proposal in my reply to patch 2.
Quoted 88 lines
Hashtable implementation
------------------------Since I couldn't find a suitable existing wrapper for runtime-sized (but fixed after creation) hashtables, this patch uses a newly hand-rolled implementation. It's not very complex so this might be fine, but there is also rhashtable which would be especially suitable if we want to use hash table for unmerged rulesets too. See patch 2 message for details.
Testing
-------selftests/landlock/fs_tests all passes under KASAN, lockdep etc. Other tests showed no obvious issues, but base and net fails due to missing config (no MPTCP, no
CONFIG_ASYMMETRIC_KEY_TYPEi.e. keyctl)I ran benchmark with before/after using two workloads, on the same machine and setup:
1.
run_microbenchwith different depth and number of extra rules using code in https://github.com/landlock-lsm/landlock-test-tools/pull/172. A more "typical" workload I put together quickly, calling git status and the like repeatedly:
https://github.com/torvalds/linux/commit/f1865ce970af97ac3b6f4edf580529b8cdc66371On the "typical" workload, which has 2 layers and ~15 rules, we have:
Comparing: orig hashtable (% change)
landlock_overhead:(this is the % of time spent in landlock hook in the open syscall) avg = 34 33 (-2.9%) median = 34 33 (-2.9%)landlock_hook: avg = 837 775 (-7.4%) (unit: ns) median = 813 748 (-8.0%) (unit: ns)open_syscall: avg = 2429 2324 (-4.3%) (unit: ns) median = 2370 2265 (-4.4%) (unit: ns)Using the microbench script, for an extreme case on a path beneath 28 directories and with 10000 rules:
Comparing: orig hashtable (% change)
landlock_overhead: avg = 27 24 (-11.1%) median = 29 25 (-13.8%) landlock_hook: avg = 1913 1577 (-17.6%) median = 1884 1544 (-18.0%) open_syscall: avg = 6775 6259 (-7.6%) median = 6666 6115 (-8.3%)The full results can be found at
https://fileshare.maowtm.org/landlock/20250521/index.htmlTingmao Wang (10):
landlock: Add some debug output
landlock/hash: define (dynamic, non-resizable) hash table helpers landlock/hash: Use linear search for small tables landlock/ruleset: Rename and extractcreate_rule
Addhlist_nodemember to structlandlock_rulelandlock/domain: Definelandlock_domain
landlock: Add the new domain tolandlock_cred_security
landlock: Construct the inode hashtable in the newlandlock_domainlandlock/fs: Use the new hashtable-based domain to find inode rules
landlock: Debug print inode hashtable inlandlock_merge_ruleset2security/landlock/cred.c | 8 +- security/landlock/cred.h | 1 + security/landlock/domain.c | 145 +++++++++++++++++ security/landlock/domain.h | 45 ++++++ security/landlock/fs.c | 107 +++++++++---- security/landlock/fs.h | 1 + security/landlock/hash.h | 294 +++++++++++++++++++++++++++++++++++ security/landlock/ruleset.c | 80 +--------- security/landlock/ruleset.h | 99 +++++++++++- security/landlock/syscalls.c | 35 +++++ 10 files changed, 702 insertions(+), 113 deletions(-) create mode 100644 security/landlock/hash.hbase-commit:
3039ed432745f8fdf5cbb43fdc60b2e1aad624c1--
2.49.0