Problems with semaphores, mutexes, and atomic?

Problems with semaphores, mutexes, and atomic?

[Dave Hylands]

Hi,

I wrote a small test module to test semaphores, mutexes and atomic
increments, and I've tested it with CONFIG_SMP=y with 1 and 2
processors and with CONFIG_SMP disabled.

My test code can be found here:
http://svn.hylands.org/linux/test-mutex/test-mutex.c
(it's about 133 lines long).

For each test, I launch 100 threads, and then increment a counter,
either inside a mutex_lock/unlock, a down/up, or do an atomic_inc.

Each thread performs the loop a number of times, and at the end the
count often doesn't have the expected value if the locks were in fact
atomic.

Typical output looks like:

192.168.0.50  ~ # modprobe test-mutex
[   26.220000] Testing mutex...
[   26.230000]     Launching threads ..........
[   26.300000]     Waiting for threads to finish ..........
[   26.310000]   counter = 999888 FAIL
[   26.310000] Testing semaphore...
[   26.310000]     Launching threads ..........
[   26.440000]     Waiting for threads to finish ..........
[   27.810000]   counter = 999575 FAIL
[   27.810000] Testing atomic...
[   27.820000]     Launching threads ..........
[   28.030000]     Waiting for threads to finish ..........
[   28.040000]  counter = 9910929 FAIL

My processor info from /proc/cpuinfo looks like:

192.168.0.50  ~ # cat /proc/cpuinfo
Processor       : ARMv7 Processor rev 5 (v7l)
processor       : 0
BogoMIPS        : 1893.99

processor       : 1
BogoMIPS        : 1893.99

Features        : swp half thumb fastmult vfp edsp neon vfpv3
CPU implementer : 0x41
CPU architecture: 7
CPU variant     : 0x2
CPU part        : 0xc09
CPU revision    : 5

I'm running 2.6.36.3, and some snippets from my boot log:

Uncompressing Linux... done, booting the kernel.
Linux version 2.6.36.3 (dhylands at dave-ubuntu) (gcc version 4.5.1 (GCC)
) #40 SMP PREEMPT Sun Jun 19 13:41:47 PDT 2011
CPU: ARMv7 Processor [412fc095] revision 5 (ARMv7), cr=10c53c7f
CPU: VIPT nonaliasing data cache, VIPT aliasing instruction cache

[    0.280000] CPU: Testing write buffer coherency: ok
[    0.280000] Calibrating local timer... 474.46MHz.
[    0.340000] L310 cache controller enabled
[    0.340000] l2x0: 16 ways, CACHE_ID 0x410000c7, AUX_CTRL 0x7a450000

So given that I'm seeing failures even with CONFIG_SMP disabled, I
have to wonder whether my test is valid, or whether our SoC has issues
some where.

I even tried adding:

    smp_mb();
    dsb();

after acquiring the lock and before releasing the lock, but I still
see failures.

Any feedback would be appreciated, and I can provide more information,
if needed.

-- 
Dave Hylands
Shuswap, BC, Canada
http://www.davehylands.com

Problems with semaphores, mutexes, and atomic?

[saeed bishara]

On Mon, Jun 20, 2011 at 9:39 AM, Dave Hylands <dhylands@gmail.com> wrote:
> Hi,
>
> I wrote a small test module to test semaphores, mutexes and atomic
> increments, and I've tested it with CONFIG_SMP=y with 1 and 2
> processors and with CONFIG_SMP disabled.
>
> My test code can be found here:
> http://svn.hylands.org/linux/test-mutex/test-mutex.c
> (it's about 133 lines long).
yout code is not complete, the DEFINE_SEMAPHORE and DEFINE_SEMAPHORE
definitions are missing
saeed
>

Problems with semaphores, mutexes, and atomic?

[Dave Hylands]

Hi Saeed,

On Mon, Jun 20, 2011 at 12:20 AM, saeed bishara <saeed.bishara@gmail.com> wrote:
> On Mon, Jun 20, 2011 at 9:39 AM, Dave Hylands <dhylands@gmail.com> wrote:
>> Hi,
>>
>> I wrote a small test module to test semaphores, mutexes and atomic
>> increments, and I've tested it with CONFIG_SMP=y with 1 and 2
>> processors and with CONFIG_SMP disabled.
>>
>> My test code can be found here:
>> http://svn.hylands.org/linux/test-mutex/test-mutex.c
>> (it's about 133 lines long).
> yout code is not complete, the DEFINE_SEMAPHORE and DEFINE_SEMAPHORE
> definitions are missing

I don't follow. Line 7 & 8 has

DEFINE_MUTEX( lock );
DEFINE_SEMAPHORE( sem_lock );

and line 19 has

DEFINE_SEMAPHORE( thread_wait );

-- 
Dave Hylands
Shuswap, BC, Canada
http://www.davehylands.com

Problems with semaphores, mutexes, and atomic?

[Arnd Bergmann]

On Monday 20 June 2011 09:44:16 Dave Hylands wrote:
> On Mon, Jun 20, 2011 at 12:20 AM, saeed bishara <saeed.bishara@gmail.com> wrote:
> > On Mon, Jun 20, 2011 at 9:39 AM, Dave Hylands <dhylands@gmail.com> wrote:
> >> Hi,
> >>
> >> I wrote a small test module to test semaphores, mutexes and atomic
> >> increments, and I've tested it with CONFIG_SMP=y with 1 and 2
> >> processors and with CONFIG_SMP disabled.
> >>
> >> My test code can be found here:
> >> http://svn.hylands.org/linux/test-mutex/test-mutex.c
> >> (it's about 133 lines long).
> > yout code is not complete, the DEFINE_SEMAPHORE and DEFINE_SEMAPHORE
> > definitions are missing
> 
> I don't follow. Line 7 & 8 has
> 
> DEFINE_MUTEX( lock );
> DEFINE_SEMAPHORE( sem_lock );
> 
> and line 19 has
> 
> DEFINE_SEMAPHORE( thread_wait );

DEFINE_SEMAPHORE needs another argument, your code won't compile.

You should basically never use semaphores anyway. In order to wait
for a kthread to finish, use kthread_stop(). Do not use a semaphore
when you want a mutex.

	Arnd

Problems with semaphores, mutexes, and atomic?

[Dave Hylands]

Hi Arnd,

On Mon, Jun 20, 2011 at 1:03 AM, Arnd Bergmann <arnd@arndb.de> wrote:
> On Monday 20 June 2011 09:44:16 Dave Hylands wrote:
>> On Mon, Jun 20, 2011 at 12:20 AM, saeed bishara <saeed.bishara@gmail.com> wrote:
>> > On Mon, Jun 20, 2011 at 9:39 AM, Dave Hylands <dhylands@gmail.com> wrote:
>> >> Hi,
>> >>
>> >> I wrote a small test module to test semaphores, mutexes and atomic
>> >> increments, and I've tested it with CONFIG_SMP=y with 1 and 2
>> >> processors and with CONFIG_SMP disabled.
>> >>
>> >> My test code can be found here:
>> >> http://svn.hylands.org/linux/test-mutex/test-mutex.c
>> >> (it's about 133 lines long).
>> > yout code is not complete, the DEFINE_SEMAPHORE and DEFINE_SEMAPHORE
>> > definitions are missing
>>
>> I don't follow. Line 7 & 8 has
>>
>> DEFINE_MUTEX( lock );
>> DEFINE_SEMAPHORE( sem_lock );
>>
>> and line 19 has
>>
>> DEFINE_SEMAPHORE( thread_wait );
>
> DEFINE_SEMAPHORE needs another argument, your code won't compile.

As far as I can tell, DEFINE_SEMAPHORE takes exactly one argument (I
checked 2.6.36.3 and 2.6.39)
http://lxr.linux.no/linux+v2.6.36.3/include/linux/semaphore.h#L29

My code compiles just fine (no errors, no warnings).

> You should basically never use semaphores anyway.

The purpose was to test if semaphores were in fact atomic. Semaphores
have their uses, and I agree, the test code doesn't demonstrate the
best way to increment a counter, but that's not the intention of the
test code.

> In order to wait
> for a kthread to finish, use kthread_stop(). Do not use a semaphore
> when you want a mutex.

That doesn't make sense. I don't want to stop the child thread, I want
to wait until it's finished.

If I were to put checks in the loop with calls to kthread_should_stop,
then calling kthread_stop would make the thread stop early, which is
not what I'm trying to do. What I wanted was something equivalent to
pthread_join in user space, and the kthread_api doesn't appear to
offer any function with that functionality.

I don't see how you could use a mutex to achieve the same thing.

I agree that kthread_stop would have worked in this particular
instance, but I really consider that to be a misuse of the function,
and it certainly wouldn't work in the general case.

-- 
Dave Hylands
Shuswap, BC, Canada
http://www.davehylands.com

Problems with semaphores, mutexes, and atomic?

[Russell King - ARM Linux]

On Sun, Jun 19, 2011 at 11:39:49PM -0700, Dave Hylands wrote:
> Each thread performs the loop a number of times, and at the end the
> count often doesn't have the expected value if the locks were in fact
> atomic.
> 
> Typical output looks like:
> 
> 192.168.0.50  ~ # modprobe test-mutex
> [   26.220000] Testing mutex...
> [   26.230000]     Launching threads ..........
> [   26.300000]     Waiting for threads to finish ..........
> [   26.310000]   counter = 999888 FAIL
> [   26.310000] Testing semaphore...
> [   26.310000]     Launching threads ..........
> [   26.440000]     Waiting for threads to finish ..........
> [   27.810000]   counter = 999575 FAIL
> [   27.810000] Testing atomic...
> [   27.820000]     Launching threads ..........
> [   28.030000]     Waiting for threads to finish ..........
> [   28.040000]  counter = 9910929 FAIL

The answer is quite simple.  You're not waiting for all the threads to
finish.  The first down(&thread_wait) will succeed, so the values you're
getting above could be up to 100000 (NUM_ATOMIC_ITER) out.  And they
are.

Problems with semaphores, mutexes, and atomic?

[Arnd Bergmann]

On Monday 20 June 2011 10:21:27 Dave Hylands wrote:

> >> DEFINE_SEMAPHORE( thread_wait );
> >
> > DEFINE_SEMAPHORE needs another argument, your code won't compile.
> 
> As far as I can tell, DEFINE_SEMAPHORE takes exactly one argument (I
> checked 2.6.36.3 and 2.6.39)
> http://lxr.linux.no/linux+v2.6.36.3/include/linux/semaphore.h#L29
> 
> My code compiles just fine (no errors, no warnings).

Ah, sorry about that, yes. sema_init() takes two arguments, and I got
confused because hardly anything uses DEFINE_SEMAPHORE these days
as we're removing all semaphores from the kernel in order to deprecate
the API.

> > You should basically never use semaphores anyway.
> 
> The purpose was to test if semaphores were in fact atomic. Semaphores
> have their uses, and I agree, the test code doesn't demonstrate the
> best way to increment a counter, but that's not the intention of the
> test code.

They are atomic. Further inspection of your code shows that your
semaphore never sleeps, because you only ever down() it once.

> > In order to wait
> > for a kthread to finish, use kthread_stop(). Do not use a semaphore
> > when you want a mutex.
> 
> That doesn't make sense. I don't want to stop the child thread, I want
> to wait until it's finished.

But in your example, the kthread doesn't ever check kthread_should_stop(),
so kthread_stop is not stopping it at all, it just waits for it to complete.
This simple example (where the kthread doesn't stop) would be better
served by a work queue (schedule_work) than a kthread, however.

> If I were to put checks in the loop with calls to kthread_should_stop,
> then calling kthread_stop would make the thread stop early, which is
> not what I'm trying to do. What I wanted was something equivalent to
> pthread_join in user space, and the kthread_api doesn't appear to
> offer any function with that functionality.

That is what is commonly called a completion. You initialize it
before you hand off code to the other thread and then call
complete() in the other thread, but wait_for_completion() in the
waiter. This is of course what kthread_stop does internally,
besides setting the should_stop variable(). You might argue
that it would be good to also have a kthread_wait() function that
does the same as kthread_stop() without setting that bit.

Feel free to submit a patch for that if you can identify a few
drivers that would benefit from that interface.

> I don't see how you could use a mutex to achieve the same thing.
> 
> I agree that kthread_stop would have worked in this particular
> instance, but I really consider that to be a misuse of the function,
> and it certainly wouldn't work in the general case.

Using a semaphore instead of a completion is also a misuse ;-)

	Arnd

Problems with semaphores, mutexes, and atomic?

[Dave Hylands]

Hi Russell,

On Mon, Jun 20, 2011 at 1:27 AM, Russell King - ARM Linux
<linux@arm.linux.org.uk> wrote:
> On Sun, Jun 19, 2011 at 11:39:49PM -0700, Dave Hylands wrote:
>> Each thread performs the loop a number of times, and at the end the
>> count often doesn't have the expected value if the locks were in fact
>> atomic.
>>
>> Typical output looks like:
>>
>> 192.168.0.50 ?~ # modprobe test-mutex
>> [ ? 26.220000] Testing mutex...
>> [ ? 26.230000] ? ? Launching threads ..........
>> [ ? 26.300000] ? ? Waiting for threads to finish ..........
>> [ ? 26.310000] ? counter = 999888 FAIL
>> [ ? 26.310000] Testing semaphore...
>> [ ? 26.310000] ? ? Launching threads ..........
>> [ ? 26.440000] ? ? Waiting for threads to finish ..........
>> [ ? 27.810000] ? counter = 999575 FAIL
>> [ ? 27.810000] Testing atomic...
>> [ ? 27.820000] ? ? Launching threads ..........
>> [ ? 28.030000] ? ? Waiting for threads to finish ..........
>> [ ? 28.040000] ?counter = 9910929 FAIL
>
> The answer is quite simple. ?You're not waiting for all the threads to
> finish. ?The first down(&thread_wait) will succeed, so the values you're
> getting above could be up to 100000 (NUM_ATOMIC_ITER) out. ?And they
> are.

Thank you. My sanity has been restored.

I added a down on thread_wait in the init routine, and now all of test
cases pass for all of the variations (CONFIG_SMP=n, CONFIG_SMP=y, with
1 or 2 processors).

Now I need to dig deeper to find the real reason why my original code,
which prompted me to go down this path is failing.

-- 
Dave Hylands
Shuswap, BC, Canada
http://www.davehylands.com

Problems with semaphores, mutexes, and atomic?

[Dave Hylands]

Hi Arnd,

On Mon, Jun 20, 2011 at 1:34 AM, Arnd Bergmann <arnd@arndb.de> wrote:
> On Monday 20 June 2011 10:21:27 Dave Hylands wrote:
...snip...
>> The purpose was to test if semaphores were in fact atomic. Semaphores
>> have their uses, and I agree, the test code doesn't demonstrate the
>> best way to increment a counter, but that's not the intention of the
>> test code.
>
> They are atomic. Further inspection of your code shows that your
> semaphore never sleeps, because you only ever down() it once.

So I was using the "implement a mutex using a semaphore". Since there
are upto 100 threads running, some of them will sleep on the down. The
real issues was discovered by Russell. I was missing a down on the
thread_wait, since DEFINE_SEMAPHORE initializes the semaphore with a
count of 1, which my code wasn't compensating for.

>> > In order to wait
>> > for a kthread to finish, use kthread_stop(). Do not use a semaphore
>> > when you want a mutex.
>>
>> That doesn't make sense. I don't want to stop the child thread, I want
>> to wait until it's finished.
>
> But in your example, the kthread doesn't ever check kthread_should_stop(),
> so kthread_stop is not stopping it at all, it just waits for it to complete.
> This simple example (where the kthread doesn't stop) would be better
> served by a work queue (schedule_work) than a kthread, however.
>
>> If I were to put checks in the loop with calls to kthread_should_stop,
>> then calling kthread_stop would make the thread stop early, which is
>> not what I'm trying to do. What I wanted was something equivalent to
>> pthread_join in user space, and the kthread_api doesn't appear to
>> offer any function with that functionality.
>
> That is what is commonly called a completion. You initialize it
> before you hand off code to the other thread and then call
> complete() in the other thread, but wait_for_completion() in the
> waiter. This is of course what kthread_stop does internally,
> besides setting the should_stop variable(). You might argue
> that it would be good to also have a kthread_wait() function that
> does the same as kthread_stop() without setting that bit.

So in order to use completions, I would have had to create one
completion per thread, whereas using a semaphore, I only had to create
one semaphore period.

> Feel free to submit a patch for that if you can identify a few
> drivers that would benefit from that interface.

Right now, I don't have any examples, and even my example was
contrived, as it was just to write some test code to verify that
nothing funny was going on.

>> I don't see how you could use a mutex to achieve the same thing.
>>
>> I agree that kthread_stop would have worked in this particular
>> instance, but I really consider that to be a misuse of the function,
>> and it certainly wouldn't work in the general case.
>
> Using a semaphore instead of a completion is also a misuse ;-)

Yeah - I could agree with that. When I wrote the code, using
completions never really occurred to me, even though that's what I
normally use when waiting for something like a DMA to finish.

I'm happy to discover it was a bug in my test code and not a bug in
the kernel. I apologize for wasting everybody's time.

-- 
Dave Hylands
Shuswap, BC, Canada
http://www.davehylands.com

Problems with semaphores, mutexes, and atomic?

[Hesham Mahmoud]

Dave Hylands <dhylands <at> gmail.com> writes:

> 
> Hi,
> 
> I wrote a small test module to test semaphores, mutexes and atomic
> increments, and I've tested it with CONFIG_SMP=y with 1 and 2
> processors and with CONFIG_SMP disabled.
> 
> My test code can be found here:
> http://svn.hylands.org/linux/test-mutex/test-mutex.c
> (it's about 133 lines long).
> 
> For each test, I launch 100 threads, and then increment a counter,
> either inside a mutex_lock/unlock, a down/up, or do an atomic_inc.
> 
> Each thread performs the loop a number of times, and at the end the
> count often doesn't have the expected value if the locks were in fact
> atomic.
> 
> Typical output looks like:
> 
> 192.168.0.50  ~ # modprobe test-mutex
> [   26.220000] Testing mutex...
> [   26.230000]     Launching threads ..........
> [   26.300000]     Waiting for threads to finish ..........
> [   26.310000]   counter = 999888 FAIL
> [   26.310000] Testing semaphore...
> [   26.310000]     Launching threads ..........
> [   26.440000]     Waiting for threads to finish ..........
> [   27.810000]   counter = 999575 FAIL
> [   27.810000] Testing atomic...
> [   27.820000]     Launching threads ..........
> [   28.030000]     Waiting for threads to finish ..........
> [   28.040000]  counter = 9910929 FAIL
> 
> My processor info from /proc/cpuinfo looks like:
> 
> 192.168.0.50  ~ # cat /proc/cpuinfo
> Processor       : ARMv7 Processor rev 5 (v7l)
> processor       : 0
> BogoMIPS        : 1893.99
> 
> processor       : 1
> BogoMIPS        : 1893.99
> 
> Features        : swp half thumb fastmult vfp edsp neon vfpv3
> CPU implementer : 0x41
> CPU architecture: 7
> CPU variant     : 0x2
> CPU part        : 0xc09
> CPU revision    : 5
> 
> I'm running 2.6.36.3, and some snippets from my boot log:
> 
> Uncompressing Linux... done, booting the kernel.
> Linux version 2.6.36.3 (dhylands <at> dave-ubuntu) (gcc version 4.5.1 (GCC)
> ) #40 SMP PREEMPT Sun Jun 19 13:41:47 PDT 2011
> CPU: ARMv7 Processor [412fc095] revision 5 (ARMv7), cr=10c53c7f
> CPU: VIPT nonaliasing data cache, VIPT aliasing instruction cache
> 
> [    0.280000] CPU: Testing write buffer coherency: ok
> [    0.280000] Calibrating local timer... 474.46MHz.
> [    0.340000] L310 cache controller enabled
> [    0.340000] l2x0: 16 ways, CACHE_ID 0x410000c7, AUX_CTRL 0x7a450000
> 
> So given that I'm seeing failures even with CONFIG_SMP disabled, I
> have to wonder whether my test is valid, or whether our SoC has issues
> some where.
> 
> I even tried adding:
> 
>     smp_mb();
>     dsb();
> 
> after acquiring the lock and before releasing the lock, but I still
> see failures.
> 
> Any feedback would be appreciated, and I can provide more information,
> if needed.
> 

I ran this test on a PC. It gave me a FAILED result. I fixed it by
initializing the thread_Wait semaphore to locked state. It worked fine.

Failed:

Jul 16 02:57:12 ubuntu kernel: [ 1837.858846] Testing mutex...
Jul 16 02:57:12 ubuntu kernel: [ 1837.858868]     Launching threads .
Jul 16 02:57:12 ubuntu kernel: [ 1837.876590]     Waiting for threads to
finish .
Jul 16 02:57:12 ubuntu kernel: [ 1837.876652]   counter = 90000 FAIL
Jul 16 02:57:12 ubuntu kernel: [ 1837.876660] Testing semaphore...
Jul 16 02:57:12 ubuntu kernel: [ 1837.876688]     Launching threads .
Jul 16 02:57:12 ubuntu kernel: [ 1837.901929]     Waiting for threads to
finish .
Jul 16 02:57:12 ubuntu kernel: [ 1837.901956]   counter = 90000 FAIL
Jul 16 02:57:12 ubuntu kernel: [ 1837.901966] Testing atomic...
Jul 16 02:57:12 ubuntu kernel: [ 1837.901974]     Launching threads .
Jul 16 02:57:12 ubuntu kernel: [ 1837.931911]     Waiting for threads to
finish .
Jul 16 02:57:12 ubuntu kernel: [ 1837.931938]  counter = 900000 FAIL


Passed:
Jul 16 03:08:22 ubuntu kernel: [ 2507.982633] test_mutex_exit: called
Jul 16 03:11:06 ubuntu kernel: [ 2671.515674] Testing mutex...
Jul 16 03:11:06 ubuntu kernel: [ 2671.515700]     Launching threads ..........
Jul 16 03:11:06 ubuntu kernel: [ 2671.607958]     Waiting for threads to
finish ..........
Jul 16 03:11:06 ubuntu kernel: [ 2671.609115]   counter = 1000000 Pass
Jul 16 03:11:06 ubuntu kernel: [ 2671.609125] Testing semaphore...
Jul 16 03:11:06 ubuntu kernel: [ 2671.609153]     Launching threads ..........
Jul 16 03:11:06 ubuntu kernel: [ 2671.743826]     Waiting for threads to
finish ..........
Jul 16 03:11:06 ubuntu kernel: [ 2671.745109]   counter = 1000000 Pass
Jul 16 03:11:06 ubuntu kernel: [ 2671.745119] Testing atomic...
Jul 16 03:11:06 ubuntu kernel: [ 2671.745127]     Launching threads ..........
Jul 16 03:11:06 ubuntu kernel: [ 2671.950545]     Waiting for threads to
finish ..........
Jul 16 03:11:06 ubuntu kernel: [ 2671.952532]  counter = 10000000 Pass

$ uname -r
2.6.32-34-generic

Thanks,
-Hesham