Recursive mutex?

ChibiOS public support forum for all topics not covered by a specific support forum.

Moderators: utzig, lbednarz, tfAteba, barthess, RoccoMarco

Freddie Chopin
Posts: 36
Joined: Wed Oct 17, 2012 8:57 am

Recursive mutex?

Postby Freddie Chopin » Wed Oct 17, 2012 12:23 pm

I'm not entirely sure whether I understand the docs correctly, but ChibiOS/RT does not have any mechanism for recursive mutexes, right? These are the ones that can be taken multiple times by the same (owning) thread, but also have to be given back the same number of times.

I'm not saying these are great, I'm just asking [; There are some places in newlib's libc which require locks to be recursive so having a recursive mutex seems the easiest solution. Actually I don't see any other, as using semaphores could result in a deadlock, the other not-so-good-solution is to disable the scheduler, but that's not an option if the operation can be blocking...

4\/3!!

User avatar
Giovanni
Site Admin
Posts: 13020
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 748 times
Been thanked: 621 times
Contact:

Re: Recursive mutex?

Postby Giovanni » Wed Oct 17, 2012 1:11 pm

Hi,

Those have been left out for several reasons, patches were submitted and rejected in the past. Among the various reasons:
1) In ChibiOS mutexes are taken/release in strict FIFO order for efficiency and also because point 2.
2) That would conflict with the priority inheritance algorithm implemented in mutexes. The algorithm is efficiently implemented and resolves priority inversions with any number of threads and nesting level but this imposes restrictions.
3) The behavior with condition variables would not be well defined (what to do when waiting on a condition variable within a mutual exclusion zone taken multiple times?).

There are workarounds for this kind of problems, for example using more mutexes, one for each protected resource.

It would be very simple to add another kind of (recursive) mutexes without PI and condition variables, all primitives use the same scheduler API, I am just not convinced it is really required.

Giovanni

Freddie Chopin
Posts: 36
Joined: Wed Oct 17, 2012 8:57 am

Re: Recursive mutex?

Postby Freddie Chopin » Wed Oct 17, 2012 1:30 pm

Giovanni wrote:There are workarounds for this kind of problems, for example using more mutexes, one for each protected resource.

In the use-case I'm thinking of (newlib's locking), you have limited possibilities without changing a load of newlib's code - generally you're supposed to properly define these and do nothing more:

Code: Select all

typedef int _LOCK_T;
typedef int _LOCK_RECURSIVE_T;
 
#include <_ansi.h>

#define __LOCK_INIT(class,lock) static int lock = 0;
#define __LOCK_INIT_RECURSIVE(class,lock) static int lock = 0;
#define __lock_init(lock) (_CAST_VOID 0)
#define __lock_init_recursive(lock) (_CAST_VOID 0)
#define __lock_close(lock) (_CAST_VOID 0)
#define __lock_close_recursive(lock) (_CAST_VOID 0)
#define __lock_acquire(lock) (_CAST_VOID 0)
#define __lock_acquire_recursive(lock) (_CAST_VOID 0)
#define __lock_try_acquire(lock) (_CAST_VOID 0)
#define __lock_try_acquire_recursive(lock) (_CAST_VOID 0)
#define __lock_release(lock) (_CAST_VOID 0)
#define __lock_release_recursive(lock) (_CAST_VOID 0)


As you see this requires both recursive and normal locks (; Any suggestiong on how to approach this problem?

If you'd like to implement __malloc_lock() and __malloc_unlock() by means of mutex these also need to be recursive... Here is some idea with semaphore and manually counting the recursion level - http://neptune.billgatliff.com/newlib.html

It would be very simple to add another kind of (recursive) mutexes without PI and condition variables, all primitives use the same scheduler API, I am just not convinced it is really required.

That would be something like counting semaphore + owner field, right?

4\/3!!

User avatar
Giovanni
Site Admin
Posts: 13020
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 748 times
Been thanked: 621 times
Contact:

Re: Recursive mutex?

Postby Giovanni » Wed Oct 17, 2012 2:08 pm

Good point, now I am convinced it is required, however I would not start from semaphores (no need for counter, not that counter) but from mutexes by adding a reentrance counter and stripping anything PI-related.

I think it could be added to the kernel easily as "lightweight reentrant mutexes", no priority inheritance nor condvars on those however. I'll add this to the to-do list, the bulk of work are not mutexes themselves but the test code to bring coverage back close to 100%.

Giovanni

Freddie Chopin
Posts: 36
Joined: Wed Oct 17, 2012 8:57 am

Re: Recursive mutex?

Postby Freddie Chopin » Wed Oct 17, 2012 2:30 pm

I've posted to newlibs ML to see if any of the developers know whether it would be possible to drop recursive locking requirement...

If the "reentrancy" can be added easily by the user (something like in the link I've presented above) and you think such solution would be robust there's no need to add it to the kernel - without priority inheritance mutexes are not that useful probably... On the other hand, if you'd add an api function to check whether the calling thread already owns the mutex (or something with this functionality), so that a "manual" recursion could be implemented it would be enough:

Code: Select all

uint32_t recursion_count;
Mutex mutex;

void lock_recursive(void)
{
if (mutexOwnedByThisThread(mutex))
recursion_count++; // already owned - increase recursion count;
else
lock(mutex); // not owned - taken for the first time by this thread
}

void unlock_recursive(void)
{
if (recursion_count == 0) // it's "owned" for the last time so unlock
unlock(mutex);
else
recursion_count--; // there are still some recursion levels
}


What do you think? That seems easier and maybe it's already possible with current implementation?

4\/3!!

User avatar
Giovanni
Site Admin
Posts: 13020
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 748 times
Been thanked: 621 times
Contact:

Re: Recursive mutex?

Postby Giovanni » Wed Oct 17, 2012 3:38 pm

It would work as placeholder but operations should be atomic, in ChibiOS terms you have to use S-class functions enclosed between chSysLock() and chSysUnlock(), see "Kernel Concepts" in the kernel reference manual (I would not attempt using condvars with that).
I am convinced about recursive mutex because you brought up the scenario where you have to fix an existing infrastructure (newlib in this case) that makes an assumption regarding mutexes, it is a good point so I am oriented to implement them anyway.

Giovanni

Freddie Chopin
Posts: 36
Joined: Wed Oct 17, 2012 8:57 am

Re: Recursive mutex?

Postby Freddie Chopin » Wed Oct 17, 2012 3:53 pm

Giovanni wrote:It would work as placeholder but operations should be atomic, in ChibiOS terms you have to use S-class functions enclosed between chSysLock() and chSysUnlock(), see "Kernel Concepts" in the kernel reference manual (I would not attempt using condvars with that).

So just enclosing these functions with system-lock and unlock would fix that, right? (;

Giovanni wrote:I am convinced about recursive mutex because you brought up the scenario where you have to fix an existing infrastructure (newlib in this case) that makes an assumption regarding mutexes, it is a good point so I am oriented to implement them anyway.

From Newlib's mailing list I've got a response that POSIX requires stdio locks to be recursive, so the locking scheme cannot be changed.
http://sourceware.org/ml/newlib/2012/msg00422.html

As you probably know better - would mutexes without priority inheritance work reliably? Maybe lack of this just slows down operation a bit? Are there any scenarios where lack of priority inheritance would lead to deadlock?

4\/3!!

User avatar
Giovanni
Site Admin
Posts: 13020
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 748 times
Been thanked: 621 times
Contact:

Re: Recursive mutex?

Postby Giovanni » Wed Oct 17, 2012 5:38 pm

Freddie Chopin wrote:So just enclosing these functions with system-lock and unlock would fix that, right? (;


You also need to use the "S-class" variant of the APIs within locks or the state checker will complain.

Freddie Chopin wrote:As you probably know better - would mutexes without priority inheritance work reliably? Maybe lack of this just slows down operation a bit? Are there any scenarios where lack of priority inheritance would lead to deadlock?


Lack of PI does not lead to deadlocks but can lead to priority inversion, it can also reduce the quality of real time response by increasing overall jitter. But don't worry too much, some RTOSes out there don't even have that and work acceptably in most applications.

A lander crashed on Mars because that but don't let that stop you :)

Giovanni

User avatar
Prof. Dr. YoMan
Posts: 57
Joined: Thu May 24, 2012 11:00 am
Been thanked: 1 time

Re: Recursive mutex?

Postby Prof. Dr. YoMan » Fri Oct 19, 2012 8:32 am

One thing about malloc, malloc_lock and unlock.

In a fast check I was able to overwrite malloc and free with an own implementation. Seems it is defined week in newlib of GNU ARM embedded (from launchpad).
Implementing it as chHeapAlloc chHeapFree and companion should work I guess.
From what I see in the .map and .lst my malloc and free are used. I did not test with actual code. Including a "my_malloc.h" and not <malloc.h> and you are done.

And yes i would like to see some recursive mutex/lock to implement all other locks in newlib correct.

Any hits on how to implement mytexOwnedByThisThread using ChibiOS internal structures, Giovanni?

User avatar
Giovanni
Site Admin
Posts: 13020
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 748 times
Been thanked: 621 times
Contact:

Re: Recursive mutex?

Postby Giovanni » Fri Oct 19, 2012 9:19 am

It is easy, the mutex has a pointer to the owning thread, just compare it with chThdSelf().

Giovanni


Return to “General Support”

Who is online

Users browsing this forum: No registered users and 7 guests