Critical sections in userspace without syscalls?

[rdos]

Is it possible to do this in a multitasking, SMP OS? If it is, what does the code look like?

Some alternatives that I've discarded / though about:

The ordinary spinlock-code would only work if the application can disable scheduling or interrupts. If a task gets the spinlock, and then is preempted, the spinlock will never be released, so this will fail. It will also deadlock if the scheduler selects a new task that tries to get the same spinlock.

Another alternative might be to use a variable in user-space, and do a lock sub var,1 / lock add var,1. If this suceeds (CY set), there will be no syscals, but as soon as it fails, syscalls will be needed. This might work (I had a working version before SMP, but it should be possible to make SMP safe).

A special issue is that userspace tampering with section content should not be potentially dangerous to kernel.

So has somebody managed to do this, and if so, how?

[bluemoon]

It depends on the lock is shared across multiple process or not.

For critical section in user space, do you mean an API for user space to perform lock? If yes, this lock usually does not required to share across multiple process, and you can just use ordinary spinlock without the need of disable interrupt.


If the lock need to be shared across process and kernel, you need regular kernel locks; but in situation requiring such lock you usually better deal with other mechanism like IPC and queue.

[rdos]

It depends on the lock is shared across multiple process or not.

It's not shared between processes, but it is shared between multiple threads in the same process.

For critical section in user space, do you mean an API for user space to perform lock?

Yes. I need to protect data shared between multiple userspace threads running in the same process. It would be preferable if no syscalls were needed.

If yes, this lock usually does not required to share across multiple process, and you can just use ordinary spinlock without the need of disable interrupt.

How? Look at the following scenario:

thread1:
RequestLock

Scheduler changes thread

thread2:
RequestLock ; this results in a deadlock

If the lock need to be shared across process and kernel, you need regular kernel locks; but in situation requiring such lock you usually better deal with other mechanism like IPC and queue.

This is how I have implemented it today. I allocate the section resources in kernel, and have a EnterSection and LeaveSection syscall. This works well, but requires 2 syscalls for protecting global data in userspace.

[Owen]

Its not possible to implement without system calls (Well, not unless using a user-mode scheduler). The best implementation is the Futex, and I wrote a long post about them in 2010 so that I would have a good technical overview to refer people to

[Combuster]

If a task gets the spinlock, and then is preempted, the spinlock will never be released

Bull. If it's preempted, it will also be rescheduled and the release code will be reached eventually.

Furthermore, Owen is definitely wrong here: You can implement any mutual exclusion solely in userland. Pick any sample algorithm from wikipedia and it will work perfectly fine.

The only problem is that waiting for such a lock will inherently be a busy wait, and you will need scheduler intervention to prevent cycles being wasted on that - you really want to spend a system call on that when the thread having the lock is not currently scheduled. Since lock contention is a bad thing and should be prevented in the using code, there should not be any need to call the kernel in the vast majority of cases.

Owen already posted a link to a sample good implementation, so I won't need to do that.

[gravaera]

Yo:

It's not shared between processes, but it is shared between multiple threads in the same process.

You're making a few mistakes overall; the only time a process needs kernel assistance to handle locking is when the lock sleeps all threads that fail to acquire it -- in that case you need the scheduler's intervention to put the thread to sleep. For a lock that does not sleep acquisition-failed threads (like a spinlock) it can be fully done in userspace. There are two "standard" behaviours for locks: locks that sleep on acquisition failure, and locks that wait ("spin") on failure.

Yes. I need to protect data shared between multiple userspace threads running in the same process. It would be preferable if no syscalls were needed.

There's a small problem caused by people using "critical section" and "shared data" interchangeably (as you did in the thread title). A critical section is a code path which should not be interrupted mid-execution, or else the operation being performed will be at risk of failure. An example is writing command sequences to hardware registers. Even when you are doing this in a single-processor environment, the registers may be timing sensitive, or may "time out", or some other similar anomaly if you allowed the execution stream to be preempted before the writes have been completed. The aim in protecting a "critical section" isn't necessarily to prevent simultaneous access or multiple writes. Many times a resource which is written to by a critical section also needs to be protected from simultaneous writes though, so the two concepts often overlap, but they aren't technically the same. If all you need to do is enforce a critical section, then you only need to provide "CLI" to userspace.

If you need serialization of access to a shared resource, then you need locking -- simple as that. If you need to ensure that threads trying for the lock don't spin doing nothing, then you need to sleep them; ergo you need scheduler intervention. If not, then you can do it all in userspace.

Code: Select all

thread1:
    RequestLock

Scheduler changes thread

thread2:
    RequestLock   ; this results in a deadlock

This is actually not a deadlock, but what is known as a "livelock". There will be progress made as soon as the thread that holds the lock is rescheduled. The most important thing is that there is progress being made toward the lock being released by the holder, so this is not yet a deadlock.

--Peace out,
gravaera

[rdos]

I think bts can be used instead of cmpxchg with no adverse side effects. The states are slightly changed. Bit 0 in the state is the "busy bit", and thus state 2 is changed to state 3 (has the busy bit set). Luckily, rcr will go through the correct states (3 -> 1 -> 0).

Code: Select all

lock:
    lock bts val,0
    jnc done

retry:
    mov al,3
    xchg al,val
    or al,al
    jz done

    futex_wait(&val, 3):
    jmp retry

done:
    ret

unlock:
    clc
    lock rcr val,1
    jnc done

    xor al,al
    mov val,al

    futex_wake(&val, 1)

done:

[bluemoon]

On 486+ you can use xadd.
On 386 you may need a spinlock(lock xchg/bts)+integer, which itself packed into single word, to form a multi-value semaphore - it sound slow, but it's doggy 386 anyway.

[Combuster]

A critical section is a code path which should not be interrupted mid-execution, or else the operation being performed will be at risk of failure.

Interruption is the least of your problems:

In concurrent programming a critical section is a piece of code that accesses a shared resource (data structure or device) that must not be concurrently accessed by more than one thread of execution

I think atomic_dec would be lock sub val,1, and this would set ZR flag if the result becomes 0, and CY flag if the result becomes -1

SF and ZF collectively determine positive, negative, or zero. CF specifically determines the 0 -> -1 transition, so for a locked sub you have four distinct outcomes you can act on. A lock add only has three because CF will equal ZF, lock inc/dec preserve CF and therefore are limited to the first three cases as well (which is why you want to use sub instead of dec).

Write out the cases then shift around the associated values to solve the rest of the puzzle

[gerryg400]

Rdos, I also used that doc as a reference to develop my futures. Unfortunately that document doesn't explain exactly what part the kernel plays in getting futures to work correctly. So this is what I came up with. I would be interested to see whether you agree with this logic.

FutexWait()

Code: Select all

1. Lock the futex queue.
2a. IF (the user-space variable no longer indicates that queueing is required AND there is no-one in the futex queue)
                unlock the futex queue
                return to user space for a retry (original thread will retry)
2b. ELSEIF (the user-space variable no longer indicates that queueing is required AND there is someone in the futex queue)
                add the current thread to the tail of the futex queue
                schedule the thread at the head of the futex queue
                unlock the futex queue
                return to user space for a retry (long waiting thread will retry)
2c. ELSE
                add the current thread to the tail of the futex queue
3. Unlock the futex queue
4. Schedule

FutexWake()

Code: Select all

1. Lock the futex queue.
2. IF (there is a thread in the futex queue)
                schedule the thread
3. Unlock the futex queue

[rdos]

I happened to edit the post instead of replying.

Here is the x86 method from above:

Code: Select all

lock:
    lock bts val,0
    jnc done

retry:
    mov al,3
    xchg al,val
    or al,al
    jz done

    futex_wait(&val, 3):
    jmp retry

done:
    ret

unlock:
    clc
    lock rcr val,1
    jnc done

    xor al,al
    mov val,al

    futex_wake(&val, 1)

done:

[gerryg400]

rdos, is the following atomic ? I'm afraid I don't know enough asm to be sure.

Code: Select all

    xchg al,val

It needs to be atomic so that 2 cores don't swap a 0 out at the same time. Perhaps you need a lock prefix there.

[edit] I just read that lock is implied with this instruction.

[rdos]

Rdos, I also used that doc as a reference to develop my futures. Unfortunately that document doesn't explain exactly what part the kernel plays in getting futures to work correctly. So this is what I came up with. I would be interested to see whether you agree with this logic.

At least I agree that this isn't properly described, which probably has to do with more interest in using the Futex in Linux than implementing the kernel functionality.

FutexWait()

Code: Select all

1. Lock the futex queue.
2a. IF (the user-space variable no longer indicates that queueing is required AND there is no-one in the futex queue)
                unlock the futex queue
                return to user space for a retry (original thread will retry)
2b. ELSEIF (the user-space variable no longer indicates that queueing is required AND there is someone in the futex queue)
                add the current thread to the tail of the futex queue
                schedule the thread at the head of the futex queue
                unlock the futex queue
                return to user space for a retry (long waiting thread will retry)
2c. ELSE
                add the current thread to the tail of the futex queue
3. Unlock the futex queue
4. Schedule

In my possible implementation, there is really only one value passed to the futex entry-point (3), so I suspect that I would want to do it like this (value is not passed as a parameter):

Code: Select all

kernel_lock_futex:
    LockKernel    ; take an exclusive lock
    mov al,val
    cmp al,3
    jnz unlock_scheduler

    Block
    jmp done

unlock_scheduler:
   UnlockKernel

done:
    ret 

FutexWake()

Code: Select all

1. Lock the futex queue.
2. IF (there is a thread in the futex queue)
                schedule the thread
3. Unlock the futex queue

That does seem pretty reasonable

[gerryg400]

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.

[rdos]

On 486+ you can use xadd.
On 386 you may need a spinlock(lock xchg/bts)+integer, which itself packed into single word, to form a multi-value semaphore - it sound slow, but it's doggy 386 anyway.

Actually, by a lucky circumstance, it seems like cmpxchg can be replaced by bts on bit 0, and atomic_dec can be replaced by rcr. This means there are states 0, 1 and 3 (instead of 0, 1 and 2), and it works on 386.