malloc/free and priority inheritance?

malloc/free and priority inheritance?

[Stanislav Meduna]

Hi,

I am hunting a possible priority inversion case and I would like
to ask whether the malloc/free from glibc (particularly 2.11.3
used in Debian 6 or newer) uses priority inheritance mutexes
when doing the necessary locking.

There is http://sourceware.org/bugzilla/show_bug.cgi?id=12114
which would suggest that it is not - is this (still) true?
If yes, is there some patch or are there tried&tested alternative
malloc libraries that do not have the problem (e.g. tcmalloc)?
I am using it on a RT_PREEMPT_FULL linux-rt.

Please Cc me on answer, I am not subscribed to libc-help

Thanks
-- 
                                        Stano

Re: malloc/free and priority inheritance?

[Stanislav Meduna]

On 03.04.2013 01:06, Stanislav Meduna wrote:

> I am hunting a possible priority inversion case and I would like
> to ask whether the malloc/free from glibc (particularly 2.11.3
> used in Debian 6 or newer) uses priority inheritance mutexes
> when doing the necessary locking.

OK, after code-review it looks that it does not and neither
do the condition variables and semaphores. This is bad...

I think I can work around the malloc/free with some linker magic
and wrapper functions (we don't allocate much so the performance
hit is tolerable), but anyone here has a pointer to priority
inheritance aware condition variables implemented using futexes
outside of glibc?

I'd like to avoid patching glibc, as this is always a quite risky
challenge and we already have production code. On the other hand
I only need to support RT-Linux on x86 and ARM and I don't need
the assembly-optimized versions.

Thanks
-- 
                                        Stano

Re: malloc/free and priority inheritance?

[Stanislav Meduna]

On 04.04.2013 14:59, Stanislav Meduna wrote:

> OK, after code-review it looks that it does not and neither
> do the condition variables and semaphores. This is bad...

hm well.. the assembler version of e.g. __pthread_cond_broadcast
in 2.17 for x86 seems to be using the PI. No luck with ARM (2.16
in ports) though.

Regards
-- 
                                        Stano

Re: malloc/free and priority inheritance?

[Siddhesh Poyarekar]

On 4 April 2013 19:00, Stanislav Meduna <stano@meduna.org> wrote:

> hm well.. the assembler version of e.g. __pthread_cond_broadcast
> in 2.17 for x86 seems to be using the PI. No luck with ARM (2.16
> in ports) though.

The generic C code was updated to use PI in current master (I don't
remember if the arm support bits were added, but they must have been
by now), so you could cherry-pick and backport those bits for your
distro if you want.

Siddhesh
--
http://siddhesh.in

Re: malloc/free and priority inheritance?

[Carlos O'Donell]

On 04/04/2013 09:37 AM, Siddhesh Poyarekar wrote:
> On 4 April 2013 19:00, Stanislav Meduna <stano@meduna.org> wrote:
> 
>> hm well.. the assembler version of e.g. __pthread_cond_broadcast
>> in 2.17 for x86 seems to be using the PI. No luck with ARM (2.16
>> in ports) though.
> 
> The generic C code was updated to use PI in current master (I don't
> remember if the arm support bits were added, but they must have been
> by now), so you could cherry-pick and backport those bits for your
> distro if you want.

... and ARM uses the generic C code.

My comments in BZ#12114 still remain. Why can't we make malloc/free
use PI locks? We need not convert lll_lock, but just make malloc-machine.h
use a PI-aware lock?

Cheers,
Carlos.

[1] http://sourceware.org/bugzilla/show_bug.cgi?id=12114

Re: malloc/free and priority inheritance?

[Stanislav Meduna]

On 04.04.2013 15:37, Siddhesh Poyarekar wrote:

> The generic C code was updated to use PI in current master (I don't
> remember if the arm support bits were added, but they must have been
> by now), so you could cherry-pick and backport those bits for your
> distro if you want.

Oh.. thanks for pointing out.

One more question: what exactly does lll_lock do? Is it priority
inheritance aware? It is difficult to follow all the macros
and assembler code, but as far as I can tell this ends
with calling FUTEX_WAIT.

The first thing e.g. the __pthread_cond_broadcast (and most of the
other functions as well) does is to grab lll_lock. Is the following
scenario possible?

- a low priority thread does the broadcast and gets the lock
- a medium priority thread unrelated to this condition variable
  gets scheduled and preempts the low priority one right
  after returning from lll_lock
- a high priority thread gets scheduled and wants to do
  the broadcast on this variable too
- it finds the lock held and blocks. The medium priority thread
  gets scheduled again

Now we have a classical priority inversion.

>From all that I can read it is not mandatory that the
pthread_cond_broadcast or signal is being called with the mutex
held and I think there could be more variants of this anyway.

Thanks
-- 
                                          Stano

Re: malloc/free and priority inheritance?

[Siddhesh Poyarekar]

On 4 April 2013 20:23, Carlos O'Donell <carlos@redhat.com> wrote:
> ... and ARM uses the generic C code.
>
> My comments in BZ#12114 still remain. Why can't we make malloc/free
> use PI locks? We need not convert lll_lock, but just make malloc-machine.h
> use a PI-aware lock?

The trouble (as always) is to decide on when to use PI-aware locks.
Do we do that by default or do we have (*chuckle*) an environment
variable to override the default locks?  Maybe this discussion is more
suitable for libc-alpha though, since we can hopefully get all
maintainers to chime in there.

Siddhesh
--
http://siddhesh.in

Re: malloc/free and priority inheritance?

[Siddhesh Poyarekar]

On 4 April 2013 20:39, Stanislav Meduna <stano@meduna.org> wrote:
> The first thing e.g. the __pthread_cond_broadcast (and most of the
> other functions as well) does is to grab lll_lock. Is the following
> scenario possible?

Yes this is possible.  I think there is a bug report that describes
this.  We need to convert the pthread_cond_t internal lock into a PI
one if the mutex guarding it is PI.  It's probably tricky to do
though; I haven't thought it through.

Siddhesh
--
http://siddhesh.in

Re: malloc/free and priority inheritance?

[Darren Hart]

On 04/04/2013 08:39 AM, Siddhesh Poyarekar wrote:
> On 4 April 2013 20:39, Stanislav Meduna <stano@meduna.org> wrote:
>> The first thing e.g. the __pthread_cond_broadcast (and most of the
>> other functions as well) does is to grab lll_lock. Is the following
>> scenario possible?
> 
> Yes this is possible.  I think there is a bug report that describes
> this.  We need to convert the pthread_cond_t internal lock into a PI
> one if the mutex guarding it is PI.  It's probably tricky to do
> though; I haven't thought it through.

I have patches out on the glibc alpha list that do this. It is on my
plate to dust these off, reapply and test them, and try to push them
again, I just haven't been able to get to it.

Patches and test cases available here:
http://sourceware.org/bugzilla/show_bug.cgi?id=11588

-- 
Darren Hart
Intel Open Source Technology Center
Yocto Project - Technical Lead - Linux Kernel

Re: malloc/free and priority inheritance?

[Carlos O'Donell]

On 04/04/2013 11:32 AM, Siddhesh Poyarekar wrote:
> On 4 April 2013 20:23, Carlos O'Donell <carlos@redhat.com> wrote:
>> ... and ARM uses the generic C code.
>>
>> My comments in BZ#12114 still remain. Why can't we make malloc/free
>> use PI locks? We need not convert lll_lock, but just make malloc-machine.h
>> use a PI-aware lock?
> 
> The trouble (as always) is to decide on when to use PI-aware locks.
> Do we do that by default or do we have (*chuckle*) an environment
> variable to override the default locks?  Maybe this discussion is more
> suitable for libc-alpha though, since we can hopefully get all
> maintainers to chime in there.

The number of tunables just keeps growing doesn't it?

Added this to my list of tunables in the WIP document I'm writing:
sourceware.org/glibc/wiki/TuningLibraryRuntimeBehavior

Cheers,
Carlos.

Re: malloc/free and priority inheritance?

[Carlos O'Donell]

On 04/05/2013 01:39 PM, Darren Hart wrote:
> On 04/04/2013 08:39 AM, Siddhesh Poyarekar wrote:
>> On 4 April 2013 20:39, Stanislav Meduna <stano@meduna.org> wrote:
>>> The first thing e.g. the __pthread_cond_broadcast (and most of the
>>> other functions as well) does is to grab lll_lock. Is the following
>>> scenario possible?
>>
>> Yes this is possible.  I think there is a bug report that describes
>> this.  We need to convert the pthread_cond_t internal lock into a PI
>> one if the mutex guarding it is PI.  It's probably tricky to do
>> though; I haven't thought it through.
> 
> I have patches out on the glibc alpha list that do this. It is on my
> plate to dust these off, reapply and test them, and try to push them
> again, I just haven't been able to get to it.
> 
> Patches and test cases available here:
> http://sourceware.org/bugzilla/show_bug.cgi?id=11588

Darren,

Thanks, and I assume you have copyright assignment through Intel
which is great.

As a community I think we're in a better place to review and
accept these kinds of patches.

Thanks for sticking around for 3 years to make sure these changes
get into glibc :-)

Cheers,
Carlos.