Critical sections in userspace without syscalls?

[rdos]

There actually is a 386 solution. It is possible to change cmpxchg to add. The results for cmpxchg is that 0->1, 1->1 and 2->2. However, the line after a failed cmpxchg sets 1->2, so in essence the function is 0->1, 1->2 and 2->2. An add would be very similar. The only difference is that 2->3, and that if many threads execute the initial add only, the value could go up considerably. However, if a 16 bit value is used up to 65535 threads could try to access the mutex at the same time without the counter rolling over. For practical purposes, this will be fine. Owen's optimization to overlay the thread-id with the value will not work, but that is of minor importance.

In order to use add/sub, the value range must also change. The initial vaule should be -1, and then CF will be checked in order to detect the fast paths.

At the kernel side, there will be a check if value is -1, 0 or something else. Values -1 and 0 will exit the acquire syscall.

Code: Select all

struct mutex
{
    int handle;
    int counter;
    short int val;
    short int owner;
};

; es:edi contains mutex

init:
    push edi
    lea edi,[edi].val
    ebx = RdosCreateFutex(es:edi)
    pop edi
    mov [edi].handle,ebx
    mov [edi].val,-1
    mov [edi].counter,0
    mov [edi].owner,0
    ret

lock:
    str eax
    cmp ax,[edi].owner
    jne lock_do

    inc [edi].counter
    ret

lock_do:
    lock add [edi].val,1
    jc lock_take

lock_retry:
    mov ax,1
    xchg ax,[edi].val
    cmp ax,-1
    je lock_take

    mov ebx,[edi].handle
    RdosAcquireFutex(ebx)

    jmp lock_retry

lock_take:
    str eax
    mov [edi].owner,ax
    mov [edi].counter,1
    ret

unlock:
    str eax
    cmp ax,[edi].owner    ; check owner for safety
    jne unlock_done

    sub [edi].counter,1
    jnz unlock_done

    mov [edi].owner,0
    lock sub [edi].val,1       
    jc unlock_done             

    mov [edi].val,-1
    mov ebx,[edi].handle
    RdosReleaseFutex(ebx)

unlock_done:
    ret

[rdos]

I plan to provide the more efficient userspace mutexes (which I call critical sections), transparently. Today, the code patcher will patch a syscall when it encounters these instructions. However, I've provided new hooks so the loader can provide a different patch that is the near call to the fast mutexes that are based on futexes. This part of the patching procedure now works for flat applications using PE-format. Now I only need to implement the kernel part (the futexes) before I can make some serious tests.

[rdos]

Some more redesigns.

In order to provide a "safe" (and compatible) interface I changed the idea about returning an address to the mutex data structure. Instead I predefine a maximum number of mutexes that a process can create (currently 1024), and allocate linear space for an index array + the actual mutex data (which then is 16 * 1024 bytes). I then initialize the index array with zeros. The interface will work with indexes into the array (1..1024), which is safer.

Then I used the original futex-idea so now I don't allocate the handle at initialization time, rather only when a thread is about to block. Since I don't want to expose kernel data (and especially not scheduler lists) to applications, I still use the handle concept. When the first thread is about to block, it acquires a kernel lock, allocates the handle (and thus the block-list) and fills in the handle in the userlevel mutex data structure. The next time something is blocked, the stored handle will be dereferenced, which is much faster than looking up physical addresses. The application cannot forge the handle to manipulate scheduler lists. When a mutex no longer is used, the application should delete it, and then also possibly free the handle if it is allocated.

The nice thing is that the whole sequence of create, acquire, release and delete a mutex can be done without syscalls if there is no contention.

[rdos]

OK, so now I've implemented the kernel-side also, and made some tests.

The test code looks like this

Code: Select all

void test_thread(char mych)
{
    for (;;)
    {
        Section.Enter();
        WriteChar(mych);
        Section.Leave();
    }
}

It runs fine with 2 threads on a dual-code PC, as well as with 3 threads on a dual-core and 6-core PC.

However, there is a problem with fairness. Since the code takes the mutex almost immediately after releasing it, most of the time the woken-up threads will have no time to activate and compete for the mutex, so frequently the same thread will run multiple rounds before it accidently loose the race. It is worse on the 6-core AMD Athlon, probably because it is much faster.

A possible solution is to force a reschedule every time the futex_release syscall is called, but that would also slow down the code when it is less extreme than in this case.

Edit:
A more elaborate test:

Code: Select all

char someval;

void test_thread(char mych)
{
    for (;;)
    {
        Section.Enter();
        someval = mych;
        WriteChar(mych);
        if (someval != mych)
            for (;;)
                 ;
        Section.Leave();
    }
}

The code never gets to the infinite loop, which should be an indication that no more than one thread could be in the protected section.

[Nable]

What about calling (with some condition checking) smth like sched_yield from the application if you want fairness? Such mixture of preemption and cooperative multitasking.
Else it's a scheduler task to provide fairness by keeping some trace counters for threads and preempting those who have the highest values of, for example, section_acquire counter.

[rdos]

What about calling (with some condition checking) smth like sched_yield from the application if you want fairness? Such mixture of preemption and cooperative multitasking.
Else it's a scheduler task to provide fairness by keeping some trace counters for threads and preempting those who have the highest values of, for example, section_acquire counter.

The example is quite extreme because it takes perhaps 100 times as long to execute the protected code compared to retake the mutex. That will hardly ever happen in real situations.

I tried to do a yield in the release_futex call, but it doesn't do much good. About the only effect is that it consumes a lot of cycles which in itself increases chances for another core / thread to win the race for the mutex.

I think I just let it be. No sense in optimizing for unlikely cases.

[Owen]

If the futex was contented, then the unlocker knows this and has to call into the kernel. If you're already in the kernel, surely it can't be that expensive to

• Pick the first task off the waiting list
• Rewrite the futex (which is still in the locked state) to be locked by this task
• Unblock the task

No need to (necessarily) immediately go for a full schedule - but in doing this you've (inexpensively, one hopes) guaranteed fairness

[rdos]

If the futex was contented, then the unlocker knows this and has to call into the kernel. If you're already in the kernel, surely it can't be that expensive to

• Pick the first task off the waiting list
• Rewrite the futex (which is still in the locked state) to be locked by this task
• Unblock the task

No need to (necessarily) immediately go for a full schedule - but in doing this you've (inexpensively, one hopes) guaranteed fairness

What happens is this:

• The owner releases the futex (setting it to "free"), and then unblocks one thread
• The owner then exists the release code, and directly enters the lock code again
• If the woken-up thread hasn't been activated yet, the previous owner will take the futex again (it's free)
• The woken-up thread is activated, and tries to take the futex, but it can't because it is already taken, and thus will be blocked again

What is needed to avoid this scenario is that the thread that unblocks one thread cannot be allowed to continue until the unblocked thread is running. This means it must be preempted. It is a race-condition.

I might look into Owen's solution above where the thread that releases the futex will set the unblocked thread to the owner of the futex. That could work, especially since owner is the task selector, which is easily available when unblocking. The retry code also must be changed so a retrying thread first checks if it is the owner, and if it is, just exists the acquire procedure. Additionally, the thread that unblocks one thread probably shouldn't set the mutex to "free" before it does the unblock syscall. To ensure fairness, it should set it to "contended".

[rdos]

OK, updated code according to Owen's idea (and with the user-handle concept):

Code: Select all

struct mutex
{
    int handle;
    int counter;
    short int val;
    short int owner;
};

; create new mutex
; returns handle in ebx

create:
    push eax
    push ecx
    push edx
    push edi

    mov edx,OFFSET handle_tab
    mov edi,edx
    mov ecx,MAX_SECTIONS
    repnz scasd                                     ; search for free handle

    stc
    jnz create_done                               ; no free handles

    mov ebx,MAX_SECTIONS
    sub ebx,ecx
    push ebx                                         ; ebx now is the handle (1-based index)

    dec ebx
    sub edi,4                                        ; edi is the handle table index
    mov eax,12
    mul ebx
    add eax,4 * MAX_SECTIONS           
    mov edx,eax
    add edx,OFFSET handle_tab              ; edx is the mutex entry itself
    mov [edi],edx                                 ; save address to mutex in index array

    mov [edx].handle,0                          ; initialize mutex
    mov [edx].val,-1
    mov [edx].counter,0
    mov [edx].owner,0

    pop ebx
    clc

create_done:
    pop edi
    pop edx
    pop ecx
    pop eax
    ret

; free mutex
; ebx is handle

free:
    push edx

    sub ebx,1
    jc free_done

    cmp ebx,MAX_SECTIONS            ; check that hande is in range
    jae free_done

    shl ebx,2
    add ebx,OFFSET handle_tab
    xor eax,eax
    xchg eax,[ebx]                         ; mark  handle as free
    or eax,eax
    jz free_done

    mov ebx,eax
    mov eax,[ebx].handle                ; check if a kernel contention handle has been allocated
    or eax,eax
    jz free_done

    FreeFutex(ebx)                        ; free kernel side handle                      

free_done:
    xor ebx,ebx
    pop edx
    ret

; lock mutex
; ebx is handle

lock:
    push eax
    push edx

    sub ebx,1
    jc lock_done                             ; invalid zero handle

    cmp ebx,MAX_SECTIONS
    jae lock_done                          ; index out of range

    shl ebx,2
    add ebx,OFFSET handle_tab
    mov ebx,[ebx]
    or ebx,ebx
    jz lock_done                            ; not allocated

    str ax
    cmp ax,[ebx].owner
    jne lock_do                            ; already owned?

    inc [ebx].counter
    jmp lock_done

lock_do:
    lock add [ebx].val,1
    jc lock_take

    mov eax,1
    xchg ax,[ebx].val                   ; double check so it isn't free, and avoid the "roll-over" problem
    cmp ax,-1
    jne lock_block

lock_take:
    str ax                                 ; set as owner
    mov [ebx].owner,ax
    mov [ebx].counter,1
    jmp lock_done

lock_block:
    RdosAcquireFutex(ebx)          ; block

lock_done:
    pop ebx
    pop eax
    ret

; unlock mutex
; ebx is handle

unlock:
    push eax
    push ebx

    sub ebx,1
    jc unlock_done              ; invalid zero handle

    cmp ebx,MAX_SECTIONS
    jae unlock_done               ; index out of range

    shr ebx,2
    add ebx,OFFSET handle_tab
    mov ebx,[ebx]
    or ebx,ebx
    jz unlock_done                ; not allocated

    str ax
    cmp ax,[ebx].owner 
    jne unlock_done              ; check that owner is correct

    sub [ebx].counter,1
    jnz unlock_done             

    mov [ebx].owner,0
    lock sub [ebx].val,1       
    jc unlock_done                  ; go if not contended

    mov [ebx].val,-1                 ; temporarily set to free to handle race condition with wakeup
    RdosReleaseFutex(ebx)

unlock_done:
    pop ebx
    pop eax
    ret

Edit: When the acquire call returns from kernel, the kernel can ensure that the mutex is always owned, and thus there is no need to check after the blocking call returns.

Edit2: In order to handle race conditions it is necesary to set the mutex to free before doing the release futex syscall.

[rdos]

Here is the kernel-side, with some pseudo-code:

Code: Select all

; acquire futex
; es:ebx is address of mutex data

acquire_futex:
    push ds
    push fs
    push eax
    push ebx
    push cx
    push esi
;    
    mov esi,ebx          
;
    mov ebx,es:[esi].fs_handle
    mov ax,FUTEX_HANDLE
    DerefHandle                                ; try to deref kernel handle
    jnc acquire_no_sect                
;    
    mov ax,task_sel
    mov ds,ax
    EnterSection ds:futex_section       ; take a kernel mutex to ensure only one kernel handle is allocated
;
    mov ebx,es:[esi].fs_handle
    mov ax,FUTEX_HANDLE
    DerefHandle                                ; retry with lock
    jnc acquire_handle_ok
;
    mov cx,SIZE futex_handle_seg
    AllocateHandle                             ; allocate kernel handle
    mov ds:[ebx].fh_list,0                   ; clear block-list
    mov ds:[ebx].fh_lock,0                  ; initialize spinlock
    mov [ebx].hh_sign,FUTEX_HANDLE   ; set to this handle-type
;
    movzx eax,[ebx].hh_handle
    mov es:[esi].fs_handle,eax             ; save handle in user-level mutex

acquire_handle_ok:
    push ds
    mov ax,task_sel
    mov ds,ax
    LeaveSection ds:futex_section        ; release handle mutex
    pop ds

acquire_no_sect:
    call LockCore                               ; lock core so no scheduling can happen
    call cs:lock_futex_proc                  ; take mutex spinlock
    mov ax,1
    xchg ax,es:[esi].val                  ; make sure nobody just left the section
    cmp ax,-1
    je acquire_take
;
    mov ax,ds
    push OFFSET acquire_done            ; save resume-point on stack
    call SaveLockedThread                  ; save thread state
;
    mov ds,ax
    lea edi,[ebx].fh_list     
    mov es,fs:ps_curr_thread
    mov fs:ps_curr_thread,0
;
    call InsertBlock32                        ; block into block list
    call cs:unlock_futex_proc             ; release spinlock
;
    mov es:p_sleep_sel,ds
    mov es:p_sleep_offset,edi    
    jmp LoadThread                         ; schedule

acquire_take:
    str ax
    mov es:[esi].owner,ax                ; set self to owner
    mov es:[esi].counter,1                 
    call cs:unlock_futex_proc            ; free mutex spinlock
    call UnlockCore                          ; unlock scheduler
    
acquire_done:
    pop esi
    pop cx
    pop ebx
    pop eax
    pop fs
    pop ds    
    ret

; release futex
; es:ebx address of user-level mutex data

release_futex:
    push ds
    push fs
    push eax
    push ebx
    push cx
    push esi
;
    mov esi,ebx                            ; save user-level base in esi
    mov ebx,es:[esi].handle
    mov ax,FUTEX_HANDLE
    DerefHandle                           ; dereference handle
    jc release_done
;
    call LockCore                         ; lock scheduler
    call cs:lock_futex_proc            ; take futex spinlock
;
    mov ax,ds:[ebx].fh_list
    or ax,ax
    jz release_unlock                    ; check if somebody is blocked, go if not
;    
    mov ax,1
    xchg ax,es:[esi].val                ; try to acquire the mutex
    cmp ax,-1
    jne release_unlock                  ; if somebody already has it, go
;
    push di    
;
    push es
    push esi    
    lea esi,ds:[ebx].fh_list
    call RemoveBlock32                 ; remove a waiting thread
    mov es:p_data,0
    mov cx,es                             ; save thread block
    mov di,es:p_tss_sel               ; get task selector of waiting thread
    pop esi
    pop es
;
    mov es:[esi].owner,di             ; set owner
    mov es:[esi].counter,1            ; set count
;
    call cs:unlock_futex_proc         ; release mutex spinlock
;
    push es
    mov es,cx                              ; restore thread block
    cli
    mov di,OFFSET ps_wakeup_list
    call InsertCoreBlock                 ; insert unblocked thread into wakeup list
    sti
    pop es
;    
    pop di
    call UnlockCore                       ; unlock scheduler
    jmp release_done

release_unlock:
    call cs:unlock_futex_proc        ; release mutex spinlock
    call UnlockCore                      ; unlock scheduler
    
release_done:
    pop esi
    pop cx
    pop ebx
    pop eax
    pop fs
    pop ds    
    ret

Edit: Made some more modifications. In essence, what the release_futex syscall does is that it tries to acquire the futex in kernel if somebody is blocked, and then hands it over to the blocked thread. That means the functionality is very similar. It is necesary to set the futex to free before starting to do this because otherwise a concurrent acquire can be on it's way on another core, but still not having lead to a blocked thread.

Edit2: Changed registers as the address of the kernel handle data was destroyed.

[rdos]

In order to implement this design in long mode, there is a need for a slight modification. The owner no longer can be determined by using str (task register) since TR is loaded with a per-core value. There is a need for a different thread indicator in long mode. I think a good one is bits 30-39 of application RSP. This is because thread stacks are allocated with 1G alignment from a specific address-range. The identification can be provided as a new parameter to the acquire and release calls, or be determined through the task structure. The latter probably is better since this can be used transparently. When the syscalls determine the thread is running in long mode, it would use the identification in the task structure instead of TR as owner.

[Combuster]

I think a good one is bits 30-39 of application RSP.

I see an exploit coming soon.

[rdos]

I think a good one is bits 30-39 of application RSP.

I see an exploit coming soon.

Anything that is in the user-part of structure can be abused by user-mode, which includes the owner field. Thus, you don't need an "exploit", you can already do it in 32-bit by setting owner to anything you like. The owner field is not used for anything in kernel, other than as an indicator of who user-mode set to owner. If all the exploit is for is to mark the section as occupied, it is easier to do with an acquire call

[rdos]

Update:

There is a new field in the thread structure called p_futex_id, which kernel side uses to match owner. In 32-bit mode, this field is set to TR on thread creation. In 64-bit mode, the long mode monitor will use bits 30-46 of the newly created thread's RSP as the id, and call a register function in the scheduler to set p_futex_id to this value. At the user-mode side, 32-bit will use str for the owner field, while 64-bit mode will use current RSP bits 30-46.

[FallenAvatar]

If it wasn't an issue, why did you suddenly update us with how you "fixed" it?

- Monk