OSDev.org

The Place to Start for Operating System Developers
It is currently Tue Nov 21, 2017 4:06 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 7 posts ] 
Author Message
 Post subject: Spinlock Macros
PostPosted: Sat Feb 06, 2016 3:06 pm 
Offline

Joined: Sun Jan 17, 2016 7:57 am
Posts: 11
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:
Quote:
Here are example macros in C you can use for spinlocks:
Code:
#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.


Top
 Profile  
 
 Post subject: Re: Spinlock Macros
PostPosted: Sun Feb 07, 2016 1:40 pm 
Offline
Member
Member

Joined: Thu Mar 25, 2010 11:26 pm
Posts: 1801
Location: Melbourne, Australia
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:
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);
}

_________________
If a trainstation is where trains stop, what is a workstation ?


Top
 Profile  
 
 Post subject: Re: Spinlock Macros
PostPosted: Sun Feb 07, 2016 3:30 pm 
Offline

Joined: Sun Jan 17, 2016 7:57 am
Posts: 11
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:
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.


Top
 Profile  
 
 Post subject: Re: Spinlock Macros
PostPosted: Sun Feb 07, 2016 5:11 pm 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 1179
nakst wrote:
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.


Top
 Profile  
 
 Post subject: Re: Spinlock Macros
PostPosted: Sun Feb 07, 2016 8:16 pm 
Offline
Member
Member

Joined: Thu Mar 25, 2010 11:26 pm
Posts: 1801
Location: Melbourne, Australia
nakst wrote:
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:
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.

_________________
If a trainstation is where trains stop, what is a workstation ?


Top
 Profile  
 
 Post subject: Re: Spinlock Macros
PostPosted: Mon Feb 08, 2016 12:33 am 
Offline
Member
Member

Joined: Sun Jun 16, 2013 4:09 am
Posts: 330
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:
   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:
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;
   }
}


Top
 Profile  
 
 Post subject: Re: Spinlock Macros
PostPosted: Mon Feb 08, 2016 12:40 am 
Offline
Member
Member

Joined: Sun Jun 16, 2013 4:09 am
Posts: 330
Code:
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;
   }
}


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group