1
\$\begingroup\$

My history of C/ASM locks here in codereview:

Once you have gotten taste of assembly, there is no turning back. I don't care if I am not ready/worthy, I going to step things up a bit and be a little bit more adventures. So I went ahead and made a lock that I hope is able to handle recursions. I will without a doubt fail very painfully and the mistake is also going to be hard to spot. No, I am not pessimistic. Just like gravity works to put things down, so does my reasoning skills to me. It is up to you to give me tough love and spot my faulty reasoning and throw bananas at me!

The code in question.

// "gate_" is the namespace marker for higher level languages that might import this code... as if...
#define gate_Gate volatile int
#define gate_Pass volatile int

extern inline void
gate_Enter
(gate_Gate *gate, gate_Pass *pass)
{
    asm volatile (
        "jmp gate_Enter_check\n"     // Skip the line.
        "gate_Enter_wait:\n"         // Wait in line.
        "pause\n"                    // Wait a long time.
        "gate_Enter_check:\n"        // Now we are at the gate.
        "cmp %[lock], %[checkin]\n"  // See if our pass is any good.
        "jge gate_Enter_skip\n"      // Skip if pass >= lock.
        "mov %[lock], %%eax\n"       // eax = 1.
        "lock xchg %%eax, %[gate]\n" // Attempt to validate our pass and connect it to the gate.
        "test %%eax, %%eax\n"        // Hope for the best.
        "jnz gate_Enter_wait\n"      // There is no hope, go back in line.
        "gate_Enter_skip:\n"         // We are VIP!
        "add %[lock], %[checkin]\n"  // Checkin pass like pro!
        : [gate] "=m" (*gate), [checkin] "=m" (*pass)
        : [lock] "r" (1)
        : "eax"
    );
}

extern inline void
gate_Leave
(gate_Gate *gate, gate_Pass *pass)
{
    asm volatile (
        "cmp %[pass], %[isLast]\n"   // Have I checked in only once?
        "jg gate_Leave_skip\n"       // Skip next step if I have checked in more then once.
        "mov %[unlock], %[gate]\n"   // Close the gate because I am the last one to leave.
        "gate_Leave_skip:\n"         // Comment!
        "add %[checkout], %[pass]\n" // Checkout. This may or may not be the last time.
        : [gate] "=m" (*gate), [pass] "=m" (*pass)
        : [unlock] "r" (0), [checkout] "r" (-1), [isLast] "r" (1)
    );
}

// Example use
gate_Gate gate = 0;
gate_Pass exampleUsePass = 0;
void exampleUse(int count)
{
    printf("pass=%d\n", exampleUsePass);
    gate_Enter(&gate, &exampleUsePass);
    if (count == 3) {
        // exampleUsePass = 0; // force deadlock.
    }
    if (count < 5) {
        printf("Count = %d\n", count);
        exampleUse(++count);
    }
    gate_Leave(&gate, &exampleUsePass);
    printf("pass=%d\n", exampleUsePass);
}

exampleUse(0);

The question

The intent of this code is a lock that allows recursion. Will this lock make exampleUse both threadsafe and reentrant if we allow our self to assume the pass, exampleUsePass is only used for that function?

  • If not? what is wrong?
  • If yes, it is still wrong; isn't it?... Give me a good rant about what to consider, what is missing or about better approach. If you want to suggest libraries, please restrict your self to C. I am not experienced enough to bind C++ stuff to other languages, so I often can't use the good stuff over there :'(
\$\endgroup\$
2
  • \$\begingroup\$ Sorry, misread the question. \$\endgroup\$
    – user95591
    Commented May 21, 2016 at 12:37
  • \$\begingroup\$ I just changed the question, so maybe you didn't misread but helped me to improve it ;) \$\endgroup\$ Commented May 21, 2016 at 12:39

1 Answer 1

1
\$\begingroup\$

I don't believe your current code is thread safe. Looking at your gate_Enter function:

The first thing you do is skip the wait loop, this is fine:

"jmp gate_Enter_check\n"     
"gate_Enter_wait:\n"         
"pause\n"                    

Then you check your reentry count. If it's > 0 then you assume you are the the one holding the lock and skip the actual lock part.

"gate_Enter_check:\n"        
"cmp %[lock], %[checkin]\n"  
"jge gate_Enter_skip\n"      
"mov %[lock], %%eax\n"       
"lock xchg %%eax, %[gate]\n" 
"test %%eax, %%eax\n"        // Hope for the best.
"jnz gate_Enter_wait\n"      // There is no hope, go back in line.

And increment the nesting level.

"gate_Enter_skip:\n"         // We are VIP!
"add %[lock], %[checkin]\n"  // Checkin pass like pro!

The issue is you don't actually know that the thread calling gate_Enter is the same one that originally entered the gate. If another thread calls exampleUse function it's using the same pass. You could get around this by making use of thread local storage for your pass/checkin variable. Or you could create exampleUsePass on the stack, then pass it in to recursive calls instead of using global vars.

You would have a similar issue with your gate_Leave method, where you unlock the gate, then decrement the nesting count. It would be better to decrement the value, whilst you are within the locked section, something like this:

"add %[checkout], %[pass]\n" 
"jnz gate_Leave_skip\n"       // If not zero, this is a nested call
"mov %[unlock], %[gate]\n"   // Close the gate because I am the last one to leave.
"gate_Leave_skip:\n"         

As an aside, I'm not a huge fan of the way you've essentially renamed the pass parameter to your gate_Enter function to checkin.

[checkin] "=m" (*pass)

A slightly more robust version of your code, which will abort if there is an unexpected exit from gate when you don't own the gate is shown below (along with a simple test harness).

#include <stdio.h>
#include <unistd.h>
#include <unistd.h>
#include <string.h>
#include <pthread.h>

#define gate_Gate volatile int
#define gate_Pass volatile int

/*extern*/ inline void
gate_Enter
(gate_Gate *gate, gate_Pass *pass)
{
    asm volatile (
        "jmp gate_Enter_check\n"     // Skip the line.
        "gate_Enter_wait:\n"         // Wait in line.
        "pause\n"                    // Wait a long time.
        "gate_Enter_check:\n"        // Now we are at the gate.
        "cmp %[lock], %[pass]\n"  // See if our pass is any good.
        "jge gate_Enter_skip\n"      // Skip if pass >= lock.
        "mov %[lock], %%eax\n"       // eax = 1.
        "lock xchg %%eax, %[gate]\n" // Attempt to validate our pass and connect it to the gate.
        "test %%eax, %%eax\n"        // Hope for the best.
        "jnz gate_Enter_wait\n"      // There is no hope, go back in line.
        "gate_Enter_skip:\n"         // We are VIP!
        "add %[lock], %[pass]\n"  // Checkin pass like pro!
        : [gate] "=m" (*gate), [pass] "=m" (*pass)
        : [lock] "r" (1)
        : "eax"
    );
}

/*extern*/ inline void
gate_Leave
(gate_Gate *gate, gate_Pass *pass)
{
    asm volatile (
       "add %[checkout], %[pass]\n"
       "js error_abort\n"            // Abort, underflow on *pass
       "jnz gate_Leave_skip\n"       // Skip next step if I have checked in more then once.
        "mov %[unlock], %%eax\n"
        "lock xchg %%eax, %[gate]\n"
        "test %%eax, %%eax\n"
        "jnz gate_Leave_skip\n"      // If zero, abort because we unlocked an unlocked gate!
        "error_abort:\n"
        "call abort\n"
        "gate_Leave_skip:\n"         
        : [gate] "=m" (*gate), [pass] "=m" (*pass)
        : [unlock] "r" (0), [checkout] "r" (-1), [isLast] "r" (1)
        : "eax"
    );
}

// Example use
gate_Gate gate = 0;
__thread gate_Pass exampleUsePass = 0;  // notice this uses thread
                                        // local storage
void exampleUse(int count)
{
    printf("pass=%d\n", exampleUsePass);
    gate_Enter(&gate, &exampleUsePass);
    if (count == 3) {
        // exampleUsePass = 0; // force deadlock.
    }
    if (count < 5) {
        printf("Count = %d\n", count);
        exampleUse(++count);
    }
// uncomment this line to simulate Leaving twice when we owned the gate
//gate_Leave(&gate, &exampleUsePass);
    gate_Leave(&gate, &exampleUsePass);
    printf("pass=%d\n", exampleUsePass);
}

void *doSomeThing(void *arg) {
 // Uncomment lines in this method to force alternate thread to
 // try to leave gate, when it doesn't own it.
 //  if(arg == NULL)
        exampleUse(0);
 //   gate_Leave(&gate, &exampleUsePass);
    return 0;
}

pthread_t tid[2];

int main(void)
{
    int i = 0;
    int err;

    while(i < 2)
    {
        err = pthread_create(&(tid[i]), NULL, &doSomeThing, i?&err:0);
        if (err != 0)
            printf("\ncan't create thread :[%s]", strerror(err));
        else
            printf("\n Thread created successfully\n");

        i++;
    }

    sleep(5);
    return 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.