Skip to contentSkip to conversation

fs/namei.c: micro-optimize acl_permission_check

PATCH RESEND In review Rasmus Villemoes 3 participants 8 messages Jun 5, 2020 – Jun 8, 2020 VFS

lore
Share & tools
lore
#0 lore raw

PATCH RESEND 1/1 fs/namei.c: micro-optimize acl_permission_check

Just something like open(/usr/include/sys/stat.h) causes five calls of generic_permission -> acl_permission_check -> in_group_p; if the compiler first tried /usr/local/include/..., that would be a few more.

Altogether, on a bog-standard Ubuntu 20.04 install, a workload consisting of compiling lots of userspace programs (i.e., calling lots of short-lived programs that all need to get their shared libs mapped in, and the compilers poking around looking for system headers - lots of /usr/lib, /usr/bin, /usr/include/ accesses) puts in_group_p around 0.1% according to perf top. With an artificial load such as

while true ; do find /usr/ -print0 | xargs -0 stat > /dev/null ; done

that jumps to over 0.4%.

System-installed files are almost always 0755 (directories and binaries) or 0644, so in most cases, we can avoid the binary search and the cost of pulling the cred->groups array and in_group_p() .text into the cpu cache.

---
 fs/namei.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
fs/namei.c +6 -1
index d81f73ff1a8b..c6f0c6643db5 100644
@@ -303,7 +303,12 @@ static int acl_permission_check(struct inode *inode, int mask)
 				return error;
 		}
 
-		if (in_group_p(inode->i_gid))
+		/*
+		 * If the "group" and "other" permissions are the same,
+		 * there's no point calling in_group_p() to decide which
+		 * set to use.
+		 */
+		if ((((mode >> 3) ^ mode) & 7) && in_group_p(inode->i_gid))
 			mode >>= 3;
 	}
 
Signature · 1 line
2.23.0
#1 lore raw

fs/namei.c static int acl_permission_check(struct inode *inode, int mask) · line 312

Quoted 8 lines · Rasmus Villemoes
fs/namei.c +6 -0
+               /*
+                * If the "group" and "other" permissions are the same,
+                * there's no point calling in_group_p() to decide which
+                * set to use.
+                */
+               if ((((mode >> 3) ^ mode) & 7) && in_group_p(inode->i_gid))
                        mode >>= 3;

Ugh. Not only is this ugly, but it's not even the best optimization.

We don't care that group and other match exactly. We only care that they match in the low 3 bits of the "mask" bits.

So if we want this optimization - and it sounds worth it - I think we should do it right. But I also think it should be written more legibly.

And the "& 7" is the same "& (MAY_READ | MAY_WRITE | MAY_EXEC)" we do later.

In other words, if we do this, I'd like it to be done even more aggressively, but I'd also like the end result to be a lot more readable and have more comments about why we do that odd thing.

Something like this *UNTESTED* patch, perhaps?

I might have gotten something wrong, so this would need double-checking, but if it's right, I find it a _lot_ more easy to understand than making one expression that is pretty complicated and opaque.

Hmm?

Linus

#2 lore raw
Quoted 11 lines · Linus Torvalds

fs/namei.c static int acl_permission_check(struct inode *inode, int mask) · line 312

Quoted 8 lines · Rasmus Villemoes
fs/namei.c +6 -0
+               /*
+                * If the "group" and "other" permissions are the same,
+                * there's no point calling in_group_p() to decide which
+                * set to use.
+                */
+               if ((((mode >> 3) ^ mode) & 7) && in_group_p(inode->i_gid))
                        mode >>= 3;
Quoted 4 lines

Ugh. Not only is this ugly, but it's not even the best optimization.

We don't care that group and other match exactly. We only care that they match in the low 3 bits of the "mask" bits.

Yes, I did think about that, but I thought this was the more obviously correct approach, and that in practice one only sees the 0X44 and 0X55 cases.

Quoted 11 lines

So if we want this optimization - and it sounds worth it - I think we should do it right. But I also think it should be written more legibly.

And the "& 7" is the same "& (MAY_READ | MAY_WRITE | MAY_EXEC)" we do later.

In other words, if we do this, I'd like it to be done even more aggressively, but I'd also like the end result to be a lot more readable and have more comments about why we do that odd thing.

Something like this *UNTESTED* patch, perhaps?

That will kinda work, except you do that mask &= MAY_RWX before check_acl(), which cares about MAY_NOT_BLOCK and who knows what other bits.

Quoted 4 lines

I might have gotten something wrong, so this would need double-checking, but if it's right, I find it a _lot_ more easy to understand than making one expression that is pretty complicated and opaque.

Well, I thought this was readable enough with the added comment. There's already that magic constant 3 in the shifts, so the 7 seemed entirely sensible, though one could spell it 0007. Whatever.

Perhaps this? As a whole function, I think that's a bit easier for brain-storming. It's your patch, just with that rwx thing used instead of mask, except for the call to check_acl().

static int acl_permission_check(struct inode *inode, int mask)

{
	unsigned int mode = inode->i_mode;
	unsigned int rwx = mask & (MAY_READ | MAY_WRITE | MAY_EXEC);

	/* Are we the owner? If so, ACL's don't matter */
	if (likely(uid_eq(current_fsuid(), inode->i_uid))) {
		if ((rwx << 6) & ~mode)
			return -EACCES;
		return 0;
	}

	/* Do we have ACL's? */
	if (IS_POSIXACL(inode) && (mode & S_IRWXG)) {
		int error = check_acl(inode, mask);
		if (error != -EAGAIN)
			return error;
	}

	/*
	 * Are the group permissions different from
	 * the other permissions in the bits we care
	 * about? Need to check group ownership if so.
	 */
	if (rwx & (mode ^ (mode >> 3))) {
		if (in_group_p(inode->i_gid))
			mode >>= 3;
	}

	/* Bits in 'mode' clear that we require? */
	return (rwx & ~mode) ? -EACCES : 0;
}

Rasmus

#3 lore raw
Quoted 4 lines · Rasmus Villemoes

Yes, I did think about that, but I thought this was the more obviously correct approach, and that in practice one only sees the 0X44 and 0X55 cases.

I'm not sure about that - it probably depends on your umask.

Because I see a lot of -rw-rw-r--. in my home directory, and it looks like I have a umask of 0002.

That's just the Fedora default, I think. Looking at /etc/bashrc, it does

    if [ $UID -gt 199 ] && [ "`/usr/bin/id -gn`" = "`/usr/bin/id -un`" ]; then
       umask 002
    else
       umask 022
    fi

iow, if you have the same user-name and group name, then umask is 002 by default for regular users.

Honestly, I'm not sure why Fedora has that "each user has its own group" thing, but it's at least one common setup.

So I think that the system you are looking at just happens to have umask 0022, which is traditional when you have just a 'user' group.

Quoted 2 lines

That will kinda work, except you do that mask &= MAY_RWX before check_acl(), which cares about MAY_NOT_BLOCK and who knows what other bits.

Good catch.

Quoted 3 lines

Perhaps this? As a whole function, I think that's a bit easier for brain-storming. It's your patch, just with that rwx thing used instead of mask, except for the call to check_acl().

Looks fine to me. Once we have to have rwx/mask separate, I'm not sure it's worth having that early masking at all (didn't check what the register pressure is over that "check_acl()" call, but at least it is fairly easy to follow along.

Send me a patch with commit message etc, and I'll apply it.

Linus

#4 lore raw
Quoted 5 lines · Linus Torvalds
Quoted 3 lines

That will kinda work, except you do that mask &= MAY_RWX before check_acl(), which cares about MAY_NOT_BLOCK and who knows what other bits.

Good catch.

With the change to not clear the non-rwx bits in general, the owner case now wants to do the masking, and then the "shift left by 6" modification makes no sense since it only makes for a bigger constant (the only reason to do the shift-right was so that the bitwise not of the i_mode could be done in parallel with the shift, but with the masking that instruction scheduling optimization becomes kind of immaterial too). So I modified that patch to not bother, and add a comment about MAY_NOT_BLOCK.

And since I was looking at the MAY_NOT_BLOCK logic, it was not only not mentioned in comments, it also had some really confusing code around it.

The posix_acl_permission() looked like it tried to conserve that bit, which is completely wrong. It wasn't a bug only for the simple reason that the only two call-sites had either explicitly cleared the bit when calling, or had tested that the bit wasn't set in the first place.

So as a result, I wrote a second patch to clear that confusion up.

Rasmus, say the word and I'll mark you for authorship on the first one.

Comments? Can you find something else wrong here, or some other fixup to do?

Al, any reaction?

Linus

From 09cc0faef0766da8ff8e6a82cfc5c8c53a01d0a7 Mon Sep 17 00:00:00 2001
From: Linus Torvalds <[email protected]>
Date: Fri, 5 Jun 2020 13:40:45 -0700
Subject: [PATCH 1/2] vfs: do not do group lookup when not necessary

Rasmus Villemoes points out that the 'in_group_p()' tests can be a noticeable expense, and often completely unnecessary. A common situation is that the 'group' bits are the same as the 'other' bits wrt the permissions we want to test.

So rewrite 'acl_permission_check()' to not bother checking for group ownership when the permission check doesn't care.

For example, if we're asking for read permissions, and both 'group' and 'other' allow reading, there's really no reason to check if we're part of the group or not: either way, we'll allow it.

Rasmus says:
"On a bog-standard Ubuntu 20.04 install, a workload consisting of
compiling lots of userspace programs (i.e., calling lots of short-lived programs that all need to get their shared libs mapped in, and the compilers poking around looking for system headers - lots of /usr/lib, /usr/bin, /usr/include/ accesses) puts in_group_p around 0.1% according to perf top.

System-installed files are almost always 0755 (directories and binaries) or 0644, so in most cases, we can avoid the binary search and the cost of pulling the cred->groups array and in_group_p() .text into the cpu cache"

---
 fs/namei.c | 44 +++++++++++++++++++++++++++++---------------
 1 file changed, 29 insertions(+), 15 deletions(-)
fs/namei.c +29 -15
index d81f73ff1a8b..e74a7849e9b5 100644
@@ -288,37 +288,51 @@ static int check_acl(struct inode *inode, int mask)
 }
 
 /*
- * This does the basic permission checking
+ * This does the basic UNIX permission checking.
+ *
+ * Note that the POSIX ACL check cares about the MAY_NOT_BLOCK bit,
+ * for RCU walking.
  */
 static int acl_permission_check(struct inode *inode, int mask)
 {
 	unsigned int mode = inode->i_mode;
 
-	if (likely(uid_eq(current_fsuid(), inode->i_uid)))
+	/* Are we the owner? If so, ACL's don't matter */
+	if (likely(uid_eq(current_fsuid(), inode->i_uid))) {
+		mask &= 7;
 		mode >>= 6;
-	else {
-		if (IS_POSIXACL(inode) && (mode & S_IRWXG)) {
-			int error = check_acl(inode, mask);
-			if (error != -EAGAIN)
-				return error;
-		}
+		return (mask & ~mode) ? -EACCES : 0;
+	}
 
-		if (in_group_p(inode->i_gid))
-			mode >>= 3;
+	/* Do we have ACL's? */
+	if (IS_POSIXACL(inode) && (mode & S_IRWXG)) {
+		int error = check_acl(inode, mask);
+		if (error != -EAGAIN)
+			return error;
 	}
 
+	/* Only RWX matters for group/other mode bits */
+	mask &= 7;
+
 	/*
-	 * If the DACs are ok we don't need any capability check.
+	 * Are the group permissions different from
+	 * the other permissions in the bits we care
+	 * about? Need to check group ownership if so.
 	 */
-	if ((mask & ~mode & (MAY_READ | MAY_WRITE | MAY_EXEC)) == 0)
-		return 0;
-	return -EACCES;
+	if (mask & (mode ^ (mode >> 3))) {
+		if (in_group_p(inode->i_gid))
+			mode >>= 3;
+	}
+
+	/* Bits in 'mode' clear that we require? */
+	return (mask & ~mode) ? -EACCES : 0;
 }
 
 /**
  * generic_permission -  check for access rights on a Posix-like filesystem
  * @inode:	inode to check access rights for
- * @mask:	right to check for (%MAY_READ, %MAY_WRITE, %MAY_EXEC, ...)
+ * @mask:	right to check for (%MAY_READ, %MAY_WRITE, %MAY_EXEC,
+ *		%MAY_NOT_BLOCK ...)
  *
  * Used to check for read/write/execute permissions on a file.
  * We use "fsuid" for this, letting us set arbitrary permissions
Signature · 1 line
2.27.0.rc1.8.g04bd0c80d7

From ead0cfe68e04c167034405a785878058ceb6d589 Mon Sep 17 00:00:00 2001
From: Linus Torvalds <[email protected]>
Date: Sun, 7 Jun 2020 12:19:06 -0700
Subject: [PATCH 2/2] vfs: clean up posix_acl_permission() logic aroudn
MAY_NOT_BLOCK

posix_acl_permission() does not care about MAY_NOT_BLOCK, and in fact the permission logic internally must not check that bit (it's only for upper layers to decide whether they can block to do IO to look up the acl information or not).

But the way the code was written, it _looked_ like it cared, since the function explicitly did not mask that bit off.

But it has exactly two callers: one for when that bit is set, which first clears the bit before calling posix_acl_permission(), and the other call site when that bit was clear.

So stop the silly games "saving" the MAY_NOT_BLOCK bit that must not be used for the actual permission test, and that currently is pointlessly cleared by the callers when the function itself should just not care.

---
 fs/namei.c     | 2 +-
 fs/posix_acl.c | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)
fs/namei.c +1 -1
index e74a7849e9b5..72d4219c93ac 100644
@@ -271,7 +271,7 @@ static int check_acl(struct inode *inode, int mask)
 		/* no ->get_acl() calls in RCU mode... */
 		if (is_uncached_acl(acl))
 			return -ECHILD;
-	        return posix_acl_permission(inode, acl, mask & ~MAY_NOT_BLOCK);
+	        return posix_acl_permission(inode, acl, mask);
 	}
 
 	acl = get_acl(inode, ACL_TYPE_ACCESS);
fs/posix_acl.c +1 -1
index 249672bf54fe..95882b3f5f62 100644
@@ -350,7 +350,7 @@ posix_acl_permission(struct inode *inode, const struct posix_acl *acl, int want)
 	const struct posix_acl_entry *pa, *pe, *mask_obj;
 	int found = 0;
 
-	want &= MAY_READ | MAY_WRITE | MAY_EXEC | MAY_NOT_BLOCK;
+	want &= MAY_READ | MAY_WRITE | MAY_EXEC;
 
 	FOREACH_ACL_ENTRY(pa, acl, pe) {
                 switch(pa->e_tag) {
Signature · 1 line
2.27.0.rc1.8.g04bd0c80d7
maintainer
#5 lore raw
Quoted 5 lines · Linus Torvalds

Rasmus, say the word and I'll mark you for authorship on the first one.

Comments? Can you find something else wrong here, or some other fixup to do?

Al, any reaction?

It's correct, but this

fs/namei.c static int check_acl(struct inode *inode, int mask) · line 328

Quoted 7 lines
fs/namei.c +7 -0
+	if (mask & (mode ^ (mode >> 3))) {
+		if (in_group_p(inode->i_gid))
+			mode >>= 3;
+	}
+
+	/* Bits in 'mode' clear that we require? */
+	return (mask & ~mode) ? -EACCES : 0;

might be easier to follow if we had, from the very beginning done

	unsigned int deny = ~inode->i_mode;

and turned that into

	// for group the bits 3..5 apply, for others - 0..2
	// we only care which to use when they do not
	// agree anyway.
	if (mask & (deny ^ (deny >> 3))) // mask & deny != mask & (deny >> 3)
		if (in_...
			deny >>= 3;
	return mask & deny ? -EACCES : 0;

Hell knows...

#6 lore raw
Quoted 2 lines · Al Viro
        return mask & deny ? -EACCES : 0;

I agree that 'deny' would be simpler to read here, but in other places it would look odd. ie the IS_POSIXACL() thing that checks for "are group bits set" still wants the mode.

And I'd hate to have us use code that then mixes 'deny' and 'mode' when they are directly related to each other.

Anyway, I merged the patch as-is, I guess we can make future changes to this if you feel strongly about it.

Linus

#7 lore raw
In reply to Linus Torvalds
Quoted 27 lines · Linus Torvalds
Quoted 5 lines · Linus Torvalds
Quoted 3 lines

That will kinda work, except you do that mask &= MAY_RWX before check_acl(), which cares about MAY_NOT_BLOCK and who knows what other bits.

Good catch.

With the change to not clear the non-rwx bits in general, the owner case now wants to do the masking, and then the "shift left by 6" modification makes no sense since it only makes for a bigger constant (the only reason to do the shift-right was so that the bitwise not of the i_mode could be done in parallel with the shift, but with the masking that instruction scheduling optimization becomes kind of immaterial too). So I modified that patch to not bother, and add a comment about MAY_NOT_BLOCK.

And since I was looking at the MAY_NOT_BLOCK logic, it was not only not mentioned in comments, it also had some really confusing code around it.

The posix_acl_permission() looked like it tried to conserve that bit, which is completely wrong. It wasn't a bug only for the simple reason that the only two call-sites had either explicitly cleared the bit when calling, or had tested that the bit wasn't set in the first place.

Quoted 3 lines

So as a result, I wrote a second patch to clear that confusion up.

Rasmus, say the word and I'll mark you for authorship on the first one.

It might be a bit confusing with me mentioned in the third person and then also author, and it's really mostly your patch, so reported-by is fine with me. But it's up to you.

Quoted 1 line

Comments? Can you find something else wrong here, or some other fixup to do?

No, I think it's ok. I took a look at the disassembly and it looks fine. There's an extra push/pop of %r14 [that's where gcc computes mode>>3, then CSE allows it to do cmovne %r14d,%ebx after in_group_p), so the owner case gets slightly penalized. I think/hope the savings from avoiding the in_group_p should compensate for that - any absolute path open() by non-root saves at least two in_group_p. YMMV.

Rasmus