SMP Compatibility

[Therx]

Although I'm unlikely to implement SMP yet in my kernel, now that I'm writing the Task Manager, Scheduler and switcher. I'd like to do as much as i can so that I don't have to rewrite anything when I come to implement SMP.

I know that even for a single processor PC I will need Spinlocks. How exactly should these be implemented (i've head the xchg instruction mentioned)? and should there be a spinlock on all kernel functions? or only the ones that can be called from threads?

e.g. App -> vmm_alloc() - requires spinlock -> pmm_alloc() - doesn't need spinlock

Is that correct?

Thanks in advance for any help

Pete

[Dreamsmith]

Actually, in a uniprocessor system you don't need spinlocks at all, and you shouldn't be using a spinlock to guard sections from other threads on the same processor. As long as the process in question is active, the spinlock is guarenteed to not be released. Instead of spinning, you should be suspending the task and turning over control to the task that holds the lock. You only want to spin in circumstances where a lock could be released while you're spinning, which generally can only happen in an SMP environment.

OTOH, implementing standard semaphores or mutexes will require spinlocks if they're to work properly in an SMP environment, e.g. app calls acquireSemaphore, kernel disables interrupts, locks a spinlock, does what it needs to do to the semaphore, then releases the spinlock and reenables interrupts. If the semaphore can't be acquired, the task asking for it is put to sleep until some other task calls releaseSemaphore.

Anyhow, implementing a spinlock requires using a LOCK prefix on certain instructions, or instructions that implicitly LOCK. The XCHG instruction is one, so it's a good choice. LOCKing is necessary to keep two processors from modifying it at once. Here's how it can be done under GCC:

typedef unsigned char SpinLock;

INLINE void lockSpinlock(SpinLock *sp)
{
register SpinLock tmp = 1;
do
{
__asm__ __volatile__("xchgb %0,%1"
: "=r"(tmp), "=m"(*sp)
: "0"(tmp), "1"(*sp));
} while ( tmp );
}

INLINE void unlockSpinlock(SpinLock *sp)
{
register SpinLock tmp = 0;
__asm__ __volatile__("xchgb %0,%1"
: "=r"(tmp), "=m"(*sp)
: "0"(tmp), "1"(*sp));
}

Should there be a spinlock on all kernel functions? Probably not. A spinlock should only be used to guard certain sections of sensitive code. You want very specific locks, locking very specific and very small sections of code. If your kernel is preemptable on a uniprocessor, don't use spinlocks, use mutexes or semaphores with the ability to suspend/resume tasks, and only use spinlocks while implementing the semaphores/mutexes.

[Therx]

Surely a spinlock is still required on a function like fork() on a uniprocessor PC, and the various memory allocation functions as if they are interupted a linked list may be left invalid. Or for that do you just have to disable interrupts at the beginning to ensure that a task switch does not occur?

Pete

EDIT: Also how do interrupts work on multiprocessor systems? Do they all go to both CPUs or what? And if interrupts were used for syscalls and a thread running on one CPU triggered a software interrupt but the other CPU handled it then wouldn't the thread which had triggered it keep running without waiting for the interrupt to finish?

If you haven't noticed I don't really get this SMP stuff. I haven't been able to find a good link which explains all this basic stuff. Are there any?

Pete

[Pype.Clicker]

on a single CPU, spinlocks are usually useless or waste too much time. disabling interrupts at 'lock' and re-enabling them at 'unlock' should be enough.

The behaviour of interrupts on multiprocessors system is defined by the IOapic. Usually, you tell the apic which interrupt should go to which processor. In addition, you have *local* APICs on each cpu that can be used to handle inter-processor interrupts and processor-specific timer interrupt.

[Therx]

If I use SYSENTER/EXIT for my syscall interface, would it be wise to disable interrupts on entry and exit? or should I just do that in my Spinlock functions? And if I did syscalls via a software interrupt should it be an Interrupt Gate or a Trap Gate?

Pete

[Candy]

If I use SYSENTER/EXIT for my syscall interface, would it be wise to disable interrupts on entry and exit? or should I just do that in my Spinlock functions? And if I did syscalls via a software interrupt should it be an Interrupt Gate or a Trap Gate?

Pete

What's the point of making those uninterruptible? If you make them reentrant (so they can be entered multiple times, keeping data on stack) you don't have to. The Trap Gate would thus be best suited, the only (afaik) difference from the interrupt gate is that it doesn't disable interrupts automatically (which you thus don't need).

[Therx]

Local variables are stored on the stack aren't they?

Pete

[Dreamsmith]

Surely a spinlock is still required on a function like fork() on a uniprocessor PC, and the various memory allocation functions as if they are interupted a linked list may be left invalid. Or for that do you just have to disable interrupts at the beginning to ensure that a task switch does not occur?

You don't need to disable interrupts, nor necessarily disable preemption if you don't want (although that's the easiest way to do it). You can protect them with a lock, just don't use a SPINlock. Instead, use a semaphore or mutex that will invoke a task switch instead of spinning.

[proxy]

heh, well you will need to disable interrupts in order to implement semaphores and mutexes properly though...so now you are back to sqaure one

proxy

[bkilgore]

For now, I have my spinlock code set up so that if SMP is disabled, a call to lock() simply disables interrupts after saving the flags, and a call to unlock() sets back the old flags. This way I dont have to worry about whether or not interrupts were already disabled when i lock a spinlock.

I just did this recently because I was having a problem with printing to the screen where if I had two threads running, both printing to the screen (say process A printing the alphabet over and over and process B printing dots) then sometimes I would get the . overwriting one of the characters because of the race condition. By adding a spinlock around the code that updates the screen location it now works correctly, always sticking the . between two letters.

So basically, all you really have to do in a uniprocessor system is make sure interrupts are disabled, but a good way (IMHO) to do this is to use spinlocks but have the spinlock code simply handle the disabling of interrupts if your not in an SMP system. This way, if you ever decide to go SMP, you've already taken the extra step to use fine-grain protection in your kernel and you simply have to implement that SMP version of the spinlock.

- Brandon

BTW - I don't know if any of you remember me, I used to be fairly regular around here about a year ago. Unfortunately, with school I didn't have much time to work on my OS, and with work/commute taking 60+ hours a week now I still don't really but I'm trying to get back into it and hope to continue making time when school starts up again. So hopefully you'll be seeing more of me again.

[Therx]

Ok. Thanks every one

I've put together some code which I think will work (a bit based on Dreamsmith's example) but just to check:-

Code: Select all

unsigned char spinlocks[255];

inline void spin_lock(unsigned char id)
{
   register unsigned char temp = 1;   
   
#ifdef SPIN_SMP

   while(temp)
   {
      __asm__ __volatile__("xchgb %0,%1"
                          : "=r"(temp), "=m"(spinlocks[id])
                          :  "0"(temp),  "1"(spinlocks[id]));
   }

#endif

     disable();
}

Will that lock properly? I'm only asking because I know that it could appear to work and then when something breaks later I won''t realise.

Thx

Pete

[Dreamsmith]

heh, well you will need to disable interrupts in order to implement semaphores and mutexes properly though...so now you are back to sqaure one

Um, actually, no, you don't. You do need to disable preemption for short periods while reading or modifying the semaphore or mutex, but you don't need to disable interrupts at all, nor do you need to have preemption disabled while in the section of code protected by the mutex.

[Dreamsmith]

I just did this recently because I was having a problem with printing to the screen where if I had two threads running, both printing to the screen (say process A printing the alphabet over and over and process B printing dots) then sometimes I would get the . overwriting one of the characters because of the race condition. By adding a spinlock around the code that updates the screen location it now works correctly, always sticking the . between two letters.

So basically, all you really have to do in a uniprocessor system is make sure interrupts are disabled,

I would definately recommend against this, if system responsiveness to interrupts is at all an issue for you. You can get the same protection using semaphores or mutexes without having to have interrupts disabled during the entire protected section. So, for example, instead of disabling interrupts while writing to the screen, one should acquire a screen mutex, write to the screen, and release the mutex. Interrupts are only disabled for a few instructions inside the acquireMutex and releaseMutex functions. This gives you the same protection without locking out interrupts for the entire time you're in the protected section.

Really, the ONLY things that ought to be protected by a spinlock are your semaphore and mutex functions. Everything else should be protected by a semaphore or mutex. This dramatically reduces the amount of spinning your system will do -- instead, it just finds another task to execute while one is waiting to enter a critical section.

[Therx]

Ah. But as some of the functions (e.g. mem allocations) can be run from inside an ISR you need to disable ints. Because once in the ISR it will wait for ever for the lock to clear (as the code isn't running). Also the disable/enable pair shouldn't stop task switches for a long time as the spinlock loop is _before_ the disable().

Are you suggesting that I add something so that once it gets into the loop instead of just looping it causes a task switch?

Pete

[Therx]

Just a note to anyone whose taken that code above. You'll have to change the disable / enable pair to something which saves eflags, disable ints, and then instead of enable you restore the eflags. I've just spent a few hours wondering why the spinlock broke the task switching code and it was because it enable ints before everything was set up.

Also. When you have more than one CPU, do they have their own virtual address spaces and just share the physical one or what?

Pete