[PATCH v3 1/5] landlock: Implement LANDLOCK_ADD_RULE_NO_INHERIT

[Justin Suess]

This is the core part of the patch series I was unsure about.

Here when a rule tagged with LANDLOCK_ADD_RULE_NO_INHERIT is 
inserted, "blank" dentry rules (meaning rules with no access grants), 
are inserted along with the original rule on each parent of the 
original rule up to the root (but only for inodes without existing 
rules). These are then (by the mark_no_inherit_ancestors call) tagged 
with the has no inherit descendent marker (has_no_inherit_desc). This 
is used to provide the parent directory protections. 

The purpose of these blank rules is to ensure when we do a 
find_rule() on any of the LANDLOCK_ADD_RULE_NO_INHERIT tagged rule's 
parents, we will immediately know we have to disallow topology 
changes on that inode to enforce the parent directory protections 
described in the cover letter.

This lets us perform the check for these protections in O(log(n)) 
consistent with the red black tree's insertion time. The insertion 
penalty for this is O(depth * log(n)), but this is done only at 
ruleset creation time. That is somewhat more acceptable in my 
opinion. 

Additionally I suspect keeping all the rule tracking logic in one 
data structure helps with cache locality and decreases bugs from not 
keeping the rules in sync with a seperate structure. It also reduces 
the LOC and complexity somewhat. 

The previous v2 of this patch used a complex (and buggy I found after 
running the v3 test suite on it) xarray to track this. The check for 
parent directory protections was O(n) and insertion was O(n * depth). 

My questions for reviewers:

  * Is it acceptable in this case for landlock to automatically and 
silently insert rules that the user didn't explicity declare?

  * Should these protections instead be implemented in a seperate 
data structure?

  * Is the performance cost for the current  implementation 
acceptable? 

Normal landlock insertion and checking is O(log(n)). For rules with 
this tag, checking is still O(log(n)) but insertion is O(depth * 
log(n)). 

Kind Regards,

Justin Suess