LinuxLists.cc - [patch 00/62] sem2mutex: -V1

2006-01-13 12:43:53

Subject: [patch 00/62] sem2mutex: -V1

this patch-queue converts 66% of all semaphore users in 2.6.15-git9 to
mutexes.

The conversion was done by Arjan van de Ven, Jes Sorensen and myself,
via automatic tools, and the result was verified automatically as well.
Only minimal manual editing was done. We only converted semaphores that
are used as mutexes. The known "is not a mutex" list of semaphores
collected in the -rt tree in past year was automatically added to the
do-not-convert list as well. We also reviewed the resulting changes
manually, and did testbuilds and test-boots.

the GIT tree can be pulled from:

master.kernel.org/pub/scm/linux/kernel/git/mingo/mutex-2.6.git/

or:

rsync://rsync.kernel.org/pub/scm/linux/kernel/git/mingo/mutex-2.6.git/

(once master has resynced)

the patch-queue can also be downloaded from:

http://redhat.com/~mingo/generic-mutex-subsystem/

and a 'combo' patch is at:

http://redhat.com/~mingo/generic-mutex-subsystem/combo.patch

which is useful to people who'd like to test the whole patchqueue at
once.

the patch-queue has been build-tested with allyesconfig, and booted on 4
separate x86 systems.

Ingo

2006-01-13 13:00:05

by Duncan Sands

[permalink] [raw]

Subject: Re: [patch 00/62] sem2mutex: -V1

> this patch-queue converts 66% of all semaphore users in 2.6.15-git9 to
> mutexes.

Hi Ingo, the changes to drivers/usb/atm/usbatm.[ch] conflict with a bunch
of patches I just sent to Greg KH. How do you plan to handle this kind of
thing? If you like, I can tweak this part of your patch so it applies on
top of mine, and push it to Greg.

Best wishes,

Duncan.

2006-01-13 13:06:18

by Arjan van de Ven

[permalink] [raw]

Subject: Re: [patch 00/62] sem2mutex: -V1

On Fri, 2006-01-13 at 13:59 +0100, Duncan Sands wrote:
> > this patch-queue converts 66% of all semaphore users in 2.6.15-git9 to
> > mutexes.
>
> Hi Ingo, the changes to drivers/usb/atm/usbatm.[ch] conflict with a bunch
> of patches I just sent to Greg KH. How do you plan to handle this kind of
> thing? If you like, I can tweak this part of your patch so it applies on
> top of mine, and push it to Greg.

ideally you merge the patch into your queue and send it (via gregkh) on
its way to the final kernel.org merge.

This queue isn't meant to be "this is all going direct to linus
bypassing everyone"; we're trying to get as much as possible sent via
the maintainers. So if you as maintainer want to pick up a patch, we're
very happy about that!

Greetings,
Arjan van de Ven

2006-01-13 13:23:17

by Ingo Molnar

[permalink] [raw]

Subject: Re: [patch 00/62] sem2mutex: -V1

2006-01-13 13:44:09

by Ingo Molnar

[permalink] [raw]

Subject: Re: [patch 00/62] sem2mutex: -V1

* Duncan Sands <[email protected]> wrote:

> > this patch-queue converts 66% of all semaphore users in 2.6.15-git9 to
> > mutexes.
>
> Hi Ingo, the changes to drivers/usb/atm/usbatm.[ch] conflict with a
> bunch of patches I just sent to Greg KH. How do you plan to handle
> this kind of thing? If you like, I can tweak this part of your patch
> so it applies on top of mine, and push it to Greg.

yeah, the best solution from our POV is if you pick it up and send it to
Greg on your own schedule. We'll probably still carry all the patches in
our tree up until your changes upstream, because it's hard to keep track
of who does what, and we try to cover all the conversions. In general,
the faster this phase is over, the better.

we expect there to be two types of bugs introduced by these patches:

- build error - if we forgot to add mutex.h somewhere.

We think we covered most of the build issues via allyesconfig QA, but
it's possible in theory under some .config's.

- we misidentified a semaphore and converted it to mutexes, albeit the
use was not purely mutex.

all such misidentifications should trigger runtime warnings if
CONFIG_DEBUG_MUTEXES is turned on. If this happens, then one of the
following 3 scenarios should trigger:

- it should stay a semaphore (if it's a genuine counting
semaphore)

- or it should get converted to a completion (if it's used as
a completion)

- or it should get converted to struct work (if it's used as a
workflow synchronizer).

we _think_ we've identified all the converted semaphores correctly
(and we have source-code-analyzing tools to underline that belief,
plus we have a track record in -rt, which runs with all these
semaphores converted to mutexes, plus we have done our own QA), but
at 500+ files changed, it would be quite over-confident to claim that
the patch is 100% perfect :-)

another thing raises the confidence in the analysis: none of the
runtime mutex checks ever triggered during the development of this
conversion patchset. We did find a handful of bugs in drivers, but
they were all caught at the source/analysis level. We occasionally
forgot to convert some affected .c or .h modules, which errors were
caught at the build stage.

famous last words? :-)

Ingo

2006-01-13 18:25:44

by Ingo Oeser

[permalink] [raw]

Subject: Re: [patch 00/62] sem2mutex: -V1

Hi there,

On Friday 13 January 2006 14:44, Ingo Molnar wrote:
> - it should stay a semaphore (if it's a genuine counting
> semaphore)
>
> - or it should get converted to a completion (if it's used as
> a completion)
>
> - or it should get converted to struct work (if it's used as a
> workflow synchronizer).

Could we get for each of these and a mutex:

- description
- common use case
- small argument why this and nothing else should be used there

This would help driver writers a lot deciding what to use when, I think.

PS: After reading the Linux Kernel one could write a PhD thesis
just containing explanations, examples and measurements
of sychronization primitives, since Linux implements at least
most of them AFAIK :-)

Thanks & Regards

Ingo Oeser

Attachments:

(No filename) (815.00 B)
(No filename) (189.00 B)
Download all attachments

2006-01-13 19:57:19

by Ingo Molnar

[permalink] [raw]

Subject: Re: [patch 00/62] sem2mutex: -V1

* Ingo Oeser <[email protected]> wrote:

> Hi there,
>
> On Friday 13 January 2006 14:44, Ingo Molnar wrote:
> > - it should stay a semaphore (if it's a genuine counting
> > semaphore)
> >
> > - or it should get converted to a completion (if it's used as
> > a completion)
> >
> > - or it should get converted to struct work (if it's used as a
> > workflow synchronizer).
>
> Could we get for each of these and a mutex:
>
> - description
> - common use case
> - small argument why this and nothing else should be used there

like ... Documentation/mutex-design.txt?

Ingo

2006-01-13 21:04:42

by Matan Peled

[permalink] [raw]

Subject: Re: [patch 00/62] sem2mutex: -V1

Ingo Molnar wrote:
> Ingo Oeser wrote:
>> Could we get for each of these and a mutex:
>>
>> - description
>> - common use case
>> - small argument why this and nothing else should be used there
>
> like ... Documentation/mutex-design.txt?

I think what he wanted was an explanation for the change of each and every
sem... Which is kind of hard with automated tools.

--
[Name ] :: [Matan I. Peled ]
[Location ] :: [Israel ]
[Public Key] :: [0xD6F42CA5 ]
[Keyserver ] :: [keyserver.kjsl.com]
encrypted/signed plain text preferred

2006-01-13 21:26:04

by Arjan van de Ven

[permalink] [raw]

Subject: Re: [patch 00/62] sem2mutex: -V1

On Fri, 2006-01-13 at 23:04 +0200, Matan Peled wrote:
> Ingo Molnar wrote:
> > Ingo Oeser wrote:
> >> Could we get for each of these and a mutex:
> >>
> >> - description
> >> - common use case
> >> - small argument why this and nothing else should be used there
> >
> > like ... Documentation/mutex-design.txt?
>
> I think what he wanted was an explanation for the change of each and every
> sem... Which is kind of hard with automated tools.
`
it's also HIGHLY repetitive.
1) The process is : Look at semaphore and it's uses.
2) Decide it's a mutex
3) Run script to convert to mutex
4) Run script to validate the conversion
5) build+boot test

I can't think of a way to describe that uniquely different for each
one ;0

2006-01-13 22:09:56

by Junio C Hamano

[permalink] [raw]

Subject: Re: [patch 00/62] sem2mutex: -V1

Arjan van de Ven <[email protected]> writes:

> On Fri, 2006-01-13 at 23:04 +0200, Matan Peled wrote:
>> Ingo Molnar wrote:
>> > Ingo Oeser wrote:
>> >> Could we get for each of these and a mutex:
>> >>
>> >> - description
>> >> - common use case
>> >> - small argument why this and nothing else should be used there
>> >
>> > like ... Documentation/mutex-design.txt?
>>
>> I think what he wanted was an explanation for the change of each and every
>> sem... Which is kind of hard with automated tools.
> `
> it's also HIGHLY repetitive.
> 1) The process is : Look at semaphore and it's uses.
> 2) Decide it's a mutex
> 3) Run script to convert to mutex
> 4) Run script to validate the conversion
> 5) build+boot test
>
> I can't think of a way to describe that uniquely different for each
> one ;0

I do not read Ingo Oeser's request as such, but if somebody does
1) and 2), ideally, the knowledge obtained during that process,
i.e. what is being protected and what the invariants are, and
the reasoning why it is a mutex, could serve as a good
documentation for people who want to further work on that code
being converted to use mutex.

However, I think demanding Ingo (Molnar) to do all that is
unfair.

2006-01-13 22:13:33

by Arjan van de Ven

[permalink] [raw]

Subject: Re: [patch 00/62] sem2mutex: -V1

On Fri, 2006-01-13 at 14:09 -0800, Junio C Hamano wrote:
> Arjan van de Ven <[email protected]> writes:
>
> > On Fri, 2006-01-13 at 23:04 +0200, Matan Peled wrote:
> >> Ingo Molnar wrote:
> >> > Ingo Oeser wrote:
> >> >> Could we get for each of these and a mutex:
> >> >>
> >> >> - description
> >> >> - common use case
> >> >> - small argument why this and nothing else should be used there
> >> >
> >> > like ... Documentation/mutex-design.txt?
> >>
> >> I think what he wanted was an explanation for the change of each and every
> >> sem... Which is kind of hard with automated tools.
> > `
> > it's also HIGHLY repetitive.
> > 1) The process is : Look at semaphore and it's uses.
> > 2) Decide it's a mutex
> > 3) Run script to convert to mutex
> > 4) Run script to validate the conversion
> > 5) build+boot test
> >
> > I can't think of a way to describe that uniquely different for each
> > one ;0
>
> I do not read Ingo Oeser's request as such, but if somebody does
> 1) and 2), ideally, the knowledge obtained during that process,
> i.e. what is being protected and what the invariants are, and
> the reasoning why it is a mutex, could serve as a good
> documentation for people who want to further work on that code
> being converted to use mutex.

Again that is almost a generic answer, the *vast* majority of
mutex-semaphores is used in such a way that the down() and up() are
always in the same function, eg the pattern is

down(semaphore);
do_stuff();
up(semaphore);

all the time. That's then a mutex... and the most basic use pattern.
Sure this isn't always the case but it's very common.

(there have been 2 cases that accidentally did

up(semaphore);
do_stuff();
down(semaphore);

.. which is legal with semaphores but not what was intended ;)

2006-01-14 13:16:36

by Ingo Oeser

[permalink] [raw]

Subject: Re: [patch 00/62] sem2mutex: -V1

On Friday 13 January 2006 20:56, Ingo Molnar wrote:
> * Ingo Oeser <[email protected]> wrote:
> > On Friday 13 January 2006 14:44, Ingo Molnar wrote:
> > Could we get for each of these and a mutex:
> >
> > - description
> > - common use case
> > - small argument why this and nothing else should be used there
>
> like ... Documentation/mutex-design.txt?

Much simpler.

Take your favorite conversion and optionally a discussable
conversion. Now describe why mutex/completion/struct work can do
the same and still reach the same level of safety.

Sth. like extending Documentation/DocBook/kernel-locking.tmpl
which still misses completions and struct work queues,
how all works together, possible nesting and so on.

It all boils down to discussion one conversion of each type.
If one could point me to such discussions in the archives
I could write sth. up.

Regards

Ingo Oeser

Attachments:

(No filename) (893.00 B)
(No filename) (189.00 B)
Download all attachments

2006-01-14 13:22:20

by Ingo Oeser

[permalink] [raw]

Subject: Re: [patch 00/62] sem2mutex: -V1

On Friday 13 January 2006 22:04, Matan Peled wrote:
> Ingo Molnar wrote:
> > Ingo Oeser wrote:
> >> Could we get for each of these and a mutex:
> >>
> >> - description
> >> - common use case
> >> - small argument why this and nothing else should be used there
> >
> > like ... Documentation/mutex-design.txt?
>
> I think what he wanted was an explanation for the change of each and every
> sem... Which is kind of hard with automated tools.

No this is too much! I wouldn't expect this.

Just example conversions for each 3 conversion types with full discussion
(or discussion at all) like we do for all other patches would be enough.

semaphore -> mutex is explained a bit in Documentation/mutex-design.txt

Still missing:
- semaphore -> completion
- semaphore -> struct work

Regards

Ingo Oeser

Attachments:

(No filename) (810.00 B)
(No filename) (189.00 B)
Download all attachments

2006-01-14 13:31:11

by Arjan van de Ven

[permalink] [raw]

Subject: Re: [patch 00/62] sem2mutex: -V1

On Sat, 2006-01-14 at 14:16 +0100, Ingo Oeser wrote:
> On Friday 13 January 2006 20:56, Ingo Molnar wrote:
> > * Ingo Oeser <[email protected]> wrote:
> > > On Friday 13 January 2006 14:44, Ingo Molnar wrote:
> > > Could we get for each of these and a mutex:
> > >
> > > - description
> > > - common use case
> > > - small argument why this and nothing else should be used there
> >
> > like ... Documentation/mutex-design.txt?
>
> Much simpler.
>
> Take your favorite conversion

ok the most simple case is really simple.

ALL uses of it have a down() ..... ip() scenario, where all down's are
matched with up's in the same function, no trylocks in sight.

That case is the simple (and most common) case. Since it uses down()
only, it can't be irq context. (trylock could be a sign of irq context
use), and all up()'s are 1) not in irq context either because they're in
the same function as the down() which isn;t and 2) perfectly matched to
the down(), eg each down gets one up ---> perfect semaphore.

The other case on the other side of the spectrum is a down in one
function and an up in an irq function. Which is a pretty good sign of a
completion.... (same is true for a specific scenario where kernel thread
creation is involved and the up() is done in the just created thread).

2006-01-14 13:38:31

by Ingo Molnar

[permalink] [raw]

Subject: Re: [patch 00/62] sem2mutex: -V1

* Arjan van de Ven <[email protected]> wrote:

> That case is the simple (and most common) case. Since it uses down()
> only, it can't be irq context. (trylock could be a sign of irq context
> use), and all up()'s are 1) not in irq context either because they're
> in the same function as the down() which isn;t and 2) perfectly
> matched to the down(), eg each down gets one up ---> perfect
> semaphore.

one of the most frequent exceptions to the 'up in a separate function'
rule are seqfile implementations, which all have start(), mid(), stop()
methods, where start() does the down(), stop() does the up(). These can
still be converted to mutexes (and i converted a couple of them), after
manual review.

> The other case on the other side of the spectrum is a down in one
> function and an up in an irq function. Which is a pretty good sign of
> a completion.... (same is true for a specific scenario where kernel
> thread creation is involved and the up() is done in the just created
> thread).

another good sign of completion type of semaphores is the use of
DECLARE_MUTEX_LOCKED(), init_MUTEX_LOCKED(), or sema_init(&sem, 0). In
95% of these cases these signal semaphores used as completions. That is
one reason why i did not add DEFINE_MUTEX_LOCKED(), nor
mutex_init_locked() to the mutex APIs.

the 'struct work' conversion is rare, i've only seen it in XFS so far.

Ingo

2006-01-14 13:49:25

by Thomas Gleixner

[permalink] [raw]

Subject: Re: [patch 00/62] sem2mutex: -V1

Ingo,

> semaphore -> mutex is explained a bit in Documentation/mutex-design.txt
>
> Still missing:
> - semaphore -> completion

Sempahore to completion is rather simple to explain.

The pattern is mostly like this

threadA
init_MUTEX_LOCKED(&shared_data_struct.mutex);
kick_off_threadB();
down(&shared_data_struct.mutex);

threadB
wait_for_kick_off();
do_some_work();
up(&shared_data_struct.mutex);

The conversion is:

threadA
init_completion(&shared_data_struct.completion);
kick_off_threadB();
wait_for_completion(&shared_data_struct.completion);

threadB
wait_for_kick_off();
do_some_work();
complete(&shared_data_struct.completion);

Note, that a completion is only useful, when there are only two parties
involved. The one which initiates an action and the one which signals
completion of the requested action. The action can be some deferred
workload or synchronization of startup / shutdown of related threads.
Its a synchronization mechanism not a concurrency control in the sense
of data protection across multiple potential users of a data structure.

Real life example:

> --- jffs2_fs_sb.h 28 Feb 2005 08:21:06 -0000 1.51
> +++ jffs2_fs_sb.h 19 May 2005 16:12:17 -0000 1.52
> @@ -32,7 +32,7 @@
> unsigned int flags;
>
> struct task_struct *gc_task; /* GC task struct */
> - struct semaphore gc_thread_start; /* GC thread start mutex */
> + struct completion gc_thread_start; /* GC thread start completion */
> struct completion gc_thread_exit; /* GC thread exit completion port */
>
> struct semaphore alloc_sem; /* Used to protect all the following
>
>
> --- background.c 17 Mar 2005 20:15:58 -0000 1.51
> +++ background.c 19 May 2005 16:18:08 -0000 1.52
> @@ -37,7 +37,7 @@
> if (c->gc_task)
> BUG();

ThreadA

> - init_MUTEX_LOCKED(&c->gc_thread_start);
> + init_completion(&c->gc_thread_start);
> init_completion(&c->gc_thread_exit);
>
> pid = kernel_thread(jffs2_garbage_collect_thread, c, CLONE_FS|CLONE_FILES);
> @@ -48,7 +48,7 @@
> } else {
> /* Wait for it... */
> D1(printk(KERN_DEBUG "JFFS2: Garbage collect thread is pid %d\n", pid));
> - down(&c->gc_thread_start);
> + wait_for_completion(&c->gc_thread_start);
> }
>
> return ret;
> @@ -75,7 +75,7 @@
> allow_signal(SIGCONT);

ThreadB

> c->gc_task = current;
> - up(&c->gc_thread_start);
> + complete(&c->gc_thread_start);
>
> set_user_nice(current, 10);
>

Hope that helps

tglx