OSDev.org

gerryg400 wrote:I don't bother to pass a value to the kernel either. I just check the highest bit. Actually my user space futex variable is different from the one in the article as well. It contains the following fields

Code: Select all

bit31: waiter bit
bit30: spare
bits29 to bit0: thread id

I have the tid in the lock to allow recursive locks and/or to check for deadlock. It also means that the kernel can check the owner for when I get around to implementing priority inheritance. I haven't put a whole lot of thought into that yet though.

class TSection
{
public:
    TSection()
    {
        handle = RdosCreateSection(&val);
        val = 0;
    }

    ...

private:
    int handle;
    char val;
};

struct section_handle
{
    handle_base base;
    char *user_val_ptr;
    int *queue_head;
};

Nable wrote:> 386, 486
> SMP
You've touched my heart, I just want to see such system.

gerryg400 wrote:I have the tid in the lock to allow recursive locks and/or to check for deadlock. It also means that the kernel can check the owner for when I get around to implementing priority inheritance. I haven't put a whole lot of thought into that yet though.

class mutex
    mutex()
    {
        handle = RdosCreateSection(&val);
        owner = 0;
        counter = 0;
    }

    lock()
    {
        if (owner == str())
            counter++;
        else
        {
              acquire (as before)

               owner = str();
               counter = 1;
         }
     }

     unlock()
     {
         counter--;

         if (counter == 0)
         {
            owner = 0;
            release (as before)
          }
     }

private:
     int handle;
     char val;
     int counter;
     short int owner;
}

gerryg400 wrote:rdos, my first implementation was also like this but it turned out that under reasonably heavy load, that threads would get stuck on the queue while 2 threads would lock/unlock the mutex in turn. That's the reason that, if the variable has been changed and a thread needs to return and retry, it blocks and lets the next thread from the queue do the retry. It made a huge difference to the fairness in my limited testing so far.

rdos wrote:

gerryg400 wrote:I don't bother to pass a value to the kernel either. I just check the highest bit. Actually my user space futex variable is different from the one in the article as well. It contains the following fields

Code: Select all

bit31: waiter bit
bit30: spare
bits29 to bit0: thread id

I have the tid in the lock to allow recursive locks and/or to check for deadlock. It also means that the kernel can check the owner for when I get around to implementing priority inheritance. I haven't put a whole lot of thought into that yet though.

I have one additional objection to the definition of the futex. Kernel is passed an address, which proposedly needs to be translated into a physical address, and then the kernel queue must be searched for by looking up the physical address. This really sucks, especially if there are many futexes in the system, which there will be in mine.

• It allows the kernel to recycle the wait queues for any futex with no waiters
• It allows the use of futexes in shared memory regions

Owen wrote:The rationale for a physical address is twofold:

• It allows the kernel to recycle the wait queues for any futex with no waiters
• It allows the use of futexes in shared memory regions

A hash table isn't that expensive - especially when you consider that its about to be followed by the thread sleeping and a context switch. That said, you could easily have both forms, if you somehow keep the allocated handles as invalid futex addresses - a simple way would be to set the lowest bit of the handle to 1, for example.

Owen wrote:Nested, in-thread accesses only require two variables:

Code: Select all

void lock(Mutex* mutex) 
{
    prev = compareAndSwap(&mutex->futex, 0, myThreadId);
    if(prev &~ FUTEX_WAIT_BIT == myThreadId) {
        // Recursively taking the lock
        mutex->lockCount++;
    } else if(prev == 0) {
        // We took the lock
    } else {
        // Somebody else has the lock
        futexWaitLock(&mutex->futex);
    }
}

void unlock(Mutex* mutex)
{
    assert(mutex->futex &~ FUTEX_WAIT_BIT == myThreadId);
    if(--mutex->lockCount == 0) {
        prev = compareAndSwap(&mutex->futex, myThreadId, 0);
        if(prev != myThreadId) {
            // Somebody else is waiting on the lock
            futexWaitUnlock(&mutex->futex);
        }
    }
}

Fundamentally, you're always going to wrap the Futex in some manner; it's nontrivial to use correctly. That said, I like the fact that a Futex can be statically initialized in the traditional C manner (i.e. to zero)

gerryg400 wrote:Owen, it looks like your futexWaitLock function much be capable of atomically taking the lock. Is that function a system call or is the lock retried in userspace before/after the actual system call is made ? I'm curious about whether it would be possible to take the physical lock safely from kernel space.

shared_ptr<FutexWaitList> waitList(getWaitListFor(futex))
with(lock(waitList)) {
    futexValue = __atomic_load(futex, __ATOMIC_RELAXED);
    for(;;) {
        if(futexValue & FUTEX_WAIT_BIT) {
            // somebody else is already waiting. Join the list.
            waitList.waitOn(); // waitOn adds us to the wait queue and then unlocks the spinlock
            return;
        } else if(futexValue == 0) {
            bool didSet = __atomic_compare_and_swap(futex, &futexValue, myThreadId, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED);
            if(didSet) return; // successfully locked; no need to wait
        } else {
            bool didSet = __atomic_compare_and_swap(futex, &futexValue, futexValue | FUTEX_WAIT_BIT, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED);
            if(didSet) {
                waitList.waitOn();
                return;
            }
        }
    }
}