Hello, I am trying to understand how mutexes work in the kernel, and I think there might be a race between mutex_trylock() and mutex_unlock(). More specifically, the race is between the functions __mutex_trylock_slowpath and __mutex_unlock_common_slowpath (both defined in kernel/locking/mutex.c). Consider the following sequence of events: 0. Suppose a mutex is locked by task A and has no waiters. 1. Task B calls mutex_trylock(). 2. mutex_trylock() calls the architecture-specific __mutex_fastpath_trylock(), with __mutex_trylock_slowpath() as fail_fn. 3. According to the description of __mutex_fastpath_trylock() (for example in include/asm-generic/mutex-dec.h), "if the architecture has no effective trylock variant, it should call the fail_fn spinlock-based trylock variant unconditionally". So __mutex_fastpath_trylock() may now call __mutex_trylock_slowpath(). 4. Task A releases the mutex. 5. Task B, in __mutex_trylock_slowpath, executes: /* No need to trylock if the mutex is locked. */ if (mutex_is_locked(lock)) return 0; Since the mutex is no longer locked, the function continues. 6. Task C, which runs on a different cpu than task B, locks the mutex again. 7. Task B, in __mutex_trylock_slowpath(), continues: spin_lock_mutex(&lock->wait_lock, flags); prev = atomic_xchg(&lock->count, -1); if (likely(prev == 1)) { mutex_set_owner(lock); mutex_acquire(&lock->dep_map, 0, 1, _RET_IP_); } At this point task B holds mutex->wait_lock, prev is 0 (because there are no waiters other than task B, so the count was 0) and the mutex count is set to -1. 5. Task C calls mutex_unlock() to unlock the mutex. 6. mutex_unlock() calls the architecture-specific function __mutex_fastpath_unlock(), which fails (because the mutex count is -1), so it now calls __mutex_unlock_slowpath(), which calls __mutex_unlock_common_slowpath(). 7. __mutex_unlock_common_slowpath() sets the mutex count to 1 unconditionally, before spinning on mutex->wait_lock. 8. Task B, in __mutex_trylock_slowpath, continues: /* Set it back to 0 if there are no waiters: */ if (likely(list_empty(&lock->wait_list))) atomic_set(&lock->count, 0); spin_unlock_mutex(&lock->wait_lock, flags); return prev == 1; mutex->wait_list is still empty, so the code sets the mutex count to zero (which means the mutex is locked), releases mutex->wait_lock, and returns 0 (which means that the mutex is locked by someone else, and cannot be acquired). 9. Task C, in __mutex_unlock_common_slowpath, acquires mutex->wait_lock, unlocks it immediately (because there are no waiters to wake up) and returns. The end result is that the mutex count is 0 (locked), although the owner has just released it, and nobody else is holding the mutex. So it can no longer be acquired by anyone. Am I missing something that prevents the above scenario from happening? If not, should I post a patch that fixes it to LKML? Or is it considered too "theoretical" and cannot happen in practice? Thanks.
Hi, Le mercredi 04 mars 2015 à 02:13 +0200, Matthias Bonne a écrit :
I am trying to understand how mutexes work in the kernel, and I think there might be a race between mutex_trylock() and mutex_unlock(). More specifically, the race is between the functions __mutex_trylock_slowpath and __mutex_unlock_common_slowpath (both defined in kernel/locking/mutex.c).
Consider the following sequence of events:
0. Suppose a mutex is locked by task A and has no waiters.
1. Task B calls mutex_trylock().
2. mutex_trylock() calls the architecture-specific __mutex_fastpath_trylock(), with __mutex_trylock_slowpath() as fail_fn.
3. According to the description of __mutex_fastpath_trylock() (for example in include/asm-generic/mutex-dec.h), "if the architecture has no effective trylock variant, it should call the fail_fn spinlock-based trylock variant unconditionally". So __mutex_fastpath_trylock() may now call __mutex_trylock_slowpath().
4. Task A releases the mutex.
5. Task B, in __mutex_trylock_slowpath, executes:
/* No need to trylock if the mutex is locked. */ if (mutex_is_locked(lock)) return 0;
Since the mutex is no longer locked, the function continues.
6. Task C, which runs on a different cpu than task B, locks the mutex again.
7. Task B, in __mutex_trylock_slowpath(), continues:
spin_lock_mutex(&lock->wait_lock, flags);
prev = atomic_xchg(&lock->count, -1); if (likely(prev == 1)) { mutex_set_owner(lock); mutex_acquire(&lock->dep_map, 0, 1, _RET_IP_); }
At this point task B holds mutex->wait_lock, prev is 0 (because there are no waiters other than task B, so the count was 0) and the mutex count is set to -1.
5. Task C calls mutex_unlock() to unlock the mutex.
6. mutex_unlock() calls the architecture-specific function __mutex_fastpath_unlock(), which fails (because the mutex count is -1), so it now calls __mutex_unlock_slowpath(), which calls __mutex_unlock_common_slowpath().
7. __mutex_unlock_common_slowpath() sets the mutex count to 1 unconditionally, before spinning on mutex->wait_lock.
8. Task B, in __mutex_trylock_slowpath, continues:
/* Set it back to 0 if there are no waiters: */ if (likely(list_empty(&lock->wait_list))) atomic_set(&lock->count, 0);
spin_unlock_mutex(&lock->wait_lock, flags);
return prev == 1;
mutex->wait_list is still empty, so the code sets the mutex count to zero (which means the mutex is locked), releases mutex->wait_lock, and returns 0 (which means that the mutex is locked by someone else, and cannot be acquired).
9. Task C, in __mutex_unlock_common_slowpath, acquires mutex->wait_lock, unlocks it immediately (because there are no waiters to wake up) and returns.
The end result is that the mutex count is 0 (locked), although the owner has just released it, and nobody else is holding the mutex. So it can no longer be acquired by anyone.
Am I missing something that prevents the above scenario from happening? If not, should I post a patch that fixes it to LKML? Or is it considered too "theoretical" and cannot happen in practice?
I haven't looked at your explanations, you should have come with a reproductible test case to demonstrate the issue (involving slowing down one CPU ?). Anyway, such deep knowledge on the mutex implementation has to be found on lkml. Regards. -- Yann Droneaud OPTEYA
On Tue, 10 Mar 2015 14:03:59 +0100, Yann Droneaud said:
Consider the following sequence of events:
0. Suppose a mutex is locked by task A and has no waiters.
1. Task B calls mutex_trylock().
2. mutex_trylock() calls the architecture-specific __mutex_fastpath_trylock(), with __mutex_trylock_slowpath() as fail_fn.
3. According to the description of __mutex_fastpath_trylock() (for example in include/asm-generic/mutex-dec.h), "if the architecture has no effective trylock variant, it should call the fail_fn spinlock-based trylock variant unconditionally". So __mutex_fastpath_trylock() may now call __mutex_trylock_slowpath().
4. Task A releases the mutex.
5. Task B, in __mutex_trylock_slowpath, executes:
/* No need to trylock if the mutex is locked. */ if (mutex_is_locked(lock)) return 0;
Since the mutex is no longer locked, the function continues.
6. Task C, which runs on a different cpu than task B, locks the mutex again.
7. Task B, in __mutex_trylock_slowpath(), continues:
spin_lock_mutex(&lock->wait_lock, flags);
B will spin here until C releases the lock. When that spin exits, C no longer holds the lock. Re-do the analysis from this point.
On 03/10/15 16:59, Valdis.Kletnieks@vt.edu wrote:
On Tue, 10 Mar 2015 14:03:59 +0100, Yann Droneaud said:
Consider the following sequence of events:
0. Suppose a mutex is locked by task A and has no waiters.
1. Task B calls mutex_trylock().
2. mutex_trylock() calls the architecture-specific __mutex_fastpath_trylock(), with __mutex_trylock_slowpath() as fail_fn.
3. According to the description of __mutex_fastpath_trylock() (for example in include/asm-generic/mutex-dec.h), "if the architecture has no effective trylock variant, it should call the fail_fn spinlock-based trylock variant unconditionally". So __mutex_fastpath_trylock() may now call __mutex_trylock_slowpath().
4. Task A releases the mutex.
5. Task B, in __mutex_trylock_slowpath, executes:
/* No need to trylock if the mutex is locked. */ if (mutex_is_locked(lock)) return 0;
Since the mutex is no longer locked, the function continues.
6. Task C, which runs on a different cpu than task B, locks the mutex again.
7. Task B, in __mutex_trylock_slowpath(), continues:
spin_lock_mutex(&lock->wait_lock, flags);
B will spin here until C releases the lock.
When that spin exits, C no longer holds the lock. Re-do the analysis from this point.
Thank you for the review. I don't think B waits for C here - C holds the mutex (lock), not the internal spinlock (lock->wait_lock). I might be wrong though.
On 03/10/15 15:03, Yann Droneaud wrote:
Hi,
Le mercredi 04 mars 2015 à 02:13 +0200, Matthias Bonne a écrit :
I am trying to understand how mutexes work in the kernel, and I think there might be a race between mutex_trylock() and mutex_unlock(). More specifically, the race is between the functions __mutex_trylock_slowpath and __mutex_unlock_common_slowpath (both defined in kernel/locking/mutex.c).
Consider the following sequence of events:
[...]
The end result is that the mutex count is 0 (locked), although the owner has just released it, and nobody else is holding the mutex. So it can no longer be acquired by anyone.
Am I missing something that prevents the above scenario from happening? If not, should I post a patch that fixes it to LKML? Or is it considered too "theoretical" and cannot happen in practice?
I haven't looked at your explanations, you should have come with a reproductible test case to demonstrate the issue (involving slowing down one CPU ?).
Anyway, such deep knowledge on the mutex implementation has to be found on lkml.
Regards.
Thank you for your suggestions, and sorry for the long delay. I see now that my explanation was unneccesarily complex. The problem is this code from __mutex_trylock_slowpath(): spin_lock_mutex(&lock->wait_lock, flags); prev = atomic_xchg(&lock->count, -1); if (likely(prev == 1)) { mutex_set_owner(lock); mutex_acquire(&lock->dep_map, 0, 1, _RET_IP_); } /* Set it back to 0 if there are no waiters: */ if (likely(list_empty(&lock->wait_list))) atomic_set(&lock->count, 0); spin_unlock_mutex(&lock->wait_lock, flags); return prev == 1; The above code assumes that the mutex cannot be unlocked while the spinlock is held. However, mutex_unlock() sets the mutex count to 1 before taking the spinlock (even in the slowpath). If this happens between the atomic_xchg() and the atomic_set() above, and the mutex has no waiters, then the atomic_set() will set the mutex count back to 0 after it has been unlocked by mutex_unlock(), but mutex_trylock() will still return failure. So the mutex will remain locked forever. I don't know how to write a test case to demonstrate the issue, because this race is very hard to trigger in practice: the mutex needs to be locked immediately before the spinlock is acquired, and unlocked in the very short interval between atomic_xchg() and atomic_set(). It also requires that CONFIG_DEBUG_MUTEXES be set, since AFAICT the mutex debugging code is currently the only user of __mutex_trylock_slowpath. This is why I asked if it is acceptable to submit a patch for such hard-to-trigger problems. I think I will just send a fix. Any further suggestions or guidance would be appreciated.
On Sun, 2015-03-15 at 01:05 +0200, Matthias Bonne wrote:
On 03/10/15 15:03, Yann Droneaud wrote:
Hi,
Le mercredi 04 mars 2015 à 02:13 +0200, Matthias Bonne a écrit :
I am trying to understand how mutexes work in the kernel, and I think there might be a race between mutex_trylock() and mutex_unlock(). More specifically, the race is between the functions __mutex_trylock_slowpath and __mutex_unlock_common_slowpath (both defined in kernel/locking/mutex.c).
Consider the following sequence of events:
[...]
The end result is that the mutex count is 0 (locked), although the owner has just released it, and nobody else is holding the mutex. So it can no longer be acquired by anyone.
Am I missing something that prevents the above scenario from happening? If not, should I post a patch that fixes it to LKML? Or is it considered too "theoretical" and cannot happen in practice?
I haven't looked at your explanations, you should have come with a reproductible test case to demonstrate the issue (involving slowing down one CPU ?).
Anyway, such deep knowledge on the mutex implementation has to be found on lkml.
Regards.
Thank you for your suggestions, and sorry for the long delay.
I see now that my explanation was unneccesarily complex. The problem is this code from __mutex_trylock_slowpath():
spin_lock_mutex(&lock->wait_lock, flags);
prev = atomic_xchg(&lock->count, -1); if (likely(prev == 1)) { mutex_set_owner(lock); mutex_acquire(&lock->dep_map, 0, 1, _RET_IP_); }
/* Set it back to 0 if there are no waiters: */ if (likely(list_empty(&lock->wait_list))) atomic_set(&lock->count, 0);
spin_unlock_mutex(&lock->wait_lock, flags);
return prev == 1;
The above code assumes that the mutex cannot be unlocked while the spinlock is held. However, mutex_unlock() sets the mutex count to 1 before taking the spinlock (even in the slowpath). If this happens between the atomic_xchg() and the atomic_set() above, and the mutex has no waiters, then the atomic_set() will set the mutex count back to 0 after it has been unlocked by mutex_unlock(), but mutex_trylock() will still return failure. So the mutex will remain locked forever.
Good analysis, but not quite accurate for one simple fact: mutex trylocks _only_ use fastpaths (obviously just depend on the counter cmpxchg to 0), so you never fallback to the slowpath you are mentioning, thus the race is non existent. Please see the arch code.
On Sat, 2015-03-14 at 18:03 -0700, Davidlohr Bueso wrote:
Good analysis, but not quite accurate for one simple fact: mutex trylocks _only_ use fastpaths (obviously just depend on the counter cmpxchg to 0), so you never fallback to the slowpath you are mentioning, thus the race is non existent. Please see the arch code.
For debug we use the trylock slowpath, but so does everything else, so again you cannot hit this scenario.
participants (4)
-
Davidlohr Bueso -
Matthias Bonne -
Valdis.Kletnieks＠vt.edu -
Yann Droneaud