Types of spinlocks (I need a new type!)

[rdos]

My typical spinlocks looks like this:

Code: Select all

RequestSpinLock Proc

reqSpin:
    mov ax,ds:timer_spinlock
    or ax,ax
    je reqGet
;
    sti
    pause
    jmp reqSpin

reqGet:
    cli
    inc ax
    xchg ax,ds:timer_spinlock
    or ax,ax
    jne reqSpin
    ret
RequestSpinLock   Endp

ReleaseSpinLock  Proc near
    mov ds:timer_spinlock,0
    sti
    ret
ReleaseSpinLock Endp

These work between cores, and also between baseline code and IRQs on a specific core since they disable interrupts. The sections of code protected by these types of spinlocks must be short in order not to kill interrupt performance. For obvious reasons, they are not nestable, since nesting would imply the inner spinlock would enable interrupts, which is not allowed. If interrupts are enabled within the spinlock, deadlocks with IRQs could occur.

This kind of spinlock cannot protect the schduler as it switches threads. First because the scheduler uses other spinlocks (nesting not allowed), and secondly because the code to switch threads is too long.

The scheduler instead has an within core protection mechanism (and keeps local lists of available threads).

The first set of locks are only allowed to be called within basline code (not from IRQs or other asynchronous callbacks like timers):

Code: Select all

LockCore      Proc near
    push word ptr core_data_sel
    pop fs
    add fs:ps_nesting,1
    jc lcDone
;
    CrashGate                ; this is an error, so panic!

lcDone:     
    mov fs,fs:ps_sel
    ret
LockCore      Endp

UnlockCore    Proc near
    push ax
    
ucRetry:    
    cli
    sub fs:ps_nesting,1
    jc ucNestOk
;
    CrashGate               ; this is an error so panic!

ucNestOk:    
    test fs:ps_flags,PS_FLAG_TIMER      
    jnz ucSwap
;    
    mov ax,fs:ps_wakeup_list    ; check if something happened while scheduler was locked
    or ax,ax
    jz ucDone

ucSwap:
    add fs:ps_nesting,1        ; relock
    jnc ucRetry
;
    sti
    push OFFSET ucDone
    call SaveLockedThread          ; schedule
    jmp ContinueCurrentThread

ucDone:
    sti
    pop ax
    ret
UnlockCore    Endp

The second set of locks are called by ISRs (it's automatically part of the entry/exit portion of ISRs) and when timers fire:

Code: Select all

TryLockCore   Proc near
    push word ptr core_data_sel
    pop fs
    add fs:ps_nesting,1
    mov fs,fs:ps_sel
    ret
TryLockCore   Endp

TryUnlockCore    Proc near
    push ax
    
tucRetry:    
    cli
    sub fs:ps_nesting,1
    jnc tucDone
;
    mov ax,fs:ps_curr_thread
    or ax,ax
    jz tucDone
;    
    test fs:ps_flags,PS_FLAG_TIMER      
    jnz tucSwap
;    
    mov ax,fs:ps_wakeup_list
    or ax,ax
    jz tucDone

tucSwap:
    add fs:ps_nesting,1
    jnc tucRetry
;
    sti
    push OFFSET tucDone
    call SaveLockedThread
    jmp ContinueCurrentThread

tucDone:
    sti
    pop ax
    ret
TryUnlockCore    Endp

The scheduler locks can make sure that a thread cannot be scheduled away from until the lock is returned to default (ps_nesting = -1). Within these sections of code interrupts are enabled, and spinlocks can be accessed. The lock works well when threads get blocked, if the thread is put into the block-list after it's state is saved. If it is put into some block list earlier than that, it could malfunction on multicore, but not on singlecore.

The Signal/WaitforSignal synchronization primitive is one case where the thread must be placed in the block-list before it's state is saved. This is because this pair must garantee that WaitForSignal should be exited regardless if Signal is done before, during or after the WaitForSignal call. On singlecore, this pair works well, but it seems to occasionally malfunction on multicore.

What is needed to protect Signal/WaitForSignal is a spinlock on the thread involved. However, the above spinlock cannot be used (code is too long, and it accesses other spinlocks). What would be needed is a spinlock that doesn't disable interrupts, and thus cannot tolerate reentrancy from IRQs. However, the environment in the scheduler locked section is such that this spinlock can be placed in sections that are garanteed to be non-IRQ (baseline code), and thus it should never deadlock with IRQs on the same core.

It could look like this:

Code: Select all

RequestThreadLock Proc

reqSpin:
    mov ax,es:p_spinlock
    or ax,ax
    je reqGet
;
    pause
    jmp reqSpin

reqGet:
    inc ax
    xchg ax,es:p_spinlock
    or ax,ax
    jne reqSpin
    ret
RequestThreadLock   Endp

ReleaseThreadLock  Proc near
    mov es:p_spinlock,0
    ret
ReleaseThreadLock Endp

How are others doing this, or is it simply not allowed to wakeup threads from ISRs?

[gerryg400]

How are others doing this, or is it simply not allowed to wakeup threads from ISRs?

I allow ISRs to interrupt system calls, and of course in the multicore case they can execute at the same time. There are some spinlocks to protect structures but they are fairly short.

To make things simple my interrupts never call the scheduler, instead they queue an event which is processed when the interrupt is complete. If an interrupt happens while the scheduler is executing then the event for that interrupt will possibly cause the scheduler to run again when it finishes. Not all interrupt events cause a re-schedule, some are messages and are put in a message queue for a userspace driver.

I use a global variable per core to track the kernel nesting level. 0 means userspace and 1 or more means the kernel. Whenever I'm leaving the kernel I check and if the nesting level is going from 1 to zero I call the scheduler.

My locks are r/w ticketed spinlocks although I've found in practice I rarely use the RO lock and it was probably a waste to implement it. I have 4 locks (spinlock, spinlock_ro, spinlock_irq and spinlock_ro_irq). spinlock_irq is mainly used. I use the same function to unlock both read and write locks.

[Combuster]

since nesting would imply the inner spinlock would enable interrupts

And so our self-proclaimed ASM expert demonstrates he lacks the necessary knowledge to use the oldest instructions in the book: PUSHF/POPF.

Welcome to being human, rdos.

[rdos]

since nesting would imply the inner spinlock would enable interrupts

And so our self-proclaimed ASM expert demonstrates he lacks the necessary knowledge to use the oldest instructions in the book: PUSHF/POPF.

Of course I know, but nesting spinlocks is still unacceptable because of interrupt latences. For that reason, I explicitly enable interrupts because after the spinlock is done it should always enable interrupts. There is also another reason for this. If spinlocks should be nestable, the spinloop itself must be executed with interrupts disabled, which is also unacceptable.

[turdus]

I've something like

Code: Select all

lockcheck:
bts qword [offset], lockid
jc ok
call yield
jmp lockcheck
ok:

offset points to a memory that's per cpu mapped, lockid would be 0..63. In case of inter cpu locks, bts is prefixed by "lock", and offset points to word on a globally mapped page. Yield is function to pick the next runnable thread in queue. I do not allow interrupts within ISRs. My code is much much clearer this way, and it's not a problem because ISRs are really short and fast (couple dozen cycles only). They just enqueue an irq arrived message in the appropriate device driver's event queue, and mark it as runnable if it was blocked.

Releasing a lock is simple as

Code: Select all

btr qword [offset], lockid

[Brendan]

Hi,

I usually only have 2 types of spinlocks that are both the same except one disables IRQs (using the "pushfd; cli; popfd" method). Both types disable task switches because you should never do a task switch while you're holding a spinlock.

The way this works is that the spinlock increases a (per CPU) "number of locks held" variable. If any code attempts to do a task switch, the scheduler checks to make sure the "number of locks held" variable is zero - if it is zero the task switch happens like normal, and if it's non-zero the scheduler sets a (per CPU) "task switch postponed" flag and doesn't do the task switch at all.

When the spinlock is released, you decrease the "number of locks held" variable, and if it was decreased to zero you check the "task switch postponed" flag. If this flag is set you know that one or more task switches were postponed, and call the scheduler then.

The macro to acquire a spinlock might look something like this:

Code: Select all

    cmp dword [<address_of_lock>],0
    je .tryLock
.testLock:
    pause
    cmp dword [<address_of_lock>],0
    jne .testLock

.tryLock:
    ;pushfd                 ;Only for "IRQ lock"
    ;cli                    ;Only for "IRQ lock"
    lock bts [<address_of_lock>],0
    jnc .gotLock
    ;popfd                  ;Only for "IRQ lock"
    jmp .testLock

.gotLock:
    inc dword [gs:CPUstructure.locksHeld]

And the macro to release a spinlock might look something like this:

Code: Select all

    pushfd                  ;Remove for "IRQ lock"
    cli                     ;Remove for "IRQ lock"

    mov dword [<address_of_lock>],0
    sub dword [gs:CPUstructure.locksHeld],1
    je .done

    cmp dword [gs:CPUstructure.taskSwitchesPostponedFlag],0
    je .done
    mov dword [gs:CPUstructure.taskSwitchesPostponedFlag],0
    call doTaskswitch

.done:
    popfd

since nesting would imply the inner spinlock would enable interrupts

And so our self-proclaimed ASM expert demonstrates he lacks the necessary knowledge to use the oldest instructions in the book: PUSHF/POPF.

Of course I know, but nesting spinlocks is still unacceptable because of interrupt latences. For that reason, I explicitly enable interrupts because after the spinlock is done it should always enable interrupts. There is also another reason for this. If spinlocks should be nestable, the spinloop itself must be executed with interrupts disabled, which is also unacceptable.

For nested locks, it really depends on how the locks are used. If the critical section is tiny and the chance of lock contention is very small then it's fine.


Cheers,

Brendan

[rdos]

I think I understand why this malfunctions on multicore now, but the new solution would not work either. Below RequestThreadLock/ReleaseThreadLock disables interrupts.

Code: Select all

ClearSignal Proc
    mov es:p_signal,0
    ret
ClearSignal End

; this code handles the ps_wakeup_list deep inside the scheduler:

load_thread_wakeup_loop:    
    cli
    mov si,OFFSET ps_wakeup_list
    mov ax,fs:[si]
    or ax,ax
    jz load_thread_wakeup_done
;
    call RemoveCoreBlock
    sti

; run highest prio thread (which includes this one)


Signal  Proc 
    call TryLockCore
    call RequestThreadLock
    mov es:p_signal,1
    mov ax,es:p_sleep_sel
    cmp ax,SLEEP_SEL_SIGNAL
    jne signal_unlock
;
    push di
    mov di,OFFSET ps_wakeup_list
    call InsertCoreBlock                          ; this code must run with interrups disabled
    pop di

signal_unlock:
    call ReleaseThreadLock
    call TryUnlockCore
    
signal_done:       
    ret
Signal   Endp

WaitForSignal Proc
    call LockCore    
    mov es,fs:ps_curr_thread
    call RequestThreadLock
    xor al,al
    xchg al,es:p_signal
    or al,al
    jnz wait_for_signal_unlock
;
    mov es:p_sleep_sel,SLEEP_SEL_SIGNAL

;ReleaseThreadLock is currently here (doesn't work because another core could wakeup and start it before save is done)
;    call ReleaseThreadLock

    push OFFSET wait_for_signal_clear
    call SaveLockedThread                                  ; save thread state

;ReleaseThreadLock must be here (but that makes the code reenter spinlocks and hold them too long)
    call ReleaseThreadLock
    mov fs:ps_curr_thread,0
    jmp LoadThread                                           ; block and schedule

wait_for_signal_clear:
    mov ax,core_data_sel
    mov fs,ax
    mov es,fs:ps_curr_thread
    mov es:p_signal,0
    jmp wait_for_signal_done

wait_for_signal_unlock:
    call ReleaseThreadLock
    call UnlockCore

wait_for_signal_done:       
    ret
WaitForSignal Endp

The problem is that Signal can (and do) execute in ISRs, and might interrupt the WaitForSignal call on the same core, which would lead to a deadlock. If interrupts are disabled so this cannot happen, the old solution will malfunction because another core could place the thread in its ready-list and start executing it before the first core can save the register context (a relatively long procedure that also calculates elapsed time).

The solution might be to swap locks before save and use a new lock that doesn't disable interrupts (which would be the one the scheduler uses when it wakes up threads in the ps_wakeup list).

I think I have a solution now. By using one lock that leaves interrupts enabled (call it RequestStiLock/ReleaseStiLock) and one that disables interrupts (call it RequestCliLock/ReleaseCliLock):

Code: Select all

ClearSignal Proc
    mov es:p_signal,0
    ret
ClearSignal End

; this code handles the ps_wakeup_list deep inside the scheduler:

load_thread_wakeup_loop:    
    cli
    mov si,OFFSET ps_wakeup_list
    mov ax,fs:[si]
    or ax,ax
    jz load_thread_wakeup_done
;
    call RemoveCoreBlock
    sti
    call RequestStiLock                  ; access the lock so the core cannot start it until its state has been saved
    call ReleaseStiLock

; run highest prio thread (which includes this one)


Signal  Proc 
    call TryLockCore
    call RequestCliLock
    mov es:p_signal,1
    mov ax,es:p_sleep_sel
    cmp ax,SLEEP_SEL_SIGNAL
    jne signal_unlock
;
    push di
    mov di,OFFSET ps_wakeup_list
    call InsertCoreBlock                          ; this code must run with interrups disabled
    pop di
    mov es:p_sleep_sel,0
    mov es:p_signal,0                            ; clear the signal here instead so another core can set it again before the wakeup is done.

signal_unlock:
    call ReleaseCliLock
    call TryUnlockCore
    
signal_done:       
    ret
Signal   Endp

WaitForSignal Proc
    call LockCore    
    mov es,fs:ps_curr_thread
    call RequestStiLock
    xor al,al
    call RequestCliLock
    xchg al,es:p_signal
    or al,al
    jnz wait_for_signal_unlock
;
    mov es:p_sleep_sel,SLEEP_SEL_SIGNAL
    call ReleaseCliLock
    push OFFSET wait_for_signal_done
    call SaveLockedThread                                  ; save thread state
    call ReleaseStiLock
    mov fs:ps_curr_thread,0
    jmp LoadThread                                           ; block and schedule

wait_for_signal_unlock:
    call ReleaseCliLock
    call ReleaseStiLock
    call UnlockCore

wait_for_signal_done:       
    ret
WaitForSignal Endp

[rdos]

I usually only have 2 types of spinlocks that are both the same except one disables IRQs (using the "pushfd; cli; popfd" method). Both types disable task switches because you should never do a task switch while you're holding a spinlock.

Yes, but as long as the code executes with cli task switches couldn't happen (unless you use NMI). There might also be other reasons for not allowing task-switching, or the code could take several spinlocks after each others and the code as a whole might need to be executed without task-switching. That is why I prefer a distinct function to disable task-switching.

The way this works is that the spinlock increases a (per CPU) "number of locks held" variable. If any code attempts to do a task switch, the scheduler checks to make sure the "number of locks held" variable is zero - if it is zero the task switch happens like normal, and if it's non-zero the scheduler sets a (per CPU) "task switch postponed" flag and doesn't do the task switch at all.

When the spinlock is released, you decrease the "number of locks held" variable, and if it was decreased to zero you check the "task switch postponed" flag. If this flag is set you know that one or more task switches were postponed, and call the scheduler then.

Sounds somewhat similar to my solution.

[rdos]

I just tested the combination of a sti and a cli spinlock, and it seems to work. It also seems to eliminate race conditions in the NIC (and possibly in the IDE) driver. Would be interesting to test if this fixes the missing "interrupt" issues on the Compaq CQ57 machine.

[rdos]

Here is an alternative for accessing the lock:

Code: Select all

AccessStiThreadLock Proc
    mov ax,1

accSpin:
    xchg ax,es:p_spinlock
    or ax,ax
    jz accOk
;
    pause
    jmp accSpin

accOk:
    mov es:p_spinlock,ax
    ret
AccessStiThreadLock   Endp

[gerryg400]

Releasing a lock is simple as

Code: Select all

btr qword [offset], lockid

Don't you also sometimes need a memory fence before that btr ? If you use a LOCK prefix in the unlock case as well it might be okay. I'm not 100% sure.

Rdos, there's no fence in your unlock code either. That can cause problems on SMP unless you have a fence, if necessary, in the calling code.

[Brendan]

Hi,

Releasing a lock is simple as

Code: Select all

btr qword [offset], lockid

Don't you also sometimes need a memory fence before that btr ? If you use a LOCK prefix in the unlock case as well it might be okay. I'm not 100% sure.

That needs a LOCK prefix (a memory fence isn't enough).

It's also a good idea to keep different locks on different cache lines, so that you don't get false sharing.


Cheers,

Brendan

[gerryg400]

That needs a LOCK prefix (a memory fence isn't enough).

Are you sure ? Operations that clear individual bits may be okay because only the lock holder will ever clear that bit. The test and the reset don't need to be atomic.

In any event the original code is not guaranteed to be sufficient.

[Brendan]

Hi,

That needs a LOCK prefix (a memory fence isn't enough).

Are you sure ? Operations that clear individual bits may be okay because only the lock holder will ever clear that bit. The test and the reset don't need to be atomic.

The BTR instruction would load something larger (a word, dword or qword depending on operand size), clear one bit, then store the modified value.

For 32-bit operands; if two different BTR instructions running on 2 different CPUs try to clear 2 separate bits at the same time; then they both load the original dword, both clear one bit in their copy, then both store their modified dword. The dword stored by the first CPU gets overwritten when the second CPU stores its dword, and only one of the 2 bits are cleared. The end result is a spinlock that is held by nobody that can't be acquired ever again (probably leading to all CPUs spinning forever soon after that).

Of course this would only happen if multiple CPUs try to release spinlocks at exactly the same time. Depending on a lot of things (which CPUs, how many CPUs, how often locks are released, etc) the OS might lock up 3 times in 10 minutes and then work perfectly fine for 3 months before locking up again. It's not the sort of bug that would be easy to find in a debugger...


Cheers,

Brendan

[gerryg400]

Thanks for clearing that up. I see. I've never used the bit functions so had never really thought it through.

I have a question related to locks. In my spin_unlock function I use a fence whenever I clear a lock so that I don't need to remember to figure out whether to put a fence in my main code.

Do you think this perhaps unnecessary fence would have a big performance penalty ?