permission check avoidance during lookup

To quote from patch 1:
<quote>
Vast majority of real-world lookups happen on directories which are traversable by anyone. Figuring out that this holds for a given inode can be done when instantiating it or changing permissions, avoiding the overhead during lookup. Stats below.

A simple microbench of stating /usr/include/linux/fs.h on ext4 in a loop on Sapphire Rapids (ops/s):

before: 3640352
after:  3797258 (+4%)

</quote>

During a kernel build about 90% of all lookups managed to skip permission checks in my setup, see the commit message for a breakdown.

WARNING: more testing is needed for correctness, but I'm largely happy with the state as is.

WARNING: I'm assuming the following bit is applied:

index 78ea864fa8cd..eaf776cd4175 100644
@@ -5518,6 +5518,10 @@ struct inode *__ext4_iget(struct super_block *sb, unsigned long ino,
                goto bad_inode;
        brelse(iloc.bh);
 
+       /* Initialize the "no ACL's" state for the simple cases */
+       if (!ext4_test_inode_state(inode, EXT4_STATE_XATTR) && !ei->i_file_acl)
+               cache_no_acl(inode);
+
        unlock_new_inode(inode);
        return inode;
 

Lack of the patch does not affect correctness, but it does make the patch ineffective for ext4. I did not include it in the posting as other people promised to sort it out.

Discussion is here with an ack from Jan:
https://lore.kernel.org/linux-fsdevel/kn44smk4dgaj5rqmtcfr7ruecixzrik6omur2l2opitn7lbvfm@rm4y24fcfzbz/T/#m30d6cea6be48e95c0d824e98a328fb90c7a5766d
and full thread:
https://lore.kernel.org/linux-fsdevel/kn44smk4dgaj5rqmtcfr7ruecixzrik6omur2l2opitn7lbvfm@rm4y24fcfzbz/T/#t

v2:
- productize
- btrfs and tmpfs support

Mateusz Guzik (4):
fs: speed up path lookup with cheaper MAY_EXEC checks
ext4: opt-in for IOP_MAY_FAST_EXEC
btrfs: opt-in for IOP_MAY_FAST_EXEC
tmpfs: opt-in for IOP_MAY_FAST_EXEC

 fs/attr.c          |  1 +
 fs/btrfs/inode.c   | 12 +++++-
 fs/ext4/inode.c    |  2 +
 fs/ext4/namei.c    |  1 +
 fs/namei.c         | 95 +++++++++++++++++++++++++++++++++++++++++++++-
 fs/posix_acl.c     |  1 +
 fs/xattr.c         |  1 +
 include/linux/fs.h | 21 +++++++---
 mm/shmem.c         |  9 +++++
 9 files changed, 134 insertions(+), 9 deletions(-)

2.48.1

Vast majority of real-world lookups happen on directories which are traversable by anyone. Figuring out that this holds for a given inode can be done when instantiating it or changing permissions, avoiding the overhead during lookup. Stats below.

A simple microbench of stating /usr/include/linux/fs.h on ext4 in a loop on Sapphire Rapids (ops/s):

before: 3640352
after:  3797258 (+4%)

Filesystems interested in utilizing the feature call inode_enable_fast_may_exec().

Explicit opt-in is necessary as some filesystems have custom inode permission check hooks which happen to be of no significance for MAY_EXEC. With an opt-in we know it can be safely ignored. Otherwise any inode with such a func present would need to be excluded.

inodes which end up skipping perm checks during kernel build grouped per-fs (0 means checks executed, 1 means skipped):

@[devpts]:
[0, 1) 2 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|

@[cgroup2]:
[0, 1) 68 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|

@[tmpfs]:

[0, 1)                84 |@@@@@@@@@                                           |
[1, ...)             451 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|

@[sysfs]:
[0, 1) 4532 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|

@[devtmpfs]:

[0, 1)              3609 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@   |
[1, ...)            3790 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|

@[proc]:
[0, 1) 19855 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|

@[ext4]:

[0, 1)            484292 |@@@                                                 |
[1, ...)         7775413 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|

@[btrfs]:

[0, 1)           5628821 |@@@@@                                               |
[1, ...)        52551904 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|

Note that devpts, cgroup2, sysfs and proc are not opting in and thus got no hits.

gathered with:
bpftrace -e 'kprobe:security_inode_permission { @[str(((struct inode *)arg0)->i_sb->s_type->name)] = lhist(((struct inode *)arg0)->i_opflags & 0x80 ? 1 : 0, 0, 1, 1); }'

---
 fs/attr.c          |  1 +
 fs/namei.c         | 95 +++++++++++++++++++++++++++++++++++++++++++++-
 fs/posix_acl.c     |  1 +
 fs/xattr.c         |  1 +
 include/linux/fs.h | 21 +++++++---
 5 files changed, 111 insertions(+), 8 deletions(-)

index 795f231d00e8..572363ff9c6d 100644
@@ -549,6 +549,7 @@ int notify_change(struct mnt_idmap *idmap, struct dentry *dentry,
 
 	if (!error) {
 		fsnotify_change(dentry, ia_valid);
+		inode_recalc_fast_may_exec(inode);
 		security_inode_post_setattr(idmap, dentry, ia_valid);
 	}
 

index 4050942ab52f..da27dd536058 100644
@@ -1135,6 +1135,7 @@ int vfs_set_acl(struct mnt_idmap *idmap, struct dentry *dentry,
 		error = -EIO;
 	if (!error) {
 		fsnotify_xattr(dentry);
+		inode_recalc_fast_may_exec(inode);
 		security_inode_post_set_acl(dentry, acl_name, kacl);
 	}
 

index 8851a5ef34f5..917946a7f367 100644
@@ -235,6 +235,7 @@ int __vfs_setxattr_noperm(struct mnt_idmap *idmap,
 				       size, flags);
 		if (!error) {
 			fsnotify_xattr(dentry);
+			inode_recalc_fast_may_exec(inode);
 			security_inode_post_setxattr(dentry, name, value,
 						     size, flags);
 		}

index 03e450dd5211..4f9962dfe2e6 100644
@@ -647,13 +647,14 @@ is_uncached_acl(struct posix_acl *acl)
 	return (long)acl & 1;
 }
 
-#define IOP_FASTPERM	0x0001
-#define IOP_LOOKUP	0x0002
-#define IOP_NOFOLLOW	0x0004
-#define IOP_XATTR	0x0008
+#define IOP_FASTPERM		0x0001
+#define IOP_LOOKUP		0x0002
+#define IOP_NOFOLLOW		0x0004
+#define IOP_XATTR		0x0008
 #define IOP_DEFAULT_READLINK	0x0010
-#define IOP_MGTIME	0x0020
-#define IOP_CACHED_LINK	0x0040
+#define IOP_MGTIME		0x0020
+#define IOP_CACHED_LINK		0x0040
+#define IOP_FAST_MAY_EXEC	0x0080
 
 /*
  * Inode state bits.  Protected by inode->i_lock

@@ -2128,6 +2129,7 @@ extern loff_t vfs_dedupe_file_range_one(struct file *src_file, loff_t src_pos,
 #define S_VERITY	(1 << 16) /* Verity file (using fs/verity/) */
 #define S_KERNEL_FILE	(1 << 17) /* File is in use by the kernel (eg. fs/cachefiles) */
 #define S_ANON_INODE	(1 << 19) /* Inode is an anonymous inode */
+#define S_CAN_FAST_MAY_EXEC (1 << 20) /* Inode is eligible for IOP_FAST_MAY_EXEC */
 
 /*
  * Note that nosuid etc flags are inode-specific: setting some file-system

@@ -2904,6 +2906,13 @@ static inline int inode_init_always(struct super_block *sb, struct inode *inode)
 	return inode_init_always_gfp(sb, inode, GFP_NOFS);
 }
 
+void inode_recalc_fast_may_exec(struct inode *);
+static inline void inode_enable_fast_may_exec(struct inode *inode)
+{
+	inode->i_flags |= S_CAN_FAST_MAY_EXEC;
+	inode_recalc_fast_may_exec(inode);
+}
+
 extern void inode_init_once(struct inode *);
 extern void address_space_init_once(struct address_space *mapping);
 extern struct inode * igrab(struct inode *);

2.48.1

---
 fs/ext4/inode.c | 2 ++
 fs/ext4/namei.c | 1 +
 2 files changed, 3 insertions(+)

index eaf776cd4175..7d5369f66686 100644
@@ -5522,6 +5522,8 @@ struct inode *__ext4_iget(struct super_block *sb, unsigned long ino,
 	if (!ext4_test_inode_state(inode, EXT4_STATE_XATTR) && !ei->i_file_acl)
 		cache_no_acl(inode);
 
+	inode_enable_fast_may_exec(inode);
+
 	unlock_new_inode(inode);
 	return inode;
 

index 2cd36f59c9e3..870bee252e54 100644
@@ -3038,6 +3038,7 @@ static struct dentry *ext4_mkdir(struct mnt_idmap *idmap, struct inode *dir,
 	err = ext4_mark_inode_dirty(handle, dir);
 	if (err)
 		goto out_clear_inode;
+	inode_enable_fast_may_exec(inode);
 	d_instantiate_new(dentry, inode);
 	ext4_fc_track_create(handle, dentry);
 	if (IS_DIRSYNC(dir))

2.48.1

---
 fs/btrfs/inode.c | 12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

index 42da39c1e5b5..42df687a0126 100644
@@ -5852,6 +5852,8 @@ struct btrfs_inode *btrfs_iget(u64 ino, struct btrfs_root *root)
 	if (ret)
 		return ERR_PTR(ret);
 
+	if (S_ISDIR(inode->vfs_inode.i_mode))
+		inode_enable_fast_may_exec(&inode->vfs_inode);
 	unlock_new_inode(&inode->vfs_inode);
 	return inode;
 }

@@ -6803,8 +6805,11 @@ static int btrfs_create_common(struct inode *dir, struct dentry *dentry,
 	}
 
 	ret = btrfs_create_new_inode(trans, &new_inode_args);
-	if (!ret)
+	if (!ret) {
+		if (S_ISDIR(inode->i_mode))
+			inode_enable_fast_may_exec(inode);
 		d_instantiate_new(dentry, inode);
+	}
 
 	btrfs_end_transaction(trans);
 	btrfs_btree_balance_dirty(fs_info);

@@ -9163,6 +9168,11 @@ int btrfs_prealloc_file_range_trans(struct inode *inode,
 					   min_size, actual_len, alloc_hint, trans);
 }
 
+/*
+ * NOTE: in case you are adding MAY_EXEC check for directories:
+ * inode_enable_fast_may_exec() is issued when inodes get instantiated, meaning
+ * calls to this place can be elided.
+ */
 static int btrfs_permission(struct mnt_idmap *idmap,
 			    struct inode *inode, int mask)
 {

2.48.1

---
 mm/shmem.c | 9 +++++++++
 1 file changed, 9 insertions(+)

index c819cecf1ed9..265456bc6bf0 100644
@@ -3106,6 +3106,15 @@ static struct inode *__shmem_get_inode(struct mnt_idmap *idmap,
 	}
 
 	lockdep_annotate_inode_mutex_key(inode);
+
+	if (S_ISDIR(mode)) {
+		WARN_ON_ONCE(inode_state_read_once(inode) & I_NEW);
+		/* satisfy an assert inside */
+		inode_state_set_raw(inode, I_NEW);
+		inode_enable_fast_may_exec(inode);
+		inode_state_clear_raw(inode, I_NEW);
+	}
+
 	return inode;
 }
 

2.48.1

Forgot to explain more in the commit message, so here it is right now:
how almost the entirety of inode_permission() can get elided for inodes which qualify for it.
inode_permission()

{
        retval = sb_permission(inode->i_sb, inode, mask);
        if (unlikely(retval))
                return retval;

sb_permission starts with a check for mask & MAY_WRITE. Since mask is MAY_EXEC, this does not need to execute.

        if (unlikely(mask & MAY_WRITE)) {

Same here.

        retval = do_inode_permission(idmap, inode, mask);
        if (unlikely(retval))
                return retval;

do_inode_permission starts with a check for IOP_FASTPERM. This is of no relevance as we are skipping the perm checks and the behavior is as if generic_permission() was always called.

Then generic_permission:

        ret = acl_permission_check(idmap, inode, mask);
        if (ret != -EACCES)
                return ret;

We don't have to check the error code as we expect the perm is granted.

acl_permission_check:

       if (!((mask & 7) * 0111 & ~mode)) {
                if (no_acl_inode(inode))
                        return 0;
                if (!IS_POSIXACL(inode))
                        return 0;
        }

We don't need this as we already pre-checked the perm is at least 0111 and there are no acls set.

back to inode_permission:

        retval = devcgroup_inode_permission(inode, mask);
        if (unlikely(retval))
                return retval;

This checks if we are dealing with a device. The IOP_FAST_MAY_EXEC is only legally set on directories, so it is an invariant we are not dealing with a device and don't need to check that.

Finally this:

        return security_inode_permission(inode, mask);

.. *does* execute in the new scheme.

However, LSM has notpatchable calls inside and only 2 users, normally not present on Ubuntu et al. Or to put it differently, this is a func call to a nop slide on most kernels and with some extra work can also get elided.