What does this sparse warning mean in posix_acl.h?

What does this sparse warning mean in posix_acl.h?

[Theodore Ts'o]

It apparently has something to do with rcu and "address spaces" but I'm
not completely sure what sparse is complaining about --- and whether it
is a false positive or a bug in the posix_acl.h.

Can someone explain what's going on, and whether it's something to be
concerned about?

Thanks,

                                                        - Ted

% ../make-ext4 C=1 fs/ext4/acl.o
make[2]: Nothing to be done for `all'.
  GEN     /u1/ext4/Makefile
  CHK     include/generated/uapi/linux/version.h
make[2]: Nothing to be done for `relocs'.
  Using /usr/projects/linux/ext4 as source for kernel
  CHK     include/generated/utsrelease.h
  CALL    /usr/projects/linux/ext4/scripts/checksyscalls.sh
<stdin>:1220:2: warning: #warning syscall kcmp not implemented [-Wcpp]
<stdin>:1223:2: warning: #warning syscall finit_module not implemented [-Wcpp]
  CHECK   /usr/projects/linux/ext4/fs/ext4/acl.c
/usr/projects/linux/ext4/include/linux/posix_acl.h:137:9: warning: incorrect type in assignment (different address spaces)
/usr/projects/linux/ext4/include/linux/posix_acl.h:137:9:    expected struct posix_acl *<noident>
/usr/projects/linux/ext4/include/linux/posix_acl.h:137:9:    got struct posix_acl [noderef] <asn:4>*<noident>
/usr/projects/linux/ext4/include/linux/posix_acl.h:137:9: warning: incorrect type in assignment (different address spaces)
/usr/projects/linux/ext4/include/linux/posix_acl.h:137:9:    expected struct posix_acl *<noident>
/usr/projects/linux/ext4/include/linux/posix_acl.h:137:9:    got struct posix_acl [noderef] <asn:4>*<noident>

Re: What does this sparse warning mean in posix_acl.h?

[Linus Torvalds]

[-- Attachment #1: Type: text/plain, Size: 1226 bytes --]

On Sat, Aug 17, 2013 at 7:28 AM, Theodore Ts'o <tytso@thunk.org> wrote:
>
> It apparently has something to do with rcu and "address spaces" but I'm
> not completely sure what sparse is complaining about --- and whether it
> is a false positive or a bug in the posix_acl.h.

So rcu_assign_pointer() wants the destination to be a pointer to
something in the "__rcu" address space, but here "p" is just a normal
kernel pointer (it's a pointer to a regular "struct posix_acl *").

(The unreadable "asn:4" comes from the fact that sparse only has a
generic notion of address spaces, where address space zero is the
"normal" C pointer address space, and then you can just make up your
own ones by number. It was initially done for just "user space", but
designed so that it could be extended to other things, and "rcu space"
was another later use for checking certain pointer semantics).

I guess we should mark i_acl and i_defauly_acl to be RCU-accessed, and
then annotate all the accesses properly.

The attached patch does so, but I only compile-tested that one file
(fs/ext4/acl.c), so it will quite possible cause tons of new warnings
elsewhere. But I'm hoping the patch at least illustrates the concept.

               Linus

[-- Attachment #2: patch.diff --]
[-- Type: application/octet-stream, Size: 2241 bytes --]

 include/linux/fs.h        |  4 ++--
 include/linux/posix_acl.h | 18 ++++++++++--------
 2 files changed, 12 insertions(+), 10 deletions(-)

diff --git a/include/linux/fs.h b/include/linux/fs.h
index 981874773e85..883c07068485 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -528,8 +528,8 @@ struct inode {
 	unsigned int		i_flags;
 
 #ifdef CONFIG_FS_POSIX_ACL
-	struct posix_acl	*i_acl;
-	struct posix_acl	*i_default_acl;
+	struct posix_acl __rcu	*i_acl;
+	struct posix_acl __rcu	*i_default_acl;
 #endif
 
 	const struct inode_operations	*i_op;
diff --git a/include/linux/posix_acl.h b/include/linux/posix_acl.h
index 7931efe71175..c3c46a37dd64 100644
--- a/include/linux/posix_acl.h
+++ b/include/linux/posix_acl.h
@@ -95,7 +95,7 @@ extern struct posix_acl *get_posix_acl(struct inode *, int);
 extern int set_posix_acl(struct inode *, int, struct posix_acl *);
 
 #ifdef CONFIG_FS_POSIX_ACL
-static inline struct posix_acl **acl_by_type(struct inode *inode, int type)
+static inline struct posix_acl __rcu **acl_by_type(struct inode *inode, int type)
 {
 	switch (type) {
 	case ACL_TYPE_ACCESS:
@@ -109,11 +109,11 @@ static inline struct posix_acl **acl_by_type(struct inode *inode, int type)
 
 static inline struct posix_acl *get_cached_acl(struct inode *inode, int type)
 {
-	struct posix_acl **p = acl_by_type(inode, type);
-	struct posix_acl *acl = ACCESS_ONCE(*p);
+	struct posix_acl __rcu **p = acl_by_type(inode, type);
+	struct posix_acl *acl = rcu_dereference(*p);
 	if (acl) {
 		spin_lock(&inode->i_lock);
-		acl = *p;
+		acl = rcu_dereference(*p);
 		if (acl != ACL_NOT_CACHED)
 			acl = posix_acl_dup(acl);
 		spin_unlock(&inode->i_lock);
@@ -130,11 +130,13 @@ static inline void set_cached_acl(struct inode *inode,
 				  int type,
 				  struct posix_acl *acl)
 {
-	struct posix_acl **p = acl_by_type(inode, type);
-	struct posix_acl *old;
+	struct posix_acl __rcu **p = acl_by_type(inode, type);
+	struct posix_acl *old, *new;
+
+	new = posix_acl_dup(acl);
 	spin_lock(&inode->i_lock);
-	old = *p;
-	rcu_assign_pointer(*p, posix_acl_dup(acl));
+	old = rcu_dereference_protected(*p, true);
+	rcu_assign_pointer(*p, new);
 	spin_unlock(&inode->i_lock);
 	if (old != ACL_NOT_CACHED)
 		posix_acl_release(old);

Re: What does this sparse warning mean in posix_acl.h?

[Theodore Ts'o]

On Sat, Aug 17, 2013 at 09:16:54AM -0700, Linus Torvalds wrote:
> On Sat, Aug 17, 2013 at 7:28 AM, Theodore Ts'o <tytso@thunk.org> wrote:
> >
> > It apparently has something to do with rcu and "address spaces" but I'm
> > not completely sure what sparse is complaining about --- and whether it
> > is a false positive or a bug in the posix_acl.h.
> 
> I guess we should mark i_acl and i_defauly_acl to be RCU-accessed, and
> then annotate all the accesses properly.

I may be missing something, but it looks like the ACL code isn't
following the RCU rules at _all_.  Even with the missing
rcu_derference() macro invocations which you added in your
proof-of-concept patch, we're still missing the rcu_read_lock() calls
around the use of the rcu pointers.

If so, I'm kind of wondering why we haven't noticed massive problems
here before.

						- Ted

Re: What does this sparse warning mean in posix_acl.h?

[Linus Torvalds]

On Sat, Aug 17, 2013 at 1:55 PM, Theodore Ts'o <tytso@mit.edu> wrote:
>
> I may be missing something, but it looks like the ACL code isn't
> following the RCU rules at _all_.  Even with the missing
> rcu_derference() macro invocations which you added in your
> proof-of-concept patch, we're still missing the rcu_read_lock() calls
> around the use of the rcu pointers.
>
> If so, I'm kind of wondering why we haven't noticed massive problems
> here before.

Yeah, the ACL caches aren't really using RCU, although they should
probably be made to use it more widely.

The ACL cache is this mixture of an unlocked "ACCESS_ONCE()" to check
for the very special case of NULL (which is a "negative ACL cache" -
no ACL's at all), and an atomic reference count that is gotten under
i_lock. See get_cached_acl() for details.

The "unlocked ACCESS_ONCE()" case is basically an optimization for the
"no ACL's case" - it isn't actually racy despite the lack of locking,
because if you see a NULL ACL pointer, that *was* true at some time,
so if it "races" with somebody setting it to anything else, you might
as well just choose to pick that simpler state.

So anybody using "get_cached_acl()" is safe. It gets either a locked
ref-counted ACL pointer, or an unlocked optimistic NULL pointer.

There is *one* special case that is actually truly using RCU, namely
"get_cached_acl_rcu()".  And that one *is* used under the RCU read
lock (it's the RCU lock for lookup). That is all safe because the
ACL's are free'd by kfree_rcu() (see posix_acl_release()).

So the ACL accesses are this somewhat strange mix of RCU and non-RCU
use. We probably could make *more* of them use the RCU model, but
apart from the RCU pathname lookup nothing else has ever been critical
enough to care.

                   Linus

Re: What does this sparse warning mean in posix_acl.h?

[Theodore Ts'o]

On Sat, Aug 17, 2013 at 02:14:45PM -0700, Linus Torvalds wrote:
> 
> So anybody using "get_cached_acl()" is safe. It gets either a locked
> ref-counted ACL pointer, or an unlocked optimistic NULL pointer.

Ah, I see.  But as we start adding the RCU annotations and the calls
to rcu_derference(), then I imagine we'll start triggering warnings
from various other static analysis tools, even if it makes sparse happy.

> So the ACL accesses are this somewhat strange mix of RCU and non-RCU
> use. We probably could make *more* of them use the RCU model, but
> apart from the RCU pathname lookup nothing else has ever been critical
> enough to care.

Ugh.  OK, I care mostly because it's adding noise to my make C=1 runs,
but I'm not sure I care enough to fix it up right away.  I'll put it
on my todo list, and hope someone beats me to it.  :-)

         	   	     	  	  - Ted

Re: What does this sparse warning mean in posix_acl.h?

[Linus Torvalds]

On Sat, Aug 17, 2013 at 2:23 PM, Theodore Ts'o <tytso@mit.edu> wrote:
>
> Ah, I see.  But as we start adding the RCU annotations and the calls
> to rcu_derference(), then I imagine we'll start triggering warnings
> from various other static analysis tools, even if it makes sparse happy.

Yes. I suspect the patch I sent out might need some tweaking to make
the dynamic RCU accessor checkers happy.

That said, it's probably fairly simple. I think my patch was *almost*
correct, and the only required change would be to change the two
occurrences of

    rcu_dereference(*p);

in "get_cached_acl()" into a "rcu_dereference_protected(*p, true)" in
order to avoid the RCU read-lock sanity checking.

The second access is actually under the i_lock (so the "protected"
part is clearly correct), and as mentioned, the first one is special
and we only use the value if it is NULL, so the "protected" is not
technically true, but it's a special case, and together with a comment
about why NULL is fine and doesn't need rcu locking it should all be
good.

The alternative is to basically say that the ACL pointers aren't
really RCU at all, and just use ACCESS_ONCE() like we do. And then
just cast things in get_cached_acl_rcu() to shut things up.

                  Linus

Re: What does this sparse warning mean in posix_acl.h?

[Linus Torvalds]

On Sat, Aug 17, 2013 at 2:14 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> So the ACL accesses are this somewhat strange mix of RCU and non-RCU
> use. We probably could make *more* of them use the RCU model, but
> apart from the RCU pathname lookup nothing else has ever been critical
> enough to care.

Side note: the whole concept of mixing locking *and* RCU is a bit odd,
but it has turned out to be a very successful model for pathname
lookup. Doing everything under RCU is basically impossible, so having
the ability to looking things up under RCU for the simple case, but
then falling back on locking for complex cases is very very powerful.

So arguably that "somewhat strange mix of RCU and non-RCU use"
shouldn't really be strange. It's just that it is complicated enough
that we only use it for pathnames right now. Everything else tends to
be more black-and-white and do one or the other, not both.

                Linus

Re: What does this sparse warning mean in posix_acl.h?

[Josh Triplett]

On Sat, Aug 17, 2013 at 10:28:22AM -0400, Theodore Ts'o wrote:
> It apparently has something to do with rcu and "address spaces" but I'm
> not completely sure what sparse is complaining about --- and whether it
> is a false positive or a bug in the posix_acl.h.
> 
> Can someone explain what's going on, and whether it's something to be
> concerned about?
[...]
> /usr/projects/linux/ext4/include/linux/posix_acl.h:137:9: warning: incorrect type in assignment (different address spaces)
> /usr/projects/linux/ext4/include/linux/posix_acl.h:137:9:    expected struct posix_acl *<noident>
> /usr/projects/linux/ext4/include/linux/posix_acl.h:137:9:    got struct posix_acl [noderef] <asn:4>*<noident>
> /usr/projects/linux/ext4/include/linux/posix_acl.h:137:9: warning: incorrect type in assignment (different address spaces)
> /usr/projects/linux/ext4/include/linux/posix_acl.h:137:9:    expected struct posix_acl *<noident>
> /usr/projects/linux/ext4/include/linux/posix_acl.h:137:9:    got struct posix_acl [noderef] <asn:4>*<noident>

Address space 4 is __rcu.  This warning means you accessed an RCU
pointer directly, without using the appropriate RCU primitive
(rcu_assign_pointer, rcu_dereference, etc).

- Josh Triplett

Re: What does this sparse warning mean in posix_acl.h?

[Linus Torvalds]

On Sat, Aug 17, 2013 at 9:17 AM, Josh Triplett <josh@joshtriplett.org> wrote:
>
> Address space 4 is __rcu.  This warning means you accessed an RCU
> pointer directly, without using the appropriate RCU primitive
> (rcu_assign_pointer, rcu_dereference, etc).

Well, actually, in this case it was the other way around: using an RCU
primitive (rcu_assign_pointer) without having marked the variable for
RCU.

                  Linus