Using IF as mutex

[Combuster]

I just came up with an idea for locking operations, and i'd like to know if i missed some details or fail sanity checks

The main idea was to minimize cpu idle time during critical sections when another thread has a lock - (busy waits, especially, some code must work under the assumption there is no scheduler so one can't yield() instead)

Basically, i intend to use CLI/STI (disable interrupt) pairs as the primary locking mechanism, so i can do critical code without the scheduler interfering.
I'll make these basic assumptions:
- critical code has a finite execution time
- all threads will get a fair share of cpu time

By my knowledge it has the mutual exclusion property: if IF is cleared there will not be any threads running critical code

no starvation: a thread will always be able to enter the critical section - basically because when the thread is scheduled IF must be set and the critical section can be entered

and progression: the code will always enter the critical section if available (there's no check anyway), and it will always leave it.

The most interesting question to ask here, how much manipulation can and should i put in those blocks while keeping interrupt latency neglegible?

Second question, on MP systems i'll probably have to busy wait as to assure synchronisation between processors, but on the other hand, you KNOW the other end is currently executing critical code and that it must exit soon, so the delay is at most the time to execute the critical section times no. of processors - 1, what do you think?

Fire away your comments, remarks and ideas. All creative thinking welcome (or just a nod of approval so i know i'm not building an inherently flawed kernel )

[paulbarker]

On a 1-CPU system, you need to deal with 2 conditions:

1) A thread begins to modify data, and is interrupted while the data is in an inconsistant state. The interrupt handler accesses the same data and either overwrites the modifications being made or takes the wrong action due to the inconsistant state. To correct this, disable interrupts whose handlers access the same data as you are working on. Stopping all interrupts may or may not be a good idea, depending on the system.

2) A thread is modifying data, a timer interrupt comes along and the scheduler runs, all without accessing the data the thread was working on. Another thread is chosen to run, which does access the data the original thread was working on. To stop this happening, you should use a mutex/semaphore/whatever.

Disabling interrupts for (2) will lead to starvation of devices like the timer which need a response to a very high proportion of their interrupts in order to keep a good software clock running. There are other issues, eg. A low priority thread/process should be interrupted by a higher priority one, and the low priority thread holds a mutex which the high priority thread does NOT need. Preventing the high priority thread from running in this case is unnecessary.

The conclusion is, use the right tool for the job.

The system you describe is good for low-level stuff (eg. modifying interrupt tables) but is no good for high level stuff (eg. device access or process creation).

[Candy]

I intend to use cli/sti to signal to the kernel that the user code is in a critical section. These should be nestable, so you can indicate a 3rd level critical section bit. They don't actually clear the IF bit. Then, when an interrupt occurs, the task's quantum is decreased by 1. If it's now 0, it would normally be swapped out, but it has (by having >0 critical section enters) a grace bit set. This is a small bit from the next timeslice that it can also use, but only for finishing a critical section. It's then given the processor for another millisecond (or such) and can finish the critical section. The next time it's given quanta, it's given one less, for using the grace quantum.

In the kernel, I use pretty much the same, except that I use pushfd;cli and popfd (with storing their state in the mutex lock object) instead of cli/sti because they also allow nesting while actually clearing the IF.

[Brendan]

Hi,

Second question, on MP systems i'll probably have to busy wait as to assure synchronisation between processors, but on the other hand, you KNOW the other end is currently executing critical code and that it must exit soon, so the delay is at most the time to execute the critical section times no. of processors - 1, what do you think?

Fire away your comments, remarks and ideas. All creative thinking welcome (or just a nod of approval so i know i'm not building an inherently flawed kernel )

From my point of view it should work fine, but I'd suggest using some macros rather than using "CLI" and "STI" directly - that way if you wanted an SMP version you could rewrite the macros to make it easier. I'd also suggest giving the macros a single parameter - the address of a location to store a variable/lock.

For example:

Code: Select all

%macro LOCK_SECTION 1
  %ifdef MULTI_CPU
    %%wait:
      bts %1,0
      jc %%wait
  %else
      pushfd
      cli
   %endif
%endmacro

%macro UNLOCK_SECTION 1
  %ifdef MULTI_CPU
      btc %1,0
  %else
      popfd
   %endif
%endmacro


    LOCK_SECTION [ebx*4+Something]
    ....
    UNLOCK_SECTION [ebx*4+Something]

Of course, this is over-simplified (the SMP spinlock isn't efficient) and would suck if you're using C (messing up the stack like that)...

Also, Candy is completely correct. Any critical section that takes too long will mess up interrupt latency and/or waste too much CPU time. My own "general rule" is that if the critical section takes longer than a thread switch, then it should use a mutex or semaphore (or be rewritten/redesigned so it's faster)....


Cheers,

Brendan

[Combuster]

@paulbarker
CLI is meant to temporarily inhibit the scheduler. if the timer expires during a critical section the INT line will be held high for as long as it is not serviced, so the interrupt will occur directly after the critical section when STI is issued.

Besides, i am talking kernel code, and the things i want to do within IF locks are things like test and adjust pagetable entries, allocating page/4m memory, allocating bits for ioplbitmap, scheduling and descheduling of threads, that sort. Device accesses occur in userspace and cannot benefit from this situation.

@Candy
cli/sti for userspace sounds like a good idea but would require me to alter the default scheduler and have VME present and enabled. Good idea for a plugin scheduler though.
I bit of doubt that on systems without VME the hit caused by GPF on altering IF (or via syscalls) is worth the time compared to that spent in critical sections or am i wrong at that?

and thanks for the push/pop idea, i think i'll take it

@Brendan
Probably the most expensive operation i can think of that would entirely execute in a critical section is allocating a 4MB entry on systems that dont support PSE (thus an entire 4k pagetable must be written in one run) - if you or someone else knows the timings for that it'd probably help if i got to keep my current semaphore code or not.

By the look of it, your macro goes to use spinlocks on MP systems instead of using them as an addition to IF locking - was that supposed to be intentional?

as for MP systems, does it help restoring IF if the other cpu seems busy so it can be scheduled if the timeslice should run out?
As for C, the ring 0 kernel part is 100% assembler, the ring 3 parts are mixed ASM, C and Basic, but apart from candy's suggestion i dont think they'll qualify for IF locking anyway.

Thanks for the feedback everyone, I think i'll go implement some stuff on my next coding spree

[Candy]

Of course, this is over-simplified (the SMP spinlock isn't efficient) and would suck if you're using C (messing up the stack like that)...

Also, Candy is completely correct. Any critical section that takes too long will mess up interrupt latency and/or waste too much CPU time. My own "general rule" is that if the critical section takes longer than a thread switch, then it should use a mutex or semaphore (or be rewritten/redesigned so it's faster)....

If you have something that is entirely critical and that can't be interrupted, make a critical section (CLI). If you have something that needs mutual exclusion, use a mutex. Critical stuff is truly critical, IE, reading a hardware device that's out of buffers, starting a pacemaker etc.

@Candy
cli/sti for userspace sounds like a good idea but would require me to alter the default scheduler and have VME present and enabled. Good idea for a plugin scheduler though.
I bit of doubt that on systems without VME the hit caused by GPF on altering IF (or via syscalls) is worth the time compared to that spent in critical sections or am i wrong at that?

and thanks for the push/pop idea, i think i'll take it

I was hoping that the penalty for an exception would be limited to two pipeline flushes (20-30 cycles on most processors) and that the full store/reload could be saved until it's certain that the "invalid op" wasn't a cli/sti. That gives you some 50 cycle latency per sti / cli, which should be good enough.

You could just make it lock inc [thread_local_mutex_count] which would be faster accomplishing the same. The 1-quanta skipahead is to prevent the feature from being abused.

Somehow it'd be nice if the thread gave up its timeslice when its mutex count fell back to 0. You could/should add something to it that the kernel can indicate when the thread is in the grace period.

[paulbarker]

What happens if you get 3-4 clock ticks during a period where IF=0?

[Combuster]

if you mean PIT: you'll lose all ticks after the first

[paulbarker]

Yep, I did mean PIT. Or any device which will cause problems if you miss an interrupt.

As long as you remember to avoid keeping IF=0 for a long time you should be fine. Take care though, a "short operation" on a modern CPU could easily take several clock ticks on an old CPU. If memory allocation is an O(n) algorithm, disabling IF for the whole run is a Bad Idea (TM). Stick to simple, O(1) algorithms when IF=0.

For example, in my kernel I will say that allocations in an irq handler or while IF=0 may only be for 1 page (not asking for several pages at once, contiguous or not). With the memory manager I will use, this will guarentee an O(1) operation (just take the first item from a list) rather than O(n) (search the list for an element of at least the desired size).

For anything more complex than this, use a simple lock or preempt-disable flag (which would disable preemption without disabling interrupt handlers).

May I also add, pretty much as an echo of other people, do whatever you like but call the operation _lock() or spin_lock() or whatever rather than just calling cli() directly, then you can change the implementation to support multi-CPU systems without re-writing all the code. Retro-fitting spinlocks or the like is almost as hard as retro-fitting security.

[Candy]

My personal guideline is to only use IF=0 for either short operations that cannot page fault or longer operations that must not be interrupted (rep insw f.ex.) up to a certain limit. You don't call functions at all in those blocks, you don't loop unless it's a tight inner loop that must be in there. If there's anything you can move before the cli or after the sti, do so.

Since you can't call anything, there's no nesting problem either .

[Brendan]

Hi,

By the look of it, your macro goes to use spinlocks on MP systems instead of using them as an addition to IF locking - was that supposed to be intentional?

Mostly habit I guess...

On an MP system, disabling IRQs on one CPU won't prevent another CPU from accepting interrupts. Therefore you need some other mechanism to prevent IRQ handlers from being called by other CPUs in MP systems (if this causes re-entrancy problems).

Whether or not IF locking is needed depends on how this other mechanism is designed. For my previous system IF wasn't necessary, and some IRQs were capable of interrupting critical sections (IIRC, the system timer tick IRQ and the "TLB shootdown" IPI).


Cheers,

Brendan

[Candy]

You can use the VIF flag for this tracking, but it's a bit awkward. Everything works normally, but popfd is implicitly followed by a cli. You can't therefore count on it being a 0 whenever somebody's in a mutex-ish section, because a simple popfd would implicitly clear it. You can use it the other way around though.

Before entering a mutex, raise a global variable that indicates how many mutexes are active. If this value was 0, use sti before actually entering the mutex. When it's 0 after decreasing it in the exit code, use a cli.

When you notice a thread is in the grace period after handling an interrupt, set the VIP bit. Whenever the software uses another sti (so it's entering another series of critical section), the processor checks whether the VIP bit is set, and if it is it gives a GPF. In your GPF handling code, check whether the VIP bit caused a GPF combined with an STI. If so, swap out the process with the VIP bit cleared and EIP still pointing at the STI instruction and give it -1 quanta.

If I'm right, this should make it quite possible for your programs to use critical sections and to reduce latency & swapping of programs that are in a critical section or that use critical sections in the form of fairly quick mutexed sections.


You can also use the interrupt flag the normal way around, which would give a GPF on leaving the critical section (still with mutex counting or one-mutex soft limit, that is), but that would merge the popfd-oops-state into the critical-section-active-state instead of the not-critical-state. That would in turn mean that if somebody did an popfd at any time he'd be stuck in an implicit critical section including the punishments for overrunning them and that the entire idea would be worth **** until the next exit from a critical section. The other way, however it's less clear, does allow for popfd use. I'm going for the first.