Skip to contentSkip to conversation

Found it! (was Re: [3.10] Oopses in kmem_cache_allocate() via prepare_creds())

PATCH In review Linus Torvalds 6 participants 16 messages Dec 2, 2013 – Dec 11, 2013

Subsystems (4)
lore
Share & tools
lore
#0 lore raw
Quoted 4 lines · Linus Torvalds

I still don't see what could be wrong with the pipe_inode_info thing, but the fact that it's been so consistent in your traces does make me suspect it really is *that* particular slab.

I think I finally found it.

I've spent waaayy too much time looking at and thinking about that code without seeing anything wrong, but this morning I woke up and thought to myself "What if.."

And looking at the code again, I went "BINGO".

All our reference counting etc seems right, but we have one very subtle bug: on the freeing path, we have a pattern like this:

        spin_lock(&inode->i_lock);
        if (!--pipe->files) {
                inode->i_pipe = NULL;
                kill = 1;
        }
        spin_unlock(&inode->i_lock);
        __pipe_unlock(pipe);
        if (kill)
                free_pipe_info(pipe);

which on the face of it is trying to be very careful in not accessing the pipe-info after it is released by having that "kill" flag, and doing the release last.

And it's complete garbage.

Why?

Because the thread that decrements "pipe->files" *without* releasing it, will very much access it after it has been dropped: that "__pipe_unlock(pipe)" happens *after* we've decremented the pipe reference count and dropped the inode lock. So another CPU can come in and free the structure concurrently with that __pipe_unlock(pipe).

This happens in two places, and we don't actually need or want the pipe lock for the pipe->files accesses (since pipe->files is protected by inode->i_lock, not the pipe lock), so the solution is to just do the __pipe_unlock() before the whole dance about the pipe->files reference count.

Patch appended. And no wonder nobody has ever seen it, because the race is unlikely as hell to ever happen. Simon, I assume it will be another few months before we can say "yeah, that fixed it", but I really think this is it. It explains all the symptoms, including "DEBUG_PAGEALLOC didn't catch it" (because the access happens just as it is released, and DEBUG_PAGEALLOC takes too long to actually free unmap the page etc).

Linus

 fs/pipe.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
fs/pipe.c +4 -2
index d2c45e14e6d8..18f1a4b2dbbc 100644
@@ -743,13 +743,14 @@ pipe_release(struct inode *inode, struct file *file)
 		kill_fasync(&pipe->fasync_readers, SIGIO, POLL_IN);
 		kill_fasync(&pipe->fasync_writers, SIGIO, POLL_OUT);
 	}
+	__pipe_unlock(pipe);
+
 	spin_lock(&inode->i_lock);
 	if (!--pipe->files) {
 		inode->i_pipe = NULL;
 		kill = 1;
 	}
 	spin_unlock(&inode->i_lock);
-	__pipe_unlock(pipe);
 
 	if (kill)
 		free_pipe_info(pipe);
@@ -1130,13 +1131,14 @@ err_wr:
 	goto err;
 
 err:
+	__pipe_unlock(pipe);
+
 	spin_lock(&inode->i_lock);
 	if (!--pipe->files) {
 		inode->i_pipe = NULL;
 		kill = 1;
 	}
 	spin_unlock(&inode->i_lock);
-	__pipe_unlock(pipe);
 	if (kill)
 		free_pipe_info(pipe);
 	return ret;
#1 lore raw
Quoted 68 lines · Linus Torvalds
Quoted 4 lines · Linus Torvalds

I still don't see what could be wrong with the pipe_inode_info thing, but the fact that it's been so consistent in your traces does make me suspect it really is *that* particular slab.

I think I finally found it.

I've spent waaayy too much time looking at and thinking about that code without seeing anything wrong, but this morning I woke up and thought to myself "What if.."

And looking at the code again, I went "BINGO".

All our reference counting etc seems right, but we have one very subtle bug: on the freeing path, we have a pattern like this:

        spin_lock(&inode->i_lock);
        if (!--pipe->files) {
                inode->i_pipe = NULL;
                kill = 1;
        }
        spin_unlock(&inode->i_lock);
        __pipe_unlock(pipe);
        if (kill)
                free_pipe_info(pipe);

which on the face of it is trying to be very careful in not accessing the pipe-info after it is released by having that "kill" flag, and doing the release last.

And it's complete garbage.

Why?

Because the thread that decrements "pipe->files" *without* releasing it, will very much access it after it has been dropped: that "__pipe_unlock(pipe)" happens *after* we've decremented the pipe reference count and dropped the inode lock. So another CPU can come in and free the structure concurrently with that __pipe_unlock(pipe).

This happens in two places, and we don't actually need or want the pipe lock for the pipe->files accesses (since pipe->files is protected by inode->i_lock, not the pipe lock), so the solution is to just do the __pipe_unlock() before the whole dance about the pipe->files reference count.

Patch appended. And no wonder nobody has ever seen it, because the race is unlikely as hell to ever happen. Simon, I assume it will be another few months before we can say "yeah, that fixed it", but I really think this is it. It explains all the symptoms, including "DEBUG_PAGEALLOC didn't catch it" (because the access happens just as it is released, and DEBUG_PAGEALLOC takes too long to actually free unmap the page etc).

Linus

 fs/pipe.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
fs/pipe.c +0 -0
index d2c45e14e6d8..18f1a4b2dbbc 100644
@@ -743,13 +743,14 @@ pipe_release(struct inode *inode, struct file *file)
 		kill_fasync(&pipe->fasync_readers, SIGIO, POLL_IN);
 		kill_fasync(&pipe->fasync_writers, SIGIO, POLL_OUT);

fs/pipe.c pipe_release(struct inode *inode, struct file *file) · line 752

Quoted 10 lines
fs/pipe.c +2 -1
 	}
+	__pipe_unlock(pipe);
+
 	spin_lock(&inode->i_lock);
 	if (!--pipe->files) {
 		inode->i_pipe = NULL;
 		kill = 1;
 	}
 	spin_unlock(&inode->i_lock);
-	__pipe_unlock(pipe);

I'm wondering why pipe-mutex was introduced. It was done fairly recently, with no justification given:

From 72b0d9aacb89f3759931ec440e1b535671145bb4 Mon Sep 17 00:00:00 2001
From: Al Viro <[email protected]>
Date: Thu, 21 Mar 2013 02:32:24 -0400
Subject: [PATCH] pipe: don't use ->i_mutex

now it can be done - put mutex into pipe_inode_info, use it instead of ->i_mutex

---

   fs/ocfs2/file.c           | 6 ++----
   fs/pipe.c                 | 5 +++--
   include/linux/pipe_fs_i.h | 2 ++
   3 files changed, 7 insertions(+), 6 deletions(-)

It's not like there should be many (any?) VFS operations where a pipe is used via i_mutex and pipe->mutex in parallel, which would improve scalability - so I don't see the scalability advantage. (But I might be missing something)

Barring such kind of workload the extra mutex just adds extra micro-costs because now two locks have to be taken on creation/destruction, plus it adds extra complexity and races.

So unless I'm missing something obvious, another good fix would be to just revert pipe->mutex and rely on i_mutex as before?

Thanks,

Ingo

maintainer
#2 lore raw
Quoted 11 lines · Ingo Molnar

It's not like there should be many (any?) VFS operations where a pipe is used via i_mutex and pipe->mutex in parallel, which would improve scalability - so I don't see the scalability advantage. (But I might be missing something)

Barring such kind of workload the extra mutex just adds extra micro-costs because now two locks have to be taken on creation/destruction, plus it adds extra complexity and races.

So unless I'm missing something obvious, another good fix would be to just revert pipe->mutex and rely on i_mutex as before?

You are missing the extra shitloads of complexity in ->i_mutex ordering, and ->i_mutex is already used for too many things...

#3 lore raw
Quoted 11 lines · Al Viro
Quoted 9 lines · Ingo Molnar

It's not like there should be many (any?) VFS operations where a pipe is used via i_mutex and pipe->mutex in parallel, which would improve scalability - so I don't see the scalability advantage. (But I might be missing something)

Barring such kind of workload the extra mutex just adds extra micro-costs because now two locks have to be taken on creation/destruction, plus it adds extra complexity and races.

Quoted 5 lines
Quoted 2 lines

So unless I'm missing something obvious, another good fix would be to just revert pipe->mutex and rely on i_mutex as before?

You are missing the extra shitloads of complexity in ->i_mutex ordering, and ->i_mutex is already used for too many things...

Well, AFAICS the split-out did not reduce ordering complexity but increased it, at least in the short term: pipe->mutex now has to be taken in the right order with i_mutex, the subject of the bug here.

Plus AFAICS where i_mutex was used for pipe-internal purposes we used pretty generic facilities like user-copy, signal-sending, wakeups, etc. - none of which is really adding complexity to i_mutex ordering, as those are always expected to be facilities independent of the VFS in the future as well.

Anyway, it's your call obviously.

In any case, what prompted my reply was the overly terse nature of the changelog, would it make sense to put more verbose reasoning into changelogs, especially where such a change has a seemingly non-obvious (to me) cost/benefit balance?

Thanks,

Ingo

maintainer
#4 lore raw
In reply to Linus Torvalds
Quoted 48 lines · Linus Torvalds
Quoted 4 lines · Linus Torvalds

I still don't see what could be wrong with the pipe_inode_info thing, but the fact that it's been so consistent in your traces does make me suspect it really is *that* particular slab.

I think I finally found it.

I've spent waaayy too much time looking at and thinking about that code without seeing anything wrong, but this morning I woke up and thought to myself "What if.."

And looking at the code again, I went "BINGO".

All our reference counting etc seems right, but we have one very subtle bug: on the freeing path, we have a pattern like this:

        spin_lock(&inode->i_lock);
        if (!--pipe->files) {
                inode->i_pipe = NULL;
                kill = 1;
        }
        spin_unlock(&inode->i_lock);
        __pipe_unlock(pipe);
        if (kill)
                free_pipe_info(pipe);

which on the face of it is trying to be very careful in not accessing the pipe-info after it is released by having that "kill" flag, and doing the release last.

And it's complete garbage.

Why?

Because the thread that decrements "pipe->files" *without* releasing it, will very much access it after it has been dropped: that "__pipe_unlock(pipe)" happens *after* we've decremented the pipe reference count and dropped the inode lock. So another CPU can come in and free the structure concurrently with that __pipe_unlock(pipe).

This happens in two places, and we don't actually need or want the pipe lock for the pipe->files accesses (since pipe->files is protected by inode->i_lock, not the pipe lock), so the solution is to just do the __pipe_unlock() before the whole dance about the pipe->files reference count.

Quoted 7 lines

Patch appended. And no wonder nobody has ever seen it, because the race is unlikely as hell to ever happen. Simon, I assume it will be another few months before we can say "yeah, that fixed it", but I really think this is it. It explains all the symptoms, including "DEBUG_PAGEALLOC didn't catch it" (because the access happens just as it is released, and DEBUG_PAGEALLOC takes too long to actually free unmap the page etc).

Nice catch. I'd probably add

/* we are holding inode->i_pipe->files */
static void drop_pipe(struct inode *inode, struct pipe_inode_info *pipe)

{
	int kill = 0;
        spin_lock(&inode->i_lock);
	WARN_ON(pipe != inode->i_pipe);
        if (!--pipe->files) {
                inode->i_pipe = NULL;
                kill = 1;
        }
        spin_unlock(&inode->i_lock);
        if (kill)
                free_pipe_info(pipe);
}

and use it in both places...

#5 lore raw
In reply to Linus Torvalds

Once more on this issue, because I've been unable to stop thinking about it, and noticed that it's actually even subtler than I thought initially.

Quoted 20 lines · Linus Torvalds

All our reference counting etc seems right, but we have one very subtle bug: on the freeing path, we have a pattern like this:

        spin_lock(&inode->i_lock);
        if (!--pipe->files) {
                inode->i_pipe = NULL;
                kill = 1;
        }
        spin_unlock(&inode->i_lock);
        __pipe_unlock(pipe);
        if (kill)
                free_pipe_info(pipe);

which on the face of it is trying to be very careful in not accessing the pipe-info after it is released by having that "kill" flag, and doing the release last.

And it's complete garbage.

Quoted 7 lines

Why?

Because the thread that decrements "pipe->files" *without* releasing it, will very much access it after it has been dropped: that "__pipe_unlock(pipe)" happens *after* we've decremented the pipe reference count and dropped the inode lock. So another CPU can come in and free the structure concurrently with that __pipe_unlock(pipe).

So I still think this was the bug, and the problems Simon and Ian saw should be fixed, but it ends up being even more interesting than just the above explanation.

Yes, the inode->i_lock is what protects the "pipe->files" counter, and we do in fact on the allocation side have cases where we update the counter with just the spinlock held, without holding the pipe mutex. So when we decrement the 'files' counter and release the i_lock spinlock, technically it's now freeable.

BUT.

It turns out that on the *releasing* side, the old code actually held the pipe->mutex in all situations where it was decrementing the pipe->files counter, so the race we saw happen *shouldn't* have happened, because even though the i_lock spinlock was the real lock, the pipe->mutex lock *should* have serialized the two threads releasing the pipe, and thus the bug shouldn't have been visible.

So we have two threads serialized by that pipe->lock mutex, and yet one of them writes to the structure *after* the other one (remember:
serialized!) decides that it can free it.

In other words: while the fix for pipes was simply to move the mutex unlock up, this actually shows a big fundamental issue with mutexes. That issue being that you cannot use them (at least as is) to protect an object reference count. And I wonder if we do that somewhere else.

And I kind of knew about this, because we historically had very strict rules about the whole "don't use semaphores to implement completions", which has the exact same issue: a semaphore isn't "safe" wrt de-allocation, and we have some places that use completions exactly because completions guarantee that the very last access to them on the waiter is on the waiter side (who can then free the memory), and all other users are "safe".

And mutexes and semaphores don't have those guarantees: they just serialize what is *inside* the mutex/semaphore, but not necessarily the lock *ITSELF*.

So this "obviously correct" pattern is in fact fundamentally buggy:

   mutex_lock(obj->lock);
   dead = !--obj->recount;
   mutex_unlock(obj->lock);
   if (dead)
      free(obj);

even though it *looks* safe. Because by definition only the last thread to get the object mutex will be the one freeing it, right?

Wrong. Because what can happen is (roughly):

    CPU1:

        mutex_lock(obj->lock);
        dead = !--obj->refcount;
        // refcount was 2, is now 1, dead = 0.

.. at this point CPU2 comes in, tries to do the same thing:

        mutex_lock(obj->lock);
        // blocks on obj->lock, goes to slowpath
        // mutex is negative, CPU2 is in optimistic
        //  spinning mode in __mutex_lock_common
        // under #ifdef CONFIG_MUTEX_SPIN_ON_OWNER

-- CPU1 again:

        mutex_unlock(obj->lock);
          __mutex_fastpath_unlock()
            fastpath fails (because mutex is nonpositive
              __mutex_unlock_slowpath:
                if (__mutex_slowpath_needs_to_unlock())
                        atomic_set(&lock->count, 1);

.. CPU2 - who is spinning, sees this, and does

                if ((atomic_read(&lock->count) == 1) &&
                    (atomic_cmpxchg(&lock->count, 1, 0) == 1)) {

.. and now CPU2 owns the mutex, and goes on to do

        dead = !--obj->refcount;
        // refcount was 1, is now 0, dead = 1.
        mutex_unlock(obj->lock);
        if (dead)
                free(obj);

- but in the meantime, CPU1 is busy still unlocking:

                if (!list_empty(&lock->wait_list)) {
                        /* get the first entry from the wait-list: */
                        struct mutex_waiter *waiter =
                                        list_entry(lock->wait_list.next,
                                                   struct mutex_waiter, list);

                        debug_mutex_wake_waiter(lock, waiter);

                        wake_up_process(waiter->task);
        }
        spin_unlock_mutex(&lock->wait_lock, flags);

and in particular notice how CPU1 wrote to the lock *after* CPU2 had gotten the lock and free'd the data structure. In practice, it's only really that "spin_unlock_mutex(&lock->wait_lock, flags);" that happens (and this is how we got the single byte being incremented).

In other words, it's unsafe to protect reference counts inside objects with anything but spinlocks and/or atomic refcounts. Or you have to have the lock *outside* the object you're protecting (which is often what you want for other reasons anyway, notably lookup).

So having a non-atomic refcount protected inside a sleeping lock is a bug, and that's really the bug that ended up biting us for pipes.

Now, the question is: do we have other such cases? How do we document this? Do we try to make mutexes and other locks safe to use for things like this?

Linus

maintainer
#6 lore raw
Quoted 11 lines · Linus Torvalds

In other words, it's unsafe to protect reference counts inside objects with anything but spinlocks and/or atomic refcounts. Or you have to have the lock *outside* the object you're protecting (which is often what you want for other reasons anyway, notably lookup).

So having a non-atomic refcount protected inside a sleeping lock is a bug, and that's really the bug that ended up biting us for pipes.

Now, the question is: do we have other such cases? How do we document this? Do we try to make mutexes and other locks safe to use for things like this?

Umm... AFAICS, in VFS proper we have
files_struct - atomic_dec_and_test
fs_struct - spinlock + int
file - atomic_long_dec_and_test (with delays after that, including
RCU).
super_block - global spinlock + int (s_count); the mutex in there
(->s_umount) can be taken by anybody who holds an active ref *or* has bumped ->s_count while holding sb_lock. Exactly to prevent that kind of unpleasantness. Freeing RCU-delayed.
vfsmount - percpu counter + flag + global seqlock, with quite a bit of
contortions for the sake of avoiding cross-CPU stores on fastpath; discussed back in October, concluded to be safe. Freeing RCU-delayed.

	dentry - lockref, with RCU-delayed actual freeing.
	file_system_type, nls_table, linux_binfmt - module refcount of "owner";

search structures protected by global spinlocks or rwlocks, exiting module is responsible for unregistering first.
inode - atomic_dec_and_lock, with actual freeing RCU-delayed (and
evicting code waiting for pagecache references to be gone, with the rest being responsibility of fs method called before we free the sucker)
block_device - part of bdevfs inode

These should be safe, but damnit, we really need the lifecycle documented for all objects - the above is only a part of it (note that for e.g. superblocks we have additional rules re "->s_active can't be incremented for any reason once it drops to zero, it can't be incremented until superblock had been marked 'born' and it crosses over to zero only with ->s_umount held"; there's 6 stages in life cycle of struct super_block and we had interesting bugs due to messing the transitions up). The trouble is, attempt to write those down tends to stray into massive grep session, with usual results - some other crap gets found (e.g. in some odd driver) and needs to be dealt with ;-/ Sigh...

maintainer
#7 lore raw

gfs2 deadlock (was Re: Found it)

Quoted 10 lines · Al Viro

These should be safe, but damnit, we really need the lifecycle documented for all objects - the above is only a part of it (note that for e.g. superblocks we have additional rules re "->s_active can't be incremented for any reason once it drops to zero, it can't be incremented until superblock had been marked 'born' and it crosses over to zero only with ->s_umount held"; there's 6 stages in life cycle of struct super_block and we had interesting bugs due to messing the transitions up). The trouble is, attempt to write those down tends to stray into massive grep session, with usual results - some other crap gets found (e.g. in some odd driver) and needs to be dealt with ;-/ Sigh...

... and sure enough, this time is no different - gfs2 sysfs-related code cheerfully violates lifetime rules for superblocks, which would've caused a major mess later, if it had not immediately caused a deadlock on the same superblock ;-/

Watch: gfs2 creates a bunch of files in sysfs (/sys/fs/gfs2/<devname>/*). Said bunch gets removed from ->put_super(). Which is called under ->s_umount. Guess what happens if somebody tries to write "1" to /sys/fs/gfs2/.../freeze just as we enter that ->put_super() (or at any point starting from the moment when deactivate_locked_super() has dropped the last active reference)? This:
static ssize_t freeze_store(struct gfs2_sbd *sdp, const char *buf, size_t len)

{
        int error;
        int n = simple_strtol(buf, NULL, 0);

        if (!capable(CAP_SYS_ADMIN))
                return -EPERM;

        switch (n) {
[snip]
        case 1:
                error = freeze_super(sdp->sd_vfs);

And freeze_super(sb) assumes that caller has an active reference to sb:
int freeze_super(struct super_block *sb)

{
        int ret;

        atomic_inc(&sb->s_active);

... which is not legitimate when ->s_active has already reached zero. And right after that we hit this:

        down_write(&sb->s_umount);

Voila - write(2) is waiting for ->s_umount, while umount(2) is holding ->s_umount and waits for write(2) to get past freeze_store().

Hell knows what to do here - atomic_inc_not_zero() in freeze_super() (and failing if it fails) would've worked, but it doesn't help with the deadlock - just write "0" instead and we hit thaw_super(), which starts with grabbing ->s_umount. atomic_inc_not_zero()/deactivate_super() around that call of thaw_super() would probably work, but I'll need to look at that after I get some sleep...

Why bother with sysfs, anyway? What's wrong with putting those same files on gfs2meta, seeing that _this_ would have no problems with object lifetimes? Too late by now, of course, but...

#8 lore raw

Re: gfs2 deadlock (was Re: Found it)

Hi,

Quoted 59 lines · Al Viro
Quoted 10 lines · Al Viro

These should be safe, but damnit, we really need the lifecycle documented for all objects - the above is only a part of it (note that for e.g. superblocks we have additional rules re "->s_active can't be incremented for any reason once it drops to zero, it can't be incremented until superblock had been marked 'born' and it crosses over to zero only with ->s_umount held"; there's 6 stages in life cycle of struct super_block and we had interesting bugs due to messing the transitions up). The trouble is, attempt to write those down tends to stray into massive grep session, with usual results - some other crap gets found (e.g. in some odd driver) and needs to be dealt with ;-/ Sigh...

... and sure enough, this time is no different - gfs2 sysfs-related code cheerfully violates lifetime rules for superblocks, which would've caused a major mess later, if it had not immediately caused a deadlock on the same superblock ;-/

Watch: gfs2 creates a bunch of files in sysfs (/sys/fs/gfs2/<devname>/*). Said bunch gets removed from ->put_super(). Which is called under ->s_umount. Guess what happens if somebody tries to write "1" to /sys/fs/gfs2/.../freeze just as we enter that ->put_super() (or at any point starting from the moment when deactivate_locked_super() has dropped the last active reference)? This:
static ssize_t freeze_store(struct gfs2_sbd *sdp, const char *buf, size_t len)

{
        int error;
        int n = simple_strtol(buf, NULL, 0);

        if (!capable(CAP_SYS_ADMIN))
                return -EPERM;

        switch (n) {
[snip]
        case 1:
                error = freeze_super(sdp->sd_vfs);

And freeze_super(sb) assumes that caller has an active reference to sb:
int freeze_super(struct super_block *sb)

{
        int ret;

        atomic_inc(&sb->s_active);

... which is not legitimate when ->s_active has already reached zero. And right after that we hit this:

        down_write(&sb->s_umount);

Voila - write(2) is waiting for ->s_umount, while umount(2) is holding ->s_umount and waits for write(2) to get past freeze_store().

Hell knows what to do here - atomic_inc_not_zero() in freeze_super() (and failing if it fails) would've worked, but it doesn't help with the deadlock - just write "0" instead and we hit thaw_super(), which starts with grabbing ->s_umount. atomic_inc_not_zero()/deactivate_super() around that call of thaw_super() would probably work, but I'll need to look at that after I get some sleep...

Quoted 3 lines

Why bother with sysfs, anyway? What's wrong with putting those same files on gfs2meta, seeing that _this_ would have no problems with object lifetimes? Too late by now, of course, but...

Well now. Thats is a bit of a can of worms :(

Short answer is that the sysfs stuff was largely inherited from GFS unchanged. The metafs was added in GFS2 as a way to access files which are otherwise hidden from the user (e.g. the journals). In retrospect, both were probably a mistake, for different reasons.

Quite a large number of the interfaces in sysfs were added to do what should really have been the job of mount options. Over time we've now got to the point that anything that can be done with sysfs that makes sense as a mount option, is now a mount option and thats the recommended way to do things.

Freeze can be done via dmsetup suspend, and thats what we've recommended that people use for a long time now. The only thing in userspace that used the sysfs interface was gfs2_tool (an obsolete and no longer shipping userspace tool). So the chances are that nothing uses that interface any more, but it has been left for backward compatibility purposes. Maybe we could remove it now?

In any case freeze in GFS2 is due for an overhaul and Ben Marzinski has patches which he is currently working on as we speak, that are a big step forward in this area, even though they won't (I think) solve the issue that you've identified here.

What we do need to preserve are the uevents which are generated though, since those are used by the older cluster suite programs, and are also useful for debugging mount/umount/recovery issues, even with the latest pcs based cluster suite.

Returning briefly to the metafs, the locking there has also been a pain to deal with. Over time I hope to transition to using "proper" interfaces rather than trying to directly touch the internal files. We've already done that with quota - that means that extending the fs and adding journals are the only two operations left which still use the metafs as an interface. Eventually I'd like those to have fs independent (if possible!) interfaces too and then userspace will no longer require direct access to the metafs. Extending the fs is fairly easy to fix I think, adding journals will be more tricky to do.

So although it probably doesn't help a lot - thats the background behind where we are today,

Steve.

#9 lore raw

PATCH 1/1 mutexes: Add CONFIG_DEBUG_MUTEX_FASTPATH=y debug variant to debug SMP races

In reply to Linus Torvalds
Quoted 19 lines · Linus Torvalds

- but in the meantime, CPU1 is busy still unlocking:

                if (!list_empty(&lock->wait_list)) {
                        /* get the first entry from the wait-list: */
                        struct mutex_waiter *waiter =
                                        list_entry(lock->wait_list.next,
                                                   struct mutex_waiter, list);

                        debug_mutex_wake_waiter(lock, waiter);

                        wake_up_process(waiter->task);
        }
        spin_unlock_mutex(&lock->wait_lock, flags);

and in particular notice how CPU1 wrote to the lock *after* CPU2 had gotten the lock and free'd the data structure. In practice, it's only really that "spin_unlock_mutex(&lock->wait_lock, flags);" that happens (and this is how we got the single byte being incremented).

Quoted 4 lines

In other words, it's unsafe to protect reference counts inside objects with anything but spinlocks and/or atomic refcounts. Or you have to have the lock *outside* the object you're protecting (which is often what you want for other reasons anyway, notably lookup).

Indeed: this comes from mutex->count being separate from mutex->wait_lock, and this should affect every architecture that has a mutex->count fast-path implemented (essentially every architecture that matters).

Such bugs should also magically go away with mutex debugging enabled.

I'd expect such bugs to be more prominent with unlucky object size/alignment: if mutex->count lies on a separate cache line from mutex->wait_lock.

Side note: this might be a valid light weight debugging technique, we could add padding between the two fields to force them into separate cache lines, without slowing it down.

Simon, would you be willing to try the fairly trivial patch below? Please enable CONFIG_DEBUG_MUTEX_FASTPATH=y. Does your kernel fail faster that way?

Quoted 5 lines

So having a non-atomic refcount protected inside a sleeping lock is a bug, and that's really the bug that ended up biting us for pipes.

Now, the question is: do we have other such cases? How do we document this? [...]

I'd not be surprised if we had such cases, especially where spinlock->mutex conversions were done. About 20% of the kernel's critical sections use mutexes, 60% use spinlocks. (the remaining 20% is shared between semaphored, rwlocks and rwsems, in that order of frequency.)

Quoted 2 lines

[...] Do we try to make mutexes and other locks safe to use for things like this?

I think we try that, to make mutexes safer in general.

Can you see a way to do that fairly cheaply?

I can see two approaches, both rather radical:

1)

Eliminate mutex->count and (ab-)use mutex->wait_lock as 'the' mutex
lock: with TICKET_SLOWPATH_FLAG used to denote waiters or so and care taken to not use it as a 'real' spinlock but use the raw accessors.

This would still allow a good mutex_lock() fastpath, as it would essentially become spin_trylock() with an asm goto slow path helper perhaps.

Doing this would have various advantages:

- we'd eliminate much (all?) of per arch mutex code
- we'd share spinlock and mutex low level implementations
- we'd reduce struct mutex size by 4 bytes

It's still early in the morning so I might be missing something trivial though - this sounds suspiciously too easy ;-) Having a proper mutex slowpath might not be so easy without changing the spinlock code.

2)

Another method would be to do the opposite: eliminate mutex->wait_lock [for the non-debug case] and do everything via mutex->count and mutex->owner.

This saves even more space and potentially enables a tighter slowpath.

It probably won't hurt the massively parallel case, as we already do smart MCS locking via mutex->spin_mlock.

So I'd argue for #2. (Assuming it addresses the problem)

Thanks,

Ingo

=======================>
Subject: mutexes: Add CONFIG_DEBUG_MUTEX_FASTPATH=y debug variant to debug SMP races
From: Ingo Molnar <[email protected]>

Help debug SMP ordering issues by forcing mutex->count on a separate cache line with mutex->wait_lock. This will make certain classes races more prominent, without slowing down other parts of the mutex code.

include/linux/mutex.h +10 -1
index d318193..6952fc4 100644
@@ -49,6 +49,15 @@
 struct mutex {
 	/* 1: unlocked, 0: locked, negative: locked, possible waiters */
 	atomic_t		count;
+#ifdef CONFIG_DEBUG_MUTEX_FASTPATH
+	/*
+	 * Debug SMP ordering issues by forcing mutex->count on a separate
+	 * cache line with mutex->wait_lock. This will make certain classes
+	 * of races more prominent, without slowing down other parts of the
+	 * mutex code.
+	 */
+	u8			__cache_padding[64];
+#endif
 	spinlock_t		wait_lock;
 	struct list_head	wait_list;
 #if defined(CONFIG_DEBUG_MUTEXES) || defined(CONFIG_SMP)
@@ -58,7 +67,7 @@ struct mutex {
 	void			*spin_mlock;	/* Spinner MCS lock */
 #endif
 #ifdef CONFIG_DEBUG_MUTEXES
-	const char 		*name;
+	const char		*name;
 	void			*magic;
 #endif
 #ifdef CONFIG_DEBUG_LOCK_ALLOC
lib/Kconfig.debug +12 -0
index 6982094..08618a9 100644
@@ -845,6 +845,18 @@ config DEBUG_SPINLOCK
 	  best used in conjunction with the NMI watchdog so that spinlock
 	  deadlocks are also debuggable.
 
+config DEBUG_MUTEX_FASTPATH
+	bool "Mutex debugging: lightweight mutex race check"
+	depends on DEBUG_KERNEL && !DEBUG_MUTEXES
+	help
+	  This debug feature simply increases struct mutex by 64 bytes and
+	  thus allows certain mutex related SMP races to be detected more
+	  easily.
+
+	  (This feature is disabled if DEBUG_MUTEXES is enabled.)
+
+	  If unsure, say N.
+
 config DEBUG_MUTEXES
 	bool "Mutex debugging: basic checks"
 	depends on DEBUG_KERNEL
#10 lore raw

Re: [PATCH] mutexes: Add CONFIG_DEBUG_MUTEX_FASTPATH=y debug variant to debug SMP races

Quoted 4 lines · Ingo Molnar

I'd expect such bugs to be more prominent with unlucky object size/alignment: if mutex->count lies on a separate cache line from mutex->wait_lock.

I doubt that makes much of a difference. It's still just "CPU cycles" away, and the window will be tiny unless you have multi-socket machines and/or are just very unlucky.

For stress-testing, it would be much better to use some hack like

    /* udelay a bit if the spinlock isn't contended */
    if (mutex->wait_lock.ticket.head+1 == mutex->wait_lock.ticket.tail)
        udelay(1);

in __mutex_unlock_common() just before the spin_unlock(). Make the window really *big*.

Quoted 8 lines · That
Quoted 5 lines

So having a non-atomic refcount protected inside a sleeping lock is a bug, and that's really the bug that ended up biting us for pipes.

Now, the question is: do we have other such cases? How do we document this? [...]

I'd not be surprised if we had such cases, especially where spinlock->mutex conversions were done

So I actually don't think we do. Why? Having a sleeping lock inside the object that protects the refcount is actually hard to do.

You need to increment the refcount when finding the object, but that in turn tends to imply holding the lock *before* you find it. Or you have to find it locklessly, which in turn implies RCU, which in turn implies non-sleeping lock.

And quite frankly, anybody who uses SRCU and a sleeping lock is just broken to begin with. That's just an abomination. If the RT codepaths do something like that, don't even tell me. It's broken and stupid.

So protecting a refcount with a mutex in the same object is really quite hard. Even the pipe code didn't actually do that, it just happened to nest the real lock inside the sleeping lock (but that's also why it was so easy to fix - the sleeping lock wasn't actually necessary or helpful in the refcounting path).

So my *gut* feel is that nobody does this. But people have been known to do insane things just because they use too many sleeping locks and think it's "better".

Linus

#11 lore raw

Re: [PATCH] mutexes: Add CONFIG_DEBUG_MUTEX_FASTPATH=y debug variant to debug SMP races

Quoted 10 lines · Linus Torvalds
Quoted 4 lines · Ingo Molnar

I'd expect such bugs to be more prominent with unlucky object size/alignment: if mutex->count lies on a separate cache line from mutex->wait_lock.

I doubt that makes much of a difference. It's still just "CPU cycles" away, and the window will be tiny unless you have multi-socket machines and/or are just very unlucky.

Quoted 8 lines

For stress-testing, it would be much better to use some hack like

    /* udelay a bit if the spinlock isn't contended */
    if (mutex->wait_lock.ticket.head+1 == mutex->wait_lock.ticket.tail)
        udelay(1);

in __mutex_unlock_common() just before the spin_unlock(). Make the window really *big*.

I haven't had a chance yet to do much testing of the proposed race fix and race enlarging patches, but I did write a tool to reproduce the race. I started it running and left for dinner, and sure enough, it actually seems to work on plain 3.12 on a Dell PowerEdge r410 w/dual E5520, reproducing "Poison overwritten" at a rate of about once every 15 minutes (running 6 in parallel, booted with "slub_debug").

I have no idea if actually relying on tsc alignment between cores and sockets is a reasonable idea these days, but it seems to work. I first used a read() on a pipe close()d by the other process to synchronize them, but this didn't seem to work as well as busy-waiting until the timestamp counters pass a previously-decided-upon start time.

Meanwhile, I still don't understand how moving the unlock _up_ to cover less of the code can solve the race, but I will stare at your long explanation more tomorrow.

Simon-

#include <sys/wait.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

#define MAX_PIPES 450
#define FORK_CYCLES 2000000
#define CLOSE_CYCLES 100000
#define STAT_SHIFT 6

static inline unsigned long readtsc()

{
	unsigned int low, high;
	asm volatile("rdtsc" : "=a" (low), "=d" (high));
	return low | ((unsigned long)(high) << 32);
}

static int pipefd[MAX_PIPES][2];

int main(int argc, char *argv[]) {
	unsigned long loop, race_start, miss;
	unsigned long misses = 0, races = 0;
	int i;
	pid_t pid;
	struct rlimit rlim = {
		.rlim_cur = MAX_PIPES * 2 + 96,
		.rlim_max = MAX_PIPES * 2 + 96,
	};

	if (setrlimit(RLIMIT_NOFILE, &rlim) != 0)
		perror("setrlimit(RLIMIT_NOFILE)");

	for (loop = 1;;loop++) {
		/*
		 * Make a bunch of pipes
		 */
		for (i = 0;i < MAX_PIPES;i++) {
			if (pipe(pipefd[i]) == -1) {
				perror("pipe()");
				exit(EXIT_FAILURE);
			}
		}

		race_start = readtsc() + FORK_CYCLES;

		asm("":::"memory");

		pid = fork();
		if (pid == -1) {
			perror("fork()");
			exit(EXIT_FAILURE);
		}
		pid = !!pid;

		/*
		 * Close one pipe descriptor per process
		 */
		for (i = 0;i < MAX_PIPES;i++)
			close(pipefd[i][!pid]);

		for (i = 0;i < MAX_PIPES;i++) {
			/*
			 * Line up and try to close at the same time
			 */
			miss = 1;
			while (readtsc() < race_start)
				miss = 0;

			close(pipefd[i][pid]);

			misses+= miss;
			race_start+= CLOSE_CYCLES;
		}
		races+= MAX_PIPES;

		if (!(loop & (~(~0UL << STAT_SHIFT))))
			fprintf(stderr, "%c %lu (%.2f%% false starts)\n",
				"CP"[pid], readtsc(), misses * 100. / races);

		if (pid)
			wait(NULL);	/* Parent */
		else
			exit(0);	/* Child */
	}
}
#12 lore raw

Re: [PATCH] mutexes: Add CONFIG_DEBUG_MUTEX_FASTPATH=y debug variant to debug SMP races

Quoted 4 lines · Simon Kirby

Meanwhile, I still don't understand how moving the unlock _up_ to cover less of the code can solve the race, but I will stare at your long explanation more tomorrow.

The lock we're moving up isn't the lock that actually protects the whole allocation logic (it's the lock that then protects the pipe contents when a pipe is *used*). So it's a useless lock, and moving it up is a good idea regardless (because it makes the locks only protect the parts they are actually *supposed* to protect.

And while extraneous lock wouldn't normally hurt, the sleeping locks (both mutexes and semaphores) aren't actually safe wrt de-allocation - they protect anything *inside* the lock, but the lock data structure itself is accessed racily wrt other lockers (in a way that still leaves the locked region protected, but not the lock itself). If you care about details, you can walk through my example.

Linus

#13 lore raw

Re: [PATCH] mutexes: Add CONFIG_DEBUG_MUTEX_FASTPATH=y debug variant to debug SMP races

Quoted 6 lines · Linus Torvalds

The lock we're moving up isn't the lock that actually protects the whole allocation logic (it's the lock that then protects the pipe contents when a pipe is *used*). So it's a useless lock, and moving it up is a good idea regardless (because it makes the locks only protect the parts they are actually *supposed* to protect.

Quoted 6 lines

And while extraneous lock wouldn't normally hurt, the sleeping locks (both mutexes and semaphores) aren't actually safe wrt de-allocation - they protect anything *inside* the lock, but the lock data structure itself is accessed racily wrt other lockers (in a way that still leaves the locked region protected, but not the lock itself). If you care about details, you can walk through my example.

Yes, this makes sense now. It was spin_unlock_mutex() on the pipe lock that itself was already already freed and poisoned by another cpu. This explicit poison check also fires:

arch/x86/include/asm/spinlock.h +1 -0
index bf156de..ae425d0 100644
@@ -159,6 +159,7 @@ static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
 			__ticket_unlock_slowpath(lock, prev);
 	} else
 		__add(&lock->tickets.head, TICKET_LOCK_INC, UNLOCK_LOCK_PREFIX);
+	WARN_ON(*(unsigned int *)&lock->tickets.head == 0x6b6b6b6c);
 }
 
 static inline int arch_spin_is_locked(arch_spinlock_t *lock)

It warns only as often as the poison checking already did, with a stack of warn_*, __mutex_unlock_slowpath(), mutex_unlock(), pipe_release().

Trying to prove a negative, of course, but I tested with your first fix overnight and got no errors. Current git (with b0d8d2292160bb63de) also looks good. I will leave it running for a few days.

Thanks for getting stuck on this one. It was educational, at least!

Simon-

#14 lore raw

Re: [PATCH] mutexes: Add CONFIG_DEBUG_MUTEX_FASTPATH=y debug variant to debug SMP races

In reply to Ingo Molnar
Quoted 6 lines · Ingo Molnar

Indeed: this comes from mutex->count being separate from mutex->wait_lock, and this should affect every architecture that has a mutex->count fast-path implemented (essentially every architecture that matters).

Such bugs should also magically go away with mutex debugging enabled.

Confirmed: I ran the reproducer with CONFIG_DEBUG_MUTEXES for a few hours, and never got a single poison overwritten notice.

Quoted 11 lines

I'd expect such bugs to be more prominent with unlucky object size/alignment: if mutex->count lies on a separate cache line from mutex->wait_lock.

Side note: this might be a valid light weight debugging technique, we could add padding between the two fields to force them into separate cache lines, without slowing it down.

Simon, would you be willing to try the fairly trivial patch below? Please enable CONFIG_DEBUG_MUTEX_FASTPATH=y. Does your kernel fail faster that way?

I didn't see much of a change other than the incremented poison byte is now further in due to the padding, and it shows up in kmalloc-256.

I also tried with Linus' udelay() suggestion, below. With this, there were many occurrences per second.

Simon-

kernel/mutex.c +6 -0
index d24105b..f65e735 100644
@@ -25,6 +25,7 @@
 #include <linux/spinlock.h>
 #include <linux/interrupt.h>
 #include <linux/debug_locks.h>
+#include <linux/delay.h>
 
 /*
  * In the DEBUG case we are using the "NULL fastpath" for mutexes,
@@ -740,6 +741,11 @@ __mutex_unlock_common_slowpath(atomic_t *lock_count, int nested)
 		wake_up_process(waiter->task);
 	}
 
+	/* udelay a bit if the spinlock isn't contended */
+	if (lock->wait_lock.rlock.raw_lock.tickets.head + 1 ==
+	    lock->wait_lock.rlock.raw_lock.tickets.tail)
+		udelay(1);
+
 	spin_unlock_mutex(&lock->wait_lock, flags);
 }
 
#15 lore raw

Re: [PATCH] mutexes: Add CONFIG_DEBUG_MUTEX_FASTPATH=y debug variant to debug SMP races

In reply to Ingo Molnar
Quoted 36 lines · Ingo Molnar

*
I think we try that, to make mutexes safer in general.

Can you see a way to do that fairly cheaply?

I can see two approaches, both rather radical:

1)

Eliminate mutex->count and (ab-)use mutex->wait_lock as 'the' mutex
lock: with TICKET_SLOWPATH_FLAG used to denote waiters or so and care taken to not use it as a 'real' spinlock but use the raw accessors.

This would still allow a good mutex_lock() fastpath, as it would essentially become spin_trylock() with an asm goto slow path helper perhaps.

Doing this would have various advantages:

- we'd eliminate much (all?) of per arch mutex code
- we'd share spinlock and mutex low level implementations
- we'd reduce struct mutex size by 4 bytes

It's still early in the morning so I might be missing something trivial though - this sounds suspiciously too easy ;-) Having a proper mutex slowpath might not be so easy without changing the spinlock code.

2)

Another method would be to do the opposite: eliminate mutex->wait_lock [for the non-debug case] and do everything via mutex->count and mutex->owner.

This saves even more space and potentially enables a tighter slowpath.

Quoted 10 lines

It probably won't hurt the massively parallel case, as we already do smart MCS locking via mutex->spin_mlock.

So I'd argue for #2. (Assuming it addresses the problem)

Thanks,

Ingo

I also think that #2 is safer as messing with spinlock code can be risky. However, #2 probably won't work for architectures that use the generic mutex-xchg.h fastpath. Currently the following architectures use mutex-xchg.h - unicore32, arc, arm and hexagon. Is there a reason why they cannot be converted to use mutex-dec.h instead?

-Longman