Skip to contentSkip to conversation

malloc/free and priority inheritance?

DISCUSSION Stanislav Meduna 5 participants 11 messages Apr 2, 2013 – Apr 6, 2013

lore
Share & tools
lore
#0 lore raw

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

Signature · 1 line
                                        Stano
#1 lore raw
Quoted 4 lines · Stanislav Meduna

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

Signature · 1 line
                                        Stano
#2 lore raw
Quoted 2 lines · Stanislav Meduna

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

Signature · 1 line
                                        Stano
#3 lore raw
Quoted 3 lines · Stanislav Meduna

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

#4 lore raw
Quoted 10 lines · Siddhesh Poyarekar
Quoted 3 lines · Stanislav Meduna

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

#5 lore raw
Quoted 5 lines · Carlos O'Donell

... 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

#6 lore raw
Quoted 7 lines · Siddhesh Poyarekar
Quoted 5 lines · Carlos O'Donell

... 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?

Quoted 5 lines

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.

#7 lore raw
In reply to Siddhesh Poyarekar
Quoted 4 lines · Siddhesh Poyarekar

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.

Quoted 1 line

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

Signature · 1 line
                                          Stano
#8 lore raw
Quoted 3 lines · Stanislav Meduna

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

#9 lore raw
Quoted 9 lines · Siddhesh Poyarekar
Quoted 3 lines · Stanislav Meduna

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

Signature · 3 lines
Darren Hart
Intel Open Source Technology Center
Yocto Project - Technical Lead - Linux Kernel
#10 lore raw
Quoted 11 lines · Darren Hart
Quoted 9 lines · Siddhesh Poyarekar
Quoted 3 lines · Stanislav Meduna

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.

Quoted 6 lines

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.