landlock: Refactor layer masks

fs_bench benchmarks the performance of Landlock's path walk by exercising it in a scenario that amplifies Landlock's overhead:

* Create a large number of nested directories
* Enforce a Landlock policy in which a rule is associated with each of these subdirectories
* Benchmark openat() applied to the deepest directory, forcing Landlock to walk the entire path.

Signed-off-by Günther Noack <[email protected]>

---
 tools/testing/selftests/landlock/.gitignore |   1 +
 tools/testing/selftests/landlock/Makefile   |   1 +
 tools/testing/selftests/landlock/fs_bench.c | 214 ++++++++++++++++++++
 3 files changed, 216 insertions(+)
 create mode 100644 tools/testing/selftests/landlock/fs_bench.c

tools/testing/selftests/landlock/.gitignore +1 -0

index a820329cae0d..1974e17a2611 100644
@@ -1,4 +1,5 @@
 /*_test
+/fs_bench
 /sandbox-and-launch
 /true
 /wait-pipe

tools/testing/selftests/landlock/Makefile +30 -0

index 044b83bde16e..fc43225d319a 100644
 
+int main(int argc, char *argv[])
+{
+	bool use_landlock = true;
+	size_t num_iterations = 100000;
+	size_t num_subdirs = 10000;
+	int c, curr, fd;
+	struct tms start_time, end_time;
+
+	setbuf(stdout, NULL);
+	while ((c = getopt(argc, argv, "hLd:n:")) != -1) {
+		switch (c) {
+		case 'h':
+			usage(argv[0]);
+			return EXIT_SUCCESS;
+		case 'L':
+			use_landlock = false;
+			break;
+		case 'd':
+			num_subdirs = atoi(optarg);
+			break;
+		case 'n':
+			num_iterations = atoi(optarg);
+			break;
+		default:
+			usage(argv[0]);
+			return EXIT_FAILURE;
+		}
+	}
+
+	printf("*** Benchmark ***\n");

tools/testing/selftests/landlock/Makefile +24 -0

+		if (use_landlock) {
+			if (fd == 0)
+				errx(1, "openat succeeded, expected EACCES");
+			if (errno != EACCES)
+				err(1, "openat expected EACCES, but got");
+		}
+		if (fd != -1)
+			close(fd);
+	}
+
+	if (times(&end_time) == -1)
+		err(1, "times");
+
+	printf("*** Benchmark concluded ***\n");
+	printf("System: %ld clocks\n",
+	       end_time.tms_stime - start_time.tms_stime);
+	printf("User  : %ld clocks\n",
+	       end_time.tms_utime - start_time.tms_utime);
+	printf("Clocks per second: %ld\n", CLOCKS_PER_SEC);
+
+	close(curr);
+
+	remove_recursively(num_subdirs);
+}

Signature · 1 line

2.52.0

The layer masks data structure tracks the requested but unfulfilled access rights during an operation's security check. It stores one bit for each combination of access right and layer index. If the bit is set, that access right is not granted (yet) in the given layer and we have to traverse the path further upwards to grant it.

Previously, the layer masks were stored as arrays mapping from access right indices to layer_mask_t. The layer_mask_t value then indicates all layers in which the given access right is still (tentatively) denied.

This patch introduces struct layer_access_masks instead: This struct contains an array with the access_mask_t of each (tentatively) denied access right in that layer.

The hypothesis of this patch is that this simplifies the code enough so that the resulting code will run faster:

* We can use bitwise operations in multiple places where we previously looped over bits individually with macros. (Should require less branch speculation and lends itself to better loop unrolling.)

* Code is ~75 lines smaller.

Other noteworthy changes:

* In no_more_access(), call a new helper function may_refer(), which only solves the asymmetric case. Previously, the code interleaved the checks for the two symmetric cases in RENAME_EXCHANGE. It feels that the code is clearer when renames without RENAME_EXCHANGE are more obviously the normal case.

Tradeoffs:

This change improves performance, at a slight size increase to the layer masks data structure.

This fixes the size of the data structure at 32 bytes for all types of access rights. (64, once we introduce a 17th filesystem access right).

For filesystem access rights, at the moment, the data structure has the same size as before, but once we introduce the 17th filesystem access right, it will double in size (from 32 to 64 bytes), as access_mask_t grows from 16 to 32 bit. [1]

Link https://lore.kernel.org/all/[email protected]/ [1] open here

Signed-off-by Günther Noack <[email protected]>

---
 security/landlock/access.h  |  15 +-
 security/landlock/audit.c   |  81 +++------
 security/landlock/audit.h   |   3 +-
 security/landlock/domain.c  |  45 ++---
 security/landlock/domain.h  |   4 +-
 security/landlock/fs.c      | 348 ++++++++++++++++--------------------
 security/landlock/net.c     |   9 +-
 security/landlock/ruleset.c |  89 ++++-----
 security/landlock/ruleset.h |  21 ++-
 9 files changed, 274 insertions(+), 341 deletions(-)

security/landlock/access.h +8 -7

index bab403470a6c..f0a9afeb4a2a 100644
@@ -61,14 +61,15 @@ union access_masks_all {
 static_assert(sizeof(typeof_member(union access_masks_all, masks)) ==
 	      sizeof(typeof_member(union access_masks_all, all)));
 
-typedef u16 layer_mask_t;
-
-/* Makes sure all layers can be checked. */
-static_assert(BITS_PER_TYPE(layer_mask_t) >= LANDLOCK_MAX_NUM_LAYERS);
-
 /*
- * Tracks domains responsible of a denied access.  This is required to avoid
- * storing in each object the full layer_masks[] required by update_request().
+ * Tracks domains responsible of a denied access.  This avoids storing in each
+ * object the full matrix of per-layer unfulfilled access rights, which is
+ * required by update_request().
+ *
+ * Each nibble represents the layer index of the newest layer which denied a
+ * certain access right.  For file system access rights, the upper four bits are
+ * the index of the layer which denies LANDLOCK_ACCESS_FS_IOCTL_DEV and the
+ * lower nibble represents LANDLOCK_ACCESS_FS_TRUNCATE.
  */
 typedef u8 deny_masks_t;
 

security/landlock/domain.c +0 -0

index a647b68e8d06..d2a4354feeb4 100644

security/landlock/domain.c +0 -0

 #include <kunit/test.h>
 #include <linux/bitops.h>
 #include <linux/bits.h>

security/landlock/domain.h +1 -0

index 621f054c9a2b..227066d667f7 100644
@@ -10,6 +10,7 @@
 #ifndef _SECURITY_LANDLOCK_DOMAIN_H
 #define _SECURITY_LANDLOCK_DOMAIN_H
 
+#include "ruleset.h"
 #include <linux/limits.h>
 #include <linux/mm.h>
 #include <linux/path.h>

security/landlock/ruleset.h +17 -4

index 1a78cba662b2..1ceb5fd674c9 100644
@@ -301,15 +301,28 @@ landlock_get_scope_mask(const struct landlock_ruleset *const ruleset,
 	return ruleset->access_masks[layer_level].scope;
 }
 
+/**
+ * struct layer_access_masks - A boolean matrix of layers and access rights
+ *
+ * This has a bit for each combination of layer numbers and access rights.
+ * During access checks, it is used to represent the access rights for each
+ * layer which still need to be fulfilled.  When all bits are 0, the access
+ * request is considered to be fulfilled.
+ */
+struct layer_access_masks {
+	/**
+	 * @access: The unfulfilled access rights for each layer.
+	 */
+	access_mask_t access[LANDLOCK_MAX_NUM_LAYERS];
+};
+
 bool landlock_unmask_layers(const struct landlock_rule *const rule,
-			    const access_mask_t access_request,
-			    layer_mask_t (*const layer_masks)[],
-			    const size_t masks_array_size);
+			    struct layer_access_masks *masks);
 
 access_mask_t
 landlock_init_layer_masks(const struct landlock_ruleset *const domain,
 			  const access_mask_t access_request,
-			  layer_mask_t (*const layer_masks)[],
+			  struct layer_access_masks *masks,
 			  const enum landlock_key_type key_type);
 
 #endif /* _SECURITY_LANDLOCK_RULESET_H */

Signature · 1 line

2.52.0

[...]

security/landlock/audit.c +0 -0

@@ -406,12 +375,12 @@ void landlock_log_denial(const struct landlock_cred_security *const subject,
 	if (missing) {
 		/* Gets the nearest domain that denies the request. */
 		if (request->layer_masks) {

Hello!

This patch set "transposes" the layer masks matrix, which was previously modeled as a access-max-sized array of layer masks, and changes it to be a layer-max-sized array of access masks instead. (It is a pure refactoring, there are no user-visible changes.)

This unlocks a few code simplifications and in multiple places it removes the need for loops and branches that deal with individual bits. Instead, the changed data structure now lends itself for more bitwise operations. The underlying hypothesis for me was that by using more bitwise operations and fewer branches, we would get an overall speedup even when the data structure size increases slightly in some cases.

Benchmark results with and without this patch set show that the hypothesis holds true. The benchmark I used exercises a "worst case" scenario that attempts to be bottlenecked on the affected code: It constructs a large number of nested directories, with one "path beneath" rule each and then tries to open the innermost directory many times. The benchmark is intentionally unrealistic to amplify the amount of time used for the path walk logic and forces Landlock to walk the full path (eventually failing the open syscall). (I'll send the benchmark program in a reply to this mail for full transparency.)

Measured with the benchmark program, the patch set results in a speedup of about -7%. The benchmark results are only approximate and have been produced in Qemu:

With the patch, the benchmark runs in 6007 clocks (measured with times(3)):

*** Benchmark ***
10000 dirs, 100000 iterations, with landlock
*** Benchmark concluded ***
System: 6007 clocks
User : 1 clocks
Clocks per second: 1000000

Without the patch, we get 6506 clocks, which is 8% more

*** Benchmark ***
10000 dirs, 100000 iterations, with landlock
*** Benchmark concluded ***
System: 6506 clocks
User : 1 clocks
Clocks per second: 1000000

The base revision used for benchmarking was commit b7ff7151e653 ("Merge tag 'hwmon-for-v6.19-final' of
git://git.kernel.org/pub/scm/linux/kernel/git/groeck/linux-staging").

In real-life scenarios, the speed improvement from this patch set will be less pronounced than in the artificial benchmark, as people do not usually stack directories that deeply and attach so many rules to them, and the EACCES error should also be the exception rather than the norm.

I am looking forward to your feedback.

---

Changes since previous versions:

V3: (This patch set)

* Benchmark:
* Document what it does (and doesn't) do
* Const, use wrappers.h, add copyright line
* Delete the directory hierarchy after the run
* Use different Landlock policy for benchmark so that deletion works
* access_mask_subset() helper:
* Docstring corrections suggested by Randy Dunlap (thanks!)

    https://lore.kernel.org/all/[email protected]/

* Change argument names to "subset" and "superset"
* Use it from one more place
* Various
* Do not use docstring commenting style for non-docstrings
* Use ssize_t for downwards iterations from N-1 to 0
* Slightly reword deny_mask documentation

V2:

https://lore.kernel.org/all/[email protected]/

* Remove the refactoring around the deny_mask_t type,
it is better to send that as a separate patch (mic review)
* Added the benchmark program to the selftests
* Fix unused variable report for "access_dom":
https://lore.kernel.org/all/[email protected]/
* Use size_t and ARRAY_SIZE to loop over the layers (mic review)
* Documentation
* Fixing up and adding back documentaiton (mic review)
* Documented landlock_unmask_layers()
* Fixed up kernel docs in a place where it was improperly updated (Spotted by Randy Dunlap
https://lore.kernel.org/all/[email protected]/)
* Minor
* Const, some newlines (mic review)

V1: (Initial version)

https://lore.kernel.org/all/[email protected]/

Günther Noack (3):
selftests/landlock: Add filesystem access benchmark
landlock: access_mask_subset() helper
landlock: transpose the layer masks data structure

 security/landlock/access.h                  |  22 +-
 security/landlock/audit.c                   |  81 ++---
 security/landlock/audit.h                   |   3 +-
 security/landlock/domain.c                  |  45 +--
 security/landlock/domain.h                  |   4 +-
 security/landlock/fs.c                      | 352 +++++++++-----------
 security/landlock/net.c                     |   9 +-
 security/landlock/ruleset.c                 |  89 ++---
 security/landlock/ruleset.h                 |  21 +-
 tools/testing/selftests/landlock/.gitignore |   1 +
 tools/testing/selftests/landlock/Makefile   |   1 +
 tools/testing/selftests/landlock/fs_bench.c | 214 ++++++++++++
 12 files changed, 499 insertions(+), 343 deletions(-)
 create mode 100644 tools/testing/selftests/landlock/fs_bench.c

Signature · 1 line

2.52.0