Re: [PATCH 1/2] ipc/sem.c: Fix complex_count vs. simple op race

["Holger Hoffstätte" <holger@applied-asynchrony.com>]

On Sat, 25 Jun 2016 19:37:51 +0200, Manfred Spraul wrote:

> Commit 6d07b68ce16a ("ipc/sem.c: optimize sem_lock()") introduced a
> race:
> 
> sem_lock has a fast path that allows parallel simple operations.
> There are two reasons why a simple operation cannot run in parallel:
> - a non-simple operations is ongoing (sma->sem_perm.lock held)
> - a complex operation is sleeping (sma->complex_count != 0)
> 
> As both facts are stored independently, a thread can bypass the current
> checks by sleeping in the right positions. See below for more details
> (or kernel bugzilla 105651).
> 
> The patch fixes that by creating one variable (complex_mode)
> that tracks both reasons why parallel operations are not possible.
> 
> The patch also updates stale documentation regarding the locking.
> 
> With regards to stable kernels:
> The patch is required for all kernels that include the
> commit 6d07b68ce16a ("ipc/sem.c: optimize sem_lock()") (3.10?)
> 
> The alternative is to revert the patch that introduced the race.
> 
> Background:
> Here is the race of the current implementation:
> 
> Thread A: (simple op)
> - does the first "sma->complex_count == 0" test
> 
> Thread B: (complex op)
> - does sem_lock(): This includes an array scan. But the scan can't
>   find Thread A, because Thread A does not own sem->lock yet.
> - the thread does the operation, increases complex_count,
>   drops sem_lock, sleeps
> 
> Thread A:
> - spin_lock(&sem->lock), spin_is_locked(sma->sem_perm.lock)
> - sleeps before the complex_count test
> 
> Thread C: (complex op)
> - does sem_lock (no array scan, complex_count==1)
> - wakes up Thread B.
> - decrements complex_count
> 
> Thread A:
> - does the complex_count test
> 
> Bug:
> Now both thread A and thread C operate on the same array, without
> any synchronization.
> 
> Full memory barrier are required to synchronize changes of
> complex_mode and the lock operations.
> 
> Fixes: 6d07b68ce16a ("ipc/sem.c: optimize sem_lock()")
> Reported-by: felixh@informatik.uni-bremen.de
> Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
> Cc: <stable@vger.kernel.org>

<snip>

>  
> -		/* Then check that the global lock is free */
> -		if (!spin_is_locked(&sma->sem_perm.lock)) {
> -			/*
> -			 * We need a memory barrier with acquire semantics,
> -			 * otherwise we can race with another thread that does:
> -			 *	complex_count++;
> -			 *	spin_unlock(sem_perm.lock);
> -			 */
> -			smp_acquire__after_ctrl_dep();

This won't apply to -stable because smp_acquire__after_ctrl_dep() was only
recently added. I could merge this over 4.4.x by replacing it with the previous
definition ipc_smp_acquire__after_spin_is_unlocked() (just as you did in the
first version of the patch).

hth,
Holger