Mutexs, Spinlocks and all that jazz

[Kemp]

Hi guys, it's time once again for my weekly post ;D I just need to clarify how to go about protecting sections of non-reentrant code and code that simply must not be interrupted on different types of systems.

So first, we have single CPU systems. For code that can't be interrupted I imagine the obvious solution is to disable interrupts while it's executing. For non-reentrant code I guess it would make most sense to have a semaphore/mutex of some type with the thread giving up its timeslice (or equivalent) while it waits for access to it.

Then we have multi-CPU systems. The solutions should be the same as the above shouldn't they? Code that can't be interrupted can disable the interrupts that are normally routed to that particular CPU (or reroute them to the other CPU temporarily). Mutexs/semaphores and yielding should still have the desired result as well should they not? Even if the code is entered on different CPUs they should be using the same lock and thus they should all still wait and allow other threads to execute.

While I think about it, is there any specific reason to choose spinlocks instead of or in addition to mutexs/semaphores? I appreciate that they cause less reliance on the scheduler, but it seems to be less efficient to sit there spinning than to allow another thread to execute.

Well, there's my thoughts. Any obvious problems here or is it all good?

[Crazed123]

On multi-processor systems two processors can access the same code at the same time, including the locking procedures for a mutex. The only change to be made is that mutexes should be based on Test and Set Lock instructions, which guarantee that only one processor can lock the mutex at once. From there, non-mutex synchronization objects like semaphores should have a built-in mutex so that only one caller can alter their state at once. From there you're roughly good to go.

[mystran]

You can also use any other atomic instruction..

On x86 you got forexample XCHG and then LOCK prefix which works with some of the arithmetics.

My own implementation for partially userspace semaphores goes with LOCK prefixed INC/DEC, as described in http://www.cs.hut.fi/~tvoipio/threads.html

[Kemp]

On multi-processor systems two processors can access the same code at the same time, including the locking procedures for a mutex.

Yeah, thanks for reminding me about that, I forgot that not only can they be running the same piece of code at the same time, it can even be the same instruction at the same time. My mutex code uses a test-and-set instruction and locks the bus anyway fortunately (it's ripped off of one of Brendan's posts for now, though before I go much further I really need to ask if he minds or write my own).

So all else sounds ok and good then? Anything else you want to chuck at me is welcome, I need to make sure I'm not missing any edge conditions that might be unnoticable when the code's running and then bite me on the @$$ repeatedly.

[Brendan]

Hi,

My mutex code uses a test-and-set instruction and locks the bus anyway fortunately (it's ripped off of one of Brendan's posts for now, though before I go much further I really need to ask if he minds or write my own).

I don't mind at all - especially as I ripped most of mine from the Intel manuals...

So all else sounds ok and good then? Anything else you want to chuck at me is welcome, I need to make sure I'm not missing any edge conditions that might be unnoticable when the code's running and then bite me on the @$$ repeatedly.

There is one issue I'd want to clarify - it's more about design philosophy though...

It might not sound sane, but re-entrancy, etc has nothing to do with code - it's all about data. In general you'll have some sort of data structure that is read by one or more "things" and written to by one or more "things" (where a "thing" includes CPUs and ISRs). The goal is to make sure that each "thing" finds the data in a consistant state and leaves the data in a consistant state.

During design it's best to identify the data structures that will cause problems, then (for each data structure) work out who will be accessing the data and how it will be accessed. Once you've figured this out you'd try to find the "best" way of storing the data and handling accesses.

For a simple example, my last implementation had a system-wide 64-bit time counter. The counter itself is the data, and it is only ever modified by the timer IRQ (which can't be run by more than one CPU at a time due to the IRQ handling hardware - no second IRQ until an EOI is sent). The data was read in lots of places though (from any CPU, both inside and out of IRQ handlers).

Using atomic instructions alone (e.g. "lock add [timerTick], N") wouldn't work because they can't operate on 64 bit integers (at least not without long mode). Spinlocks, mutexes, semaphores, etc also wouldn't work - they'd either cause deadlocks, inaccurate time-keeping or poor efficiency/scalability.

My solution was for the timer IRQ to ignore the highest 32 bits and update the lowest 32 bits atomically. Each CPU would keep a copy of the last known lower 32 bits, and maintain it's own version of the upper 32 bits. When the lower 32 bits overflowed each CPU would know because it's copy would be greater than the timer IRQ's copy, and when overflow was detected each CPU incremented it's own version of the upper 32 bits. For e.g.:

Code: Select all

;Timer IRQ handler - run by one CPU only

timerIRQ:
      push eax
      mov eax,[timerPeriod]
      lock add [timerTickLow],eax
      pop eax
      iretd


;Get timer tick - run by any CPU at any time

getTimerTick:
      pushfd
      cli
      mov eax,[timerTickLow]
      cmp eax,[gs:lastTimerTickLow]      ;Set carry flag if overflow detected
      adc dword [gs:timerTickHigh],0     ;Add carry flag to high 32 bits of timer
      mov [gs:lastTimerTickLow],eax
      mov edx,[gs:timerTickHigh]
      popfd
      ret

Notes: GS points to a "CPU specific" data area, and interrupts are only disabled to ensure that "lastTimerTickLow" and "timerTickHigh" are consistant for the CPU being used (even though another CPU may have completely different values for the same thing in it's own "CPU specific" data area).

The goal is to make sure that each "thing" finds the data in a consistant state and leaves the data in a consistant state - "critical sections" (mutexes, spinlocks, etc) are only one way to achieve this....


Cheers,

Brendan

[Kemp]

Heh, I remember your solution from another thread I know that it's all about the data and that mutexes (mutexs, mutices?) and etc are only one way, but I figure if I get it done coarsely now then I can come up with ingenious solutions like yours once things are working. Eg, I would have locked for operations on the counter in your situation then when I had some spare time I would have thought about it, realised how much locking was actually going on (and how it was affecting things) and tried to find a different way. Of course, the stuff I'm using mutexes for right now is simple things that aren't accessed to often so they're low on the list of things that need "best" solutions.

About your code, the code I stole is spinlock code and I'm not actually using any in my current plans so it might not see execution anyway, lol.

[Brendan]

Hi,

Eg, I would have locked for operations on the counter in your situation then when I had some spare time I would have thought about it, realised how much locking was actually going on (and how it was affecting things) and tried to find a different way.

What locking would you use for the timer IRQ in the example above? A mutex or semaphore (anything that involves a task switch) is just too ugly to think about. A simple spinlock won't work, because if the code to read the counter is interrupted by the timer IRQ you'd get a deadlock.

A spinlock that also disables IRQs would work, but then you'd need to look at "fairness". With 4 or more CPUs, a multi-threaded process (with a thread per CPU) where each thread repeatedly asks to read the time could cause lock starvation on the highest priority IRQ, and therefore block all lower priority IRQs until the timer IRQ handler sends it's EOI. The "fairness" can be more of a problem for NUMA systems (some CPUs are "closer" to the RAM used to store the counter than others) and when there's several CPUs on the same chip that share caches.

At this point you start thinking of using queues to ensure fairness (for generic locks), or perhaps some method of preventing the lock from being acquired when a counter modification is pending (custom locking for the timer), and the "simple" solution starts looking more complicated than the complicated solution...

It's probably fair to say I've exaggerated, but the same thinking can be applied to situations that are much more complicated - modifying the code and data structure used by a 64 bit counter isn't too hard, but completely rewriting your IPC code to use lock-free linked lists is another matter...


Cheers,

Brendan

[Kemp]

Point taken Still we're slightly off-topic here, my original question was related to what things I need to implement for situations that don't require clever thinking and can suffice with something more generic.

A mutex or semaphore (anything that involves a task switch) is just too ugly to think about.

Would you advise against using methods which yield the thread's remaining time? I was considering having this method along with spinlocks with the spinlocks only used for things that are guaranteed (not as in hard real-time guarantees, just from a sensible point of view) to be very short. Of course, my yielding method would be for things that don't mind waiting a bit, like a memory allocation where waiting a timeslice or two for your request to be fulfilled won't hurt anything (yes there are exceptions, I know ). That's just an example anyway as my manager prototype is soon going to have much finer grained (and slightly customised) locking which can probably just be based on spinlocks anyway.

[Brendan]

Hi,

A mutex or semaphore (anything that involves a task switch) is just too ugly to think about.

Would you advise against using methods which yield the thread's remaining time?

In general there's nothing wrong with yielding - there are some performance concerns though:

• - if yielding takes longer than the operation, then it's faster to use a spinlock (and disable or postpone task switches until the lock is freed).
  - because spinlocks normally disable task switches no user-level code should be able to use them (too easy to hog all CPU time by using a never freed lock).
  - interrupt handlers must never need to acquire a "yielding lock". This includes all code that might be used from the context of any interupt handler.

I was considering having this method along with spinlocks with the spinlocks only used for things that are guaranteed (not as in hard real-time guarantees, just from a sensible point of view) to be very short. Of course, my yielding method would be for things that don't mind waiting a bit, like a memory allocation where waiting a timeslice or two for your request to be fulfilled won't hurt anything (yes there are exceptions, I know ). That's just an example anyway as my manager prototype is soon going to have much finer grained (and slightly customised) locking which can probably just be based on spinlocks anyway.

In my experience (for micro-kernels only), if there's anything in the kernel that is slow enough to justify a "yielding lock", then at least part of your kernel needs to be redesigned/improved. This makes things simple - spinlocks for all kernel code and yielding locks for everything else.

The same thinking could be applied to a monolithic kernel, but device drivers would be a "half-way between" thing. You'd still have a "kernel core" with spinlocks only and user-level code with yielding locks only, but device drivers would be able to use either (so that the device driver programmer can decide which suits their situation better).


Cheers,

Brendan

[Kemp]

Once again some very good points (this would be why you're paid the big money ). I was thinking about some things that I thought would need the yielding locks today and I think I may have come up with quicker solutions that can use spinlocks, I'll have to play around a bit as my mind was melting trying to figure out a coherent way of protecting a linked list and allowing it to change while it's being read or changed in other places. I've done a bit of googling on lock-free linked lists and I'm hoping they'll fit what I need.