Recursive Mutexes for SMP

[Crazed123]

I have an object X with a function A that locks X. I have another object Y that accesses X by locking it. While it has the lock, it calls A.

Using pure mutexes this situation deadlocks, and the normal solution is recursive mutexes. However, I don't know any implementation of recursive mutexes that doesn't rely on a preexisting thread structure and scheduler, and I need to use my locks at a level where such abstractions don't exist yet.

Anyone have any ideas?

[Kevin McGuire]

I thought it would work just like a normal mutex except:

If owner attempts to relock the mutex then success, and a counter is incremented. If owner attempts a unlock then the counter is decremented.

So it just worked like a normal mutex with a counter?

Just like the PTHREAD_MUTEX_RECURSIVE in the POSIX threading support in LIBC.

[Crazed123]

Yeah, but who's "owner"? How does the mutex know "who" accesses it?

[Kevin McGuire]

Do you mean you have mutex exclusion code and it want to make it become voided until the scheduler gets up and running?

Let me pull out my crystal ball of world discovery..

[Crazed123]

No, I want mutual exclusion code that works without a scheduler, because you can't implement a scheduler in terms of code that needs a scheduler.

[Kevin McGuire]

How about you just make one processor spin on the mutex until it gets opened? This does not need a scheduler. Then when a scheduler exists you make it call into the scheduler and have it sleep the thread until it acquires the mutex, right?

[Crazed123]

Yes, that works to create a normal mutex. But what about recursive mutexes?

Have I explained the problem badly?

[Kevin McGuire]

Oh. I just realized the problem. Try locking it with a value other than one to signal who owns it.

0x0 is free
0x1 - 0xFFFFFFFF is locked.


Then you can determine if you have already locked it. You need to look around since I know there is information in this forum and maybe the Wiki on how to build a identification number for each processor in a SMP architecture.

Brendan would be really helpful for your question. I am sorry.

[Colonel Kernel]

I will avoid the question entirely by saying that you should re-design your control flow so that recursive mutexes aren't necessary.

Also, I would call them recursive spinlocks, since to me a mutex implies blocking a thread, and at that level there is no "blocking" and there are no "threads" yet.

[Crazed123]

I will avoid the question entirely by saying that you should re-design your control flow so that recursive mutexes aren't necessary.

So I should redesign my control flow so that an "owner" object never calls the "owned" object while it holds the lock of that object? That seems to defeat the purpose of both object orientation and locks, though I agree with the principle that Better Algorithms are Best.

Anyway, I looked it up in the Intel Bible. If your processor supports the CPUID instruction, it will return the Initial Local APIC ID, a guaranteed-unique identifier for each processor, in bits 24-31 of EBX when CPUID is run with EAX=1. Some short assembler processing turns this into a processor identifier my recursive spinlocks can use.

Code: Select all

function ProcessorID(): longword; assembler;
label
_return;
asm
mov Result,0
pushf
pop eax
shr eax,21
and eax,1
cmp eax,0
je _return
mov eax,1
cpuid
shr ebx,24
mov Result,ebx
_return: nop
end ['EAX','EBX'];

The first bit just checks for CPUID support, presuming that a system without it can't possibly have multiprocessing capabilities (and therefore always returning 0 will be correct). If support is found, it runs CPUID and puts the appropriate bits into Result. I assume that on systems without multiprocessing support, those bits are reserved and guaranteed to equal 0, again giving a constant return value for uniprocessor machines.

[Colonel Kernel]

So I should redesign my control flow so that an "owner" object never calls the "owned" object while it holds the lock of that object? That seems to defeat the purpose of both object orientation and locks, though I agree with the principle that Better Algorithms are Best.

You should make either the object itself or its client responsible for locking, not both.

[Combuster]

Well, the advantage of a recursive lock is that you don't need to worry that the caller has done the locking correctly, or that you accidentally get into a recursion.

Recursive locks are easy to implement given an existing spinlock:
(untested)

Code: Select all

typedef struct
{
     spinlock_t * s;
     thread_t owner;
     int lockcount;
} recursive_lock_t;

void lock_recursive(recursive_lock_t * lock)
{
    if (lock->owner == threadid)
        lock->lockcount++;
    else {
        lock_spinlock(lock->s);
        lock->owner = threadid;
    }
}

void unlock_recursive(recursive_lock_t * lock)
{
    if (lock->lockcount > 0)
        lock->lockcount--;
    else {
        lock->owner = 0;
        unlock_spinlock(lock->s);       
    }
}

[Brendan]

Hi,

Recursive locks are easy to implement given an existing spinlock:

Given the choice between recursive spinlocks with dubious design, and bug detection, I'll choose bug detection every time.

For spinlocks, I'd recommend something like (untested):

Code: Select all

%macro GET_LOCK 1
%ifdef DEBUGGING
    push eax
    mov eax,[gs:CPUdata.currentThreadID]
%endif

    lock bts [%1],0
    je %%gotLock
%%wait:
    pause

%ifdef DEBUGGING
    cmp [%1 + 4],eax
    jne %%noPanic
    push %1
    push DEADLOCK_DETECTED
    jmp kernel_panic
%%noPanic:
%endif

    test [%1],1
    jne %%wait
    lock bts [%1],0
    jne %%wait
%%gotLock:

%ifdef DEBUGGING
    mov [%1 + 4],eax
    pop eax
%endif
%endmacro


%macro FREE_LOCK 1
%ifdef DEBUGGING
    push eax
    mov eax,[gs:CPUdata.currentThreadID]
    cmp [%1 + 4],eax
    je %%noPanic
    push %1
    push FREE_LOCK_WITHOUT_GET_LOCK
    jmp kernel_panic
%%noPanic:
%endif

    mov dword [%1],0

%ifdef DEBUGGING
    mov [%1 + 4],IMPOSSIBLE_THREAD_ID
    pop eax
%endif
%endmacro

Of course I've stuffed things up often enough to know the value of automated "stuffed it up" detection.

For the original problem, just create Function B that does the same as Function A without locking, and then make object Y used Function B instead of Function A if it's already got the lock. If code size is a problem, then you could convert Function A into a simple wrapper (i.e. "get lock, call functionB, release lock").

I'd also seriously consider Colonel Kernel's advice: You should make either the object itself or its client responsible for locking, not both..

I'm also curious why different objects access the same data in the first place - it doesn't seem very "OOP" to me (but then I've always prefered the "all data is private data" style of OOP)...


Cheers,

Brendan