Found it! (was Re: [3.10] Oopses in kmem_cache_allocate() via prepare_creds())
Subsystems (4)
Quoted 4 lines · Linus Torvalds
I still don't see what could be wrong with the
pipe_inode_infothing, 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
@@ -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;
Quoted 68 lines · Linus Torvalds
Quoted 4 lines · Linus Torvalds
I still don't see what could be wrong with the
pipe_inode_infothing, 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->filesaccesses (sincepipe->filesis protected byinode->i_lock, not the pipe lock), so the solution is to just do the__pipe_unlock()before the whole dance about thepipe->filesreference 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_PAGEALLOCdidn't catch it" (because the access happens just as it is released, andDEBUG_PAGEALLOCtakes 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@@ -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
Al Viro
maintainerQuoted 11 lines · Ingo Molnar
It's not like there should be many (any?) VFS operations where a pipe is used via
i_mutexandpipe->mutexin 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->mutexand rely oni_mutexas before?
You are missing the extra shitloads of complexity in ->i_mutex ordering, and ->i_mutex is already used for too many things...
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_mutexandpipe->mutexin 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->mutexand rely oni_mutexas 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
Al Viro
maintainerQuoted 48 lines · Linus Torvalds
Quoted 4 lines · Linus Torvalds
I still don't see what could be wrong with the
pipe_inode_infothing, 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->filesaccesses (sincepipe->filesis protected byinode->i_lock, not the pipe lock), so the solution is to just do the__pipe_unlock()before the whole dance about thepipe->filesreference 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_PAGEALLOCdidn't catch it" (because the access happens just as it is released, andDEBUG_PAGEALLOCtakes 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...
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
Al Viro
maintainerQuoted 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...
Al Viro
maintainergfs2 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_blockand 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...
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_blockand 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/.../freezejust as we enter that ->put_super() (or at any point starting from the moment whendeactivate_locked_super()has dropped the last active reference)? This:
staticssize_tfreeze_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:
intfreeze_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()infreeze_super()(and failing if it fails) would've worked, but it doesn't help with the deadlock - just write "0" instead and we hitthaw_super(), which starts with grabbing ->s_umount. atomic_inc_not_zero()/deactivate_super() around that call ofthaw_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.
PATCH 1/1 mutexes: Add CONFIG_DEBUG_MUTEX_FASTPATH=y debug variant to debug SMP races
In reply to Linus TorvaldsQuoted 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
@@ -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
@@ -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
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->countlies on a separate cache line frommutex->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->mutexconversions 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
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->countlies on a separate cache line frommutex->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 thespin_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 */
}
}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
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
@@ -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-
Re: [PATCH] mutexes: Add CONFIG_DEBUG_MUTEX_FASTPATH=y debug variant to debug SMP races
In reply to Ingo MolnarQuoted 6 lines · Ingo Molnar
Indeed: this comes from
mutex->countbeing separate frommutex->wait_lock, and this should affect every architecture that has amutex->countfast-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->countlies on a separate cache line frommutex->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
@@ -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); }
Re: [PATCH] mutexes: Add CONFIG_DEBUG_MUTEX_FASTPATH=y debug variant to debug SMP races
In reply to Ingo MolnarQuoted 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->countand (ab-)usemutex->wait_lockas 'the' mutex
lock: withTICKET_SLOWPATH_FLAGused 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 becomespin_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 bytesIt'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 viamutex->countandmutex->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