Spinlock Macros

[nakst]

Hi, I've added C macros to the Spinlock page on the wiki: http://wiki.osdev.org/Spinlock#C_Macros.
I was wondering if someone more experienced than me in threading issues could check them for any problems. Thanks!

Here is the code I added:

Here are example macros in C you can use for spinlocks:

Code: Select all

#define DECLARE_LOCK(name) volatile int name ## Locked
#define LOCK(name) \
	while (!__sync_bool_compare_and_swap(& name ## Locked, 0, 1)); \
	__sync_synchronize();
#define UNLOCK(name) \
	__sync_synchronize(); \
	name ## Locked = 0;

Call DECLARE_LOCK(name) to create a lock definition, LOCK(name) to acquire the lock, and UNLOCK(name) to release it. The LOCK macro will spin until the lock is released before continuing. This code makes use of intrisics specific to GCC, but it also compiles on Clang.

[gerryg400]

Hi, I have some comments from my understanding. I hope if I have something wrong we get further comments...

• I don't think the __sync_synchronize() call is necessary when locking because the __sync_bool_compare_and_swap() call acts as an acquire memory barrier and is sufficient.
• Some sort of 'pause' is good on x86. 8.10.6.1 of Intel 3A recommends this.
• There's no need for __sync_synchronize() when unlocking. A simple mov should be sufficient for a releasing spinlock on x86 however you can use __sync_lock_release() for portability.

My spin lock looks like this

Code: Select all

typedef uint32_t spinlock_t;

static void inline spin_lock(spinlock_t volatile *plock)
{
    while (!__sync_bool_compare_and_swap(plock, 0, 1))
    {
        while (*plock)
        {
            __pause();
        }
    }
}

static void inline spin_unlock(spinlock_t volatile *plock)
{
    __sync_lock_release(plock);
}

[nakst]

Okay, but I'm not sure we want a pause intrinsic. On X86 PAUSE is part of SSE2 which is not enabled by default and for this reason the 64-bit kernel tutorial has the -mno-sse2 compiler flag recommended. It's also not portable between architectures. It's only real advantage is in hyper threading, but I think example code on the Wiki should be as applicable in all situations rather than the best for one possible instance. Maybe it could be included as an alternative.

Here's the new proposed code:

Code: Select all

typedef volatile int Spinlock;
#define LOCK(name) \
	while (!__sync_bool_compare_and_swap(&name, 0, 1));
#define UNLOCK(name) \
	__sync_lock_release(&name);

Thanks for the tips.

[Octocontrabass]

Okay, but I'm not sure we want a pause intrinsic. On X86 PAUSE is part of SSE2 which is not enabled by default

PAUSE is a backwards-compatible extension of NOP. If PAUSE isn't supported, it behaves the same as NOP.

You want a pause intrinsic.

[gerryg400]

Okay, but I'm not sure we want a pause intrinsic. On X86 PAUSE is part of SSE2 which is not enabled by default and for this reason the 64-bit kernel tutorial has the -mno-sse2 compiler flag recommended. It's also not portable between architectures. It's only real advantage is in hyper threading, but I think example code on the Wiki should be as applicable in all situations rather than the best for one possible instance. Maybe it could be included as an alternative.

Here's the new proposed code:

Code: Select all

typedef volatile int Spinlock;
#define LOCK(name) \
	while (!__sync_bool_compare_and_swap(&name, 0, 1));
#define UNLOCK(name) \
	__sync_lock_release(&name);

Thanks for the tips.

Hi. Even if you don't use the pause instruction (and you should), it's significantly better for cache performance if you us a non-locking test while spinning and only using the lock prefix when there is a possibility of success.

[tsdnz]

I use a slightly different approach for my SpinLocks.

I want the locks to be ordered, only a single "Bus Lock" instruction, the ability to request a lock and check if the lock has been acquired, and to find out the Number of Waiting Locks.

The "TryLock" makes it possible to attempt the lock many times within a routine while continuing with code until a lock has been acquired.
I use it and check the result against [n], and if less then I Spin waiting, otherwise I continue with some other code.
This depends on the "other code", which is usually very small in cycles and all cycles counted to calculate n.

Edit: New code in the next thread. I do not need to add 2 to the Tickets any more.

Here is the code:

Code: Select all

	class Packed() tSpinlock
	{
	private:
		volatile QWORD AlignTo(8) LockTicket;
		volatile QWORD AlignTo(8) LockUserTicket;

	public:
		FIL void Init();

		FIL void Lock();
		FIL QWORD NumberOfWaitingLocksRequested();
		FIL QWORD TryLock(QWORD& LockTicketToWaitFor);
		FIL void Unlock();
	};

Code: Select all

namespace /*Spinlock*/ Kernel
{
	FIL void tSpinlock::Init()
	{
		LockTicket = 0;
		LockUserTicket = 0;
	}

	FIL QWORD tSpinlock::NumberOfWaitingLocksRequested() // Not guaranteed to return the correct answer, just used as a hint
	{
		return (LockTicket - LockUserTicket) / 2;
	}

	FIL QWORD tSpinlock::TryLock(QWORD& LockTicketToWaitFor) // Pass through 1 for the first lock
	{
		if (LockTicketToWaitFor == 1)
			LockTicketToWaitFor = __sync_fetch_and_add(&LockTicket, 2);

		return (LockTicketToWaitFor - LockUserTicket) / 2; // Return the number of locks before this one, 0 = Lock Acquired
	}

	FIL void tSpinlock::Lock()
	{
		QWORD LockTicketToWaitFor = __sync_fetch_and_add(&LockTicket, 2);

		while (LockTicketToWaitFor != LockUserTicket)
		{
			// Util.Pause(); // On my servers it runs faster without Pause
		}
	}

	FIL void tSpinlock::Unlock()
	{
		LockUserTicket += 2;
	}
}

[tsdnz]

Code: Select all

namespace /*Spinlock*/ Kernel
{
	FIL void tSpinlock::Init()
	{
		LockTicket = 2;
		LockUserTicket = 2;
	}

	FIL QWORD tSpinlock::NumberOfWaitingLocksRequested() // Not guaranteed to return the correct answer, just used as a hint
	{
		return LockTicket - LockUserTicket;
	}

	FIL QWORD tSpinlock::TryLock(QWORD& LockTicketToWaitFor) // Pass through 1 for the first lock
	{
		if (LockTicketToWaitFor == 1)
			LockTicketToWaitFor = __sync_fetch_and_add(&LockTicket, 1);

		return LockTicketToWaitFor - LockUserTicket; // Return the number of locks before this one, 0 = Lock Acquired
	}

	FIL void tSpinlock::Lock()
	{
		QWORD LockTicketToWaitFor = __sync_fetch_and_add(&LockTicket, 1);

		while (LockTicketToWaitFor != LockUserTicket)
		{
			// Util.Pause(); // On my servers it runs faster without Pause
		}
	}

	FIL void tSpinlock::Unlock()
	{
		LockUserTicket += 1;
	}
}