Spin Lock Implementation

NTFSD
1

Hi all,

Any body explain how spin lock is implemented by OS ?

Thanks in Advance,
Satish K.S

You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

2

>Any body explain how spin lock is implemented by OS

The simplified description:

L1:
MOV EAX, 1
XCHG [spinlock], EAX
OR EAX, EAX
JNE L1

Max

You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

3

Hi ,

But i found different implementation. That i described in other mail topic “RE: Synchronization Problem”

Check it and tell me ur comments on that.

Thanks,
Satish K.S

----- Original Message -----
From: Maxim S. Shatskih
To: File Systems Developers
Sent: Wednesday, March 21, 2001 5:31 PM
Subject: [ntfsd] Re: Spin Lock Implementation

Any body explain how spin lock is implemented by OS

The simplified description:

L1:
MOV EAX, 1
XCHG [spinlock], EAX
OR EAX, EAX
JNE L1

Max

You are currently subscribed to ntfsd as: xxxxx@aalayance.com
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

4

For a very simple view
I think it is based on Dekker’s algorithm.(dekker’s algorithm speaks of only 2 process case)

regards
Jeseem
mailto:xxxxx@hotmail.com
----- Original Message -----
From: Satish
To: File Systems Developers
Sent: Wednesday, March 21, 2001 1:12 PM
Subject: [ntfsd] Spin Lock Implementation

Hi all,

Any body explain how spin lock is implemented by OS ?

Thanks in Advance,
Satish K.S

You are currently subscribed to ntfsd as: xxxxx@hotmail.com
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

5

It shouldn’t be different - the code you posted in the other thread will be
at the start and end of the function.

The psuedo code Maxim posted for the implementation of the ‘spin’ which
would live in between the IRQL stuff.

Rob Linegar
Software Engineer
Data Encryption Systems Limited

-----Original Message-----
From: Satish [mailto:xxxxx@aalayance.com]
Sent: 21 March 2001 12:29
To: File Systems Developers
Subject: [ntfsd] Re: Spin Lock Implementation

Hi ,

But i found different implementation. That i described in other mail topic
“RE: Synchronization Problem”

Check it and tell me ur comments on that.

Thanks,
Satish K.S

----- Original Message -----
From: Maxim S. Shatskih
To: File Systems Developers
Sent: Wednesday, March 21, 2001 5:31 PM
Subject: [ntfsd] Re: Spin Lock Implementation

Any body explain how spin lock is implemented by OS

The simplified description:

L1:
MOV EAX, 1
XCHG [spinlock], EAX
OR EAX, EAX
JNE L1

Max

You are currently subscribed to ntfsd as: xxxxx@aalayance.com
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

You are currently subscribed to ntfsd as: xxxxx@des.co.uk
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

6

The Code which i posted is the only implementation for Spin
ocks( Uniprocessor ). Real implementation come only in MP( According Tony
Mason ). But i dont have MP systems to confirm that :frowning:

Regards,
Satish K.S

----- Original Message -----
From: “Rob Linegar”
To: “File Systems Developers”
Sent: Wednesday, March 21, 2001 9:11 PM
Subject: [ntfsd] Re: Spin Lock Implementation

>
> It shouldn’t be different - the code you posted in the other thread will
be
> at the start and end of the function.
>
> The psuedo code Maxim posted for the implementation of the ‘spin’ which
> would live in between the IRQL stuff.
>
> Rob Linegar
> Software Engineer
> Data Encryption Systems Limited
>
> -----Original Message-----
> From: Satish [mailto:xxxxx@aalayance.com]
> Sent: 21 March 2001 12:29
> To: File Systems Developers
> Subject: [ntfsd] Re: Spin Lock Implementation
>
>
> Hi ,
>
> But i found different implementation. That i described in other mail topic
> “RE: Synchronization Problem”
>
> Check it and tell me ur comments on that.
>
> Thanks,
> Satish K.S
>
>
> ----- Original Message -----
> From: Maxim S. Shatskih
> To: File Systems Developers
> Sent: Wednesday, March 21, 2001 5:31 PM
> Subject: [ntfsd] Re: Spin Lock Implementation
>
>
> >Any body explain how spin lock is implemented by OS
>
> The simplified description:
>
> L1:
> MOV EAX, 1
> XCHG [spinlock], EAX
> OR EAX, EAX
> JNE L1
>
> Max
> —
> You are currently subscribed to ntfsd as: xxxxx@aalayance.com
> To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com
> —
> You are currently subscribed to ntfsd as: xxxxx@des.co.uk
> To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com
>
> —
> You are currently subscribed to ntfsd as: xxxxx@aalayance.com
> To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

—
You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

7

Satish,

You don’t need an MP system to run the MP version of the OS. Try running a
checked build, for instance - it is always built for MP. The UP build is
just faster on a uni-processor than the MP build.

Regards,

Tony Mason
Consulting Partner
OSR Open Systems Resources, Inc.
http://www.osr.com

-----Original Message-----
From: Satish [mailto:xxxxx@aalayance.com]
Sent: Thursday, March 22, 2001 12:06 AM
To: File Systems Developers
Subject: [ntfsd] Re: Spin Lock Implementation

The Code which i posted is the only implementation for Spin
ocks( Uniprocessor ). Real implementation come only in MP( According Tony
Mason ). But i dont have MP systems to confirm that :frowning:

Regards,
Satish K.S

----- Original Message -----
From: “Rob Linegar”
To: “File Systems Developers”
Sent: Wednesday, March 21, 2001 9:11 PM
Subject: [ntfsd] Re: Spin Lock Implementation

>
> It shouldn’t be different - the code you posted in the other thread will
be
> at the start and end of the function.
>
> The psuedo code Maxim posted for the implementation of the ‘spin’ which
> would live in between the IRQL stuff.
>
> Rob Linegar
> Software Engineer
> Data Encryption Systems Limited
>
> -----Original Message-----
> From: Satish [mailto:xxxxx@aalayance.com]
> Sent: 21 March 2001 12:29
> To: File Systems Developers
> Subject: [ntfsd] Re: Spin Lock Implementation
>
>
> Hi ,
>
> But i found different implementation. That i described in other mail topic
> “RE: Synchronization Problem”
>
> Check it and tell me ur comments on that.
>
> Thanks,
> Satish K.S
>
>
> ----- Original Message -----
> From: Maxim S. Shatskih
> To: File Systems Developers
> Sent: Wednesday, March 21, 2001 5:31 PM
> Subject: [ntfsd] Re: Spin Lock Implementation
>
>
> >Any body explain how spin lock is implemented by OS
>
> The simplified description:
>
> L1:
> MOV EAX, 1
> XCHG [spinlock], EAX
> OR EAX, EAX
> JNE L1
>
> Max
> —
> You are currently subscribed to ntfsd as: xxxxx@aalayance.com
> To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com
> —
> You are currently subscribed to ntfsd as: xxxxx@des.co.uk
> To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com
>
> —
> You are currently subscribed to ntfsd as: xxxxx@aalayance.com
> To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

—
You are currently subscribed to ntfsd as: xxxxx@osr.com
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

—
You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

8

>But i found different implementation. That i described in other mail topic
"RE:

Synchronization Problem"

The my XCHG code (based on the atomic operation, the real code in NT uses
LOCK BTS instead of XCHG) - is a real spinlock.
Low-level mutual exclusive lock with busy-waiting semantics.

Now let’s imagine that a thread is holding such a lock, and is preemted by
the dispatcher which yielded control to another thread. What if another
thread will want to acquire the same spinlock? The CPU will hang forever.
To avoid this, there is a requirement of disabling preemption while
holding a spinlock.
NT’s way of disabling preemption is raising to DISPATCH_LEVEL.
So, KeAcquireSpinLock is a combination of:

  1. KeRaiseIrql to DISPATCH_LEVEL (which returns the old IRQL)
  2. the atomic operation thing
    If you’re already at DISPATCH_LEVEL, then no need in step 1, and you can use
    KeAcquireSpinLockFromDpcLevel which is the atomic operation thing only.
    Note that KfAcquireSpinLock and KfRaiseIrql are the HAL exports, while
    KeAcquireSpinLockFromDpcLevel is a kernel export. This is because the atomic
    operation thing is not motherboard-specific, while the IRQL stuff - is (it
    is connected to hardware PIC/APIC management).

On the uniprocessor builds of the kernel, there is no need in atomic
operation at all (no more CPUs) - just disabling preemption is enough to
declare it “a spin lock”. So, the code in the UP build is:
KeAcquireSpinLock is KeRaiseIrql
KeAcquireSpinLockFromDpcLevel is a no-op.

Hope this helps,

Max

You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

9

Tony Mason.

Thanks i got it .

Regards,
Satish K.S

----- Original Message -----
From: “Tony Mason”
To: “File Systems Developers”
Sent: Thursday, March 22, 2001 6:24 PM
Subject: [ntfsd] Re: Spin Lock Implementation

> Satish,
>
> You don’t need an MP system to run the MP version of the OS. Try running
a
> checked build, for instance - it is always built for MP. The UP build is
> just faster on a uni-processor than the MP build.
>
> Regards,
>
> Tony Mason
> Consulting Partner
> OSR Open Systems Resources, Inc.
> http://www.osr.com
>
> -----Original Message-----
> From: Satish [mailto:xxxxx@aalayance.com]
> Sent: Thursday, March 22, 2001 12:06 AM
> To: File Systems Developers
> Subject: [ntfsd] Re: Spin Lock Implementation
>
>
>
> The Code which i posted is the only implementation for Spin
> ocks( Uniprocessor ). Real implementation come only in MP( According Tony
> Mason ). But i dont have MP systems to confirm that :frowning:
>
> Regards,
> Satish K.S
>
>
> ----- Original Message -----
> From: “Rob Linegar”
> To: “File Systems Developers”
> Sent: Wednesday, March 21, 2001 9:11 PM
> Subject: [ntfsd] Re: Spin Lock Implementation
>
>
> >
> > It shouldn’t be different - the code you posted in the other thread will
> be
> > at the start and end of the function.
> >
> > The psuedo code Maxim posted for the implementation of the ‘spin’ which
> > would live in between the IRQL stuff.
> >
> > Rob Linegar
> > Software Engineer
> > Data Encryption Systems Limited
> >
> > -----Original Message-----
> > From: Satish [mailto:xxxxx@aalayance.com]
> > Sent: 21 March 2001 12:29
> > To: File Systems Developers
> > Subject: [ntfsd] Re: Spin Lock Implementation
> >
> >
> > Hi ,
> >
> > But i found different implementation. That i described in other mail
topic
> > “RE: Synchronization Problem”
> >
> > Check it and tell me ur comments on that.
> >
> > Thanks,
> > Satish K.S
> >
> >
> > ----- Original Message -----
> > From: Maxim S. Shatskih
> > To: File Systems Developers
> > Sent: Wednesday, March 21, 2001 5:31 PM
> > Subject: [ntfsd] Re: Spin Lock Implementation
> >
> >
> > >Any body explain how spin lock is implemented by OS
> >
> > The simplified description:
> >
> > L1:
> > MOV EAX, 1
> > XCHG [spinlock], EAX
> > OR EAX, EAX
> > JNE L1
> >
> > Max
> > —
> > You are currently subscribed to ntfsd as: xxxxx@aalayance.com
> > To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com
> > —
> > You are currently subscribed to ntfsd as: xxxxx@des.co.uk
> > To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com
> >
> > —
> > You are currently subscribed to ntfsd as: xxxxx@aalayance.com
> > To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com
>
>
> —
> You are currently subscribed to ntfsd as: xxxxx@osr.com
> To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com
>
> —
> You are currently subscribed to ntfsd as: xxxxx@aalayance.com
> To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

—
You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

10

----- Original Message -----
From: “Maxim S. Shatskih”
To: “File Systems Developers”
Sent: Thursday, March 22, 2001 5:39 PM
Subject: [ntfsd] Re: Spin Lock Implementation

> >But i found different implementation. That i described in other mail topic
> “RE:
> >Synchronization Problem”
>
> The my XCHG code (based on the atomic operation, the real code in NT uses
> LOCK BTS instead of XCHG) - is a real spinlock.
> Low-level mutual exclusive lock with busy-waiting semantics.
>
> Now let’s imagine that a thread is holding such a lock, and is preemted by
> the dispatcher which yielded control to another thread. What if another
> thread will want to acquire the same spinlock? The CPU will hang forever.
> To avoid this, there is a requirement of disabling preemption while
> holding a spinlock.
> NT’s way of disabling preemption is raising to DISPATCH_LEVEL.
> So, KeAcquireSpinLock is a combination of:
> 1) KeRaiseIrql to DISPATCH_LEVEL (which returns the old IRQL)
> 2) the atomic operation thing
> If you’re already at DISPATCH_LEVEL, then no need in step 1, and you can use
> KeAcquireSpinLockFromDpcLevel which is the atomic operation thing only.
> Note that KfAcquireSpinLock and KfRaiseIrql are the HAL exports, while
> KeAcquireSpinLockFromDpcLevel is a kernel export. This is because the atomic
> operation thing is not motherboard-specific, while the IRQL stuff - is (it
> is connected to hardware PIC/APIC management).
>
> On the uniprocessor builds of the kernel, there is no need in atomic
> operation at all (no more CPUs) - just disabling preemption is enough to
> declare it “a spin lock”. So, the code in the UP build is:
> KeAcquireSpinLock is KeRaiseIrql
> KeAcquireSpinLockFromDpcLevel is a no-op.
>
> Hope this helps,
>
> Max
>

Thanks, It really Helps. :slight_smile:

Here i got some other info ( I tested in Debug version of Win2000 - This will have MP DLLs ):
1) Driver will never invoke KeAcquireSpinLock. It will invoke always KfAcquireSpinLock exported from HAL.DLL.
2) if u call KeAcquireSpinLock at DISPATCH_LEVEL u will end up in BSOD( In MSDN Documentation u can see “Callers of KeAcquireSpinLock must be running at IRQL <= DISPATCH_LEVEL:”).

Bug Check is = KeBugCheck ( 0x09, 0xSomeThing, 0x02, 0x00, 0x04 )

Hope this helps,

Regards,
Satish K.S

—
You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

11

>Here i got some other info ( I tested in Debug version of Win2000 - This
will

have MP DLLs ):

  1. Driver will never invoke KeAcquireSpinLock. It will invoke always
    KfAcquireSpinLock exported from HAL.DLL.

KeAcquireSpinLock is defined to be KfAcquireSpinLock in NTDDK.H
Kfxxx is faster due to using no stack frame.

Max

You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com