TSL instruction reference

Question

I want to use "TSL" instruction in assembly , but it has no reference for understand .in some articles this instruction is introduced for mutual exclusion problem but it has no reference or complete example to understand completely.

Irrefutable

what platform is it for? There are normally high level wrappers for this kind of functionality. In Windows, there's a bunch of InterlockedXXXX operations. In GCC, there are builtins. Don't reinvent sync primitives unless you have to. – Reglet

Answer 1

TSL (Test and Set Lock) is an operation that frequently comes up when dealing with mutual exclusion problems in general, but that doesn't mean such an instruction actually exists on whatever architecture you are using; or, even if it does exist, that it's called TSL.

On x86, for example, you can use the XCHG instruction to perform a TSL.

Clomp

how i Can use XCHG to do it? I want any instruction use for this job – Irrefutable

Do you know what TSL does? It simply sets the lock (usually to 1) and returns the previous value. It's an atomic exchange. So all you need to do is something like: MOV EAX, 1; XCHG EAX, [lock] – Clomp

can you give me an example code used these instruction for mutual exclusion problem. I want a code in assembly or C that use it – Irrefutable

Answer 2

I think @Jester and @Seva Alekseyev have already done a great job answering this question but here is a simple implementation in C with inline Assembly by using pthreads on a x86 Ubuntu machine.

In the following example, there are two long-running threads. Both threads have a critical and a non-critical section, critical_region() and noncritical_region respectively. They both have to call enter_region() in order to get the lock. Once a thread gets the lock, it can start running its critical section. The other thread is blocked until the thread with the lock will call leave_region().

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


void enter_region() {
    asm(
        ".data\n\t"
        "lock:\n\t"
        ".byte 0\n\t"
        ".text\n\t"

        "_enter_region:\n\t"
        "movb $1, %al\n\t" /* move 1 to AL */
        "xchgb (lock),%al\n\t" 
        "cmp $0, %al\n\t"
        "jne _enter_region\n\t"

    );
}

void leave_region() {
    asm("movb $0, (lock)");
}


void critical_region() {

}

void noncritical_region() {

}

static void* f1(void* p) {
    while(1) {
        puts("wait for f2");
        enter_region();
        printf("f1 can start its critical section\n");
        critical_region();
        leave_region();
        noncritical_region();
    }
    return NULL;
}

static void* f2(void* p) {
    while(1) {
        puts("wait for f1");
        enter_region();
        printf("f2 can start its critical section\n");
        critical_region();
        leave_region();

        /* if you call sleep, you can see that the non-critical section of this thread won't
        *  block the other thread from running its critical section as many times as it wants
        */
        // sleep(1);
        noncritical_region();
    }
    return NULL;
}

int main() {
    int rc;

    pthread_t t1, t2;

    rc = pthread_create(&t1, NULL, f1, NULL);
    if(rc != 0) {
        fprintf(stderr, "pthread f1 failed\n");
        return EXIT_FAILURE;
    }

    rc = pthread_create(&t2, NULL, f2, NULL);
    if(rc != 0) {
        fprintf(stderr, "pthread f2 failed\n");
        return EXIT_FAILURE;
    }

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    puts("All threads finished.");
    return 0;
}

Carey

Answer 3

XCNG is not conditional, it just exchanges a register with a memory location. What you want is CMPXCHG with the LOCK prefix. The latter will make it atomic on multicore machines.

Also, you can implement atomic compare-and-set with LOCK XADD, but that'll take a loop.

Ref: http://en.wikipedia.org/wiki/Compare-and-swap

Reglet

can you give me an example code used these instruction for mutual exclusion problem. I want a code in assembly or C that use it – Irrefutable

Or maybe I am not wrong, because I didn't say it was conditional. You atomically set the lock to 1 then examine if the previous value was 0 in which case you got the lock or if it was already 1 in which case it hasn't been changed and you don't have the lock. Also, I said for example, so there are other ways to do it, but mine isn't wrong unless you can prove it. See also wikipedia. – Clomp

@Jester: if the test and set are not the same command, you're open to race conditions. Imagine: you exchange, you see that the previous value was 1. Now you set it back to zero... and kill a legitimate lock that was raised by another thread in the meantime. A context switch may come on any boundary between assembly commands. Including the one between set and test. That's the point of having CMPXGHG. – Reglet

Huh? If the previous value was 1, you didn't get the lock, so you don't do anything (repeat until you get the lock). If you got the lock it's now 1, and nobody else will get it and you can set it to 0 when you are done with the critical section. No race condition. – Clomp

Point taken. No race indeed. Still, why decouple test and set and a CPU level primitive that does both exists? – Reglet

I said that was one way, and there could be reasons for it. xchg doesn't require the eax register, has a shorter opcode and doesn't need a lock prefix. It also might be good to know you can do TSL with an atomic exchange on other architectures (or very old x86 cpus) where you might not have cmpxchg. Could you please edit your post and remove that I am wrong? Thank you. – Clomp