Are callbacks guaranteed to run consecutively?

Preemption is allowed, but not suspension :slight_smile:

What really is the motive for coming up with such a synch* primitive? Why
not mutex? Why not event? Why not semaphore with count == 1 ?

The motive is not to trap the HW in an useless state. If preemption is not
allowed, how would the system maintain other higher priority problem(s) and
tasks ( clocks, instruction OP code problems, and other stuff ).

The context switching is one of the culprit ( heavy over head ) of those
suspendable synch primitive. A suspendable synch primitive is one where the
acquiring thread could be suspended, and rescheduled, and again suspended

It is definitely this suspension, that motivated spinlock. Now if they are
also not preemptible then there is a real problem though.

It is altogether a different story, if someone tries to optimize the bus
traffic by not polling the flag/lock too often, but that is still spinning
and not suspending or going to wait state where scheduler/dispatcher -
intervention is needed to bring the said thread into execution.

-pro

On Dec 27, 2007 2:26 PM, Alberto Moreira wrote:

> A spinlock is supposed to stall a processor. It’s a strong tool to be
> used as an arbiter of last resort. It works like this:
>
> top: atomic_test_and_set location,true
> jump_if_old_value_is_true top
>
> Or, in C-like prose,
>
> do
> {
> old_value = atomic_test_and_set (flag,true);
> }
> while (old_value);
>
> To clear a spinlock is even simpler:
>
> flag = false;
>
> There’s no yielding of any sort here. Spinlocks don’t block, don’t yield,
> and they’re also not aware of processes, threads, or whatever. It may be the
> case that an interrupt causes a context switch, but once control comes back,
> the loop carries on. And I’m definitely not sold on the wisdom of allowing
> certain kinds of interrupts and locks to be preempted.
>
> You can dress up a spinlock with all sorts of extra baggage, but the more
> you add, the less it looks like a spinlock!
>
>
> Alberto.
>
>
>
>
> ----- Original Message -----
>
> From: Mark Roddy
> To: Windows System Software Devs Interest List
> Sent: Wednesday, December 26, 2007 10:57 AM
> Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?
>
>
>
> On Dec 26, 2007 9:22 AM, Alberto Moreira wrote:
>
> > I’m sorry, people, I’m going to put on my computer science hat now and
> > say that whatever this is, it ain’t a spinlock. The whole point of a
> > spinlock is to spin without yielding execution!
> >
>
> At least provide an accurate definition. " The whole point of a spinlock
> is to spin without yielding execution! " No that isn’t the whole point.
> That is a distinct feature. And everything we have discussed here, with the
> exception of the AIX style ‘spin a while, then sleep’ implementation,
> doesn’t ‘yield execution’. What we have discussed is that on NT, and most
> other modern multiprocessor general purpose operating systems, spinlocks are
> interruptible. The currently executing thread does not yield execution, it
> is interrupted, runs some isr, and then returns to spinning.
> Implementations of spinlocks could block all interrupts and never allow the
> processor to do anything other than busy wait for the lock. Such
> implementations are generally considered deficient as they block management
> of timers and TLBs and other critical global OS resources while not
> providing any added benefit. You are of course free to implement this sort
> of deficient simplistic private spinlock, but I would suggest not deploying
> this spinlock of yours on general purpose multiprocessor systems.
>
>
>
> >
> >
> >
> > –
> > Mark Roddy
> >
> — NTDEV is sponsored by OSR For our schedule of WDF, WDM, debugging and
> other seminars visit: http://www.osr.com/seminars To unsubscribe, visit
> the List Server section of OSR Online at
> http://www.osronline.com/page.cfm?name=ListServer
>
>
> —
> NTDEV is sponsored by OSR
>
> For our schedule of WDF, WDM, debugging and other seminars visit:
> http://www.osr.com/seminars
>
> To unsubscribe, visit the List Server section of OSR Online at
> http://www.osronline.com/page.cfm?name=ListServer
>

Preemption is allowed, but not suspension :slight_smile:

What really is the motive for coming up with such a synch* primitive? Why
not mutex? Why not event? Why not semaphore with count == 1 ?

The motive is not to trap the HW in an useless state. If preemption is not
allowed, how would the system maintain other higher priority problem(s)
and tasks ( clocks, instruction OP code problems, and other stuff ).

The context switching is one of the culprit ( heavy over head ) of those
suspendable synch primitive. A suspendable synch primitive is one where
the acquiring thread could be suspended, and rescheduled, and again
suspended …

It is definitely this suspension, that motivated spinlock. Now if they
are also not preemptible then there is a real problem though.

It is altogether a different story, if someone tries to optimize the bus
traffic by not polling the flag/lock too often, but that is still spinning
and not suspending or going to wait state where scheduler/dispatcher -
intervention is needed to bring the said thread into execution.

-pro

A spinlock is supposed to stall a processor. It’s a strong tool to be used
as an arbiter of last resort. It works like this:

top: atomic_test_and_set location,true
jump_if_old_value_is_true top

Or, in C-like prose,

do
{
old_value = atomic_test_and_set (flag,true);
}
while (old_value);

To clear a spinlock is even simpler:

flag = false;

There’s no yielding of any sort here. Spinlocks don’t block, don’t yield,
and they’re also not aware of processes, threads, or whatever. It may be
the case that an interrupt causes a context switch, but once control comes
back, the loop carries on. And I’m definitely not sold on the wisdom of
allowing certain kinds of interrupts and locks to be preempted.

You can dress up a spinlock with all sorts of extra baggage, but the more
you add, the less it looks like a spinlock!

Alberto.

----- Original Message -----
From: Mark Roddy
To: Windows System Software Devs Interest List
Sent: Wednesday, December 26, 2007 10:57 AM
Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?

On Dec 26, 2007 9:22 AM, Alberto Moreira wrote:
>
> I’m sorry, people, I’m going to put on my computer science hat now and
> say that whatever this is, it ain’t a spinlock. The whole point of a
> spinlock is to spin without yielding execution!
>
> At least provide an accurate definition. " The whole point of a spinlock
> is to spin without yielding execution! " No that isn’t the whole
> point. That is a distinct feature. And everything we have discussed
> here, with the exception of the AIX style ‘spin a while, then sleep’
> implementation, doesn’t ‘yield execution’. What we have discussed is
> that on NT, and most other modern multiprocessor general purpose
> operating systems, spinlocks are interruptible. The currently executing
> thread does not yield execution, it is interrupted, runs some isr, and
> then returns to spinning. Implementations of spinlocks could block all
> interrupts and never allow the processor to do anything other than busy
> wait for the lock. Such implementations are generally considered
> deficient as they block management of timers and TLBs and other critical
> global OS resources while not providing any added benefit. You are of
> course free to implement this sort of deficient simplistic private
> spinlock, but I would suggest not deploying this spinlock of yours on
> general purpose multiprocessor systems.
>
>
>
>
>
> –
> Mark Roddy
> — NTDEV is sponsored by OSR For our schedule of WDF, WDM, debugging
> and other seminars visit: http://www.osr.com/seminars To unsubscribe,
> visit the List Server section of OSR Online at
> http://www.osronline.com/page.cfm?name=ListServer
> —
> NTDEV is sponsored by OSR
>
> For our schedule of WDF, WDM, debugging and other seminars visit:
> http://www.osr.com/seminars
>
> To unsubscribe, visit the List Server section of OSR Online at
> http://www.osronline.com/page.cfm?name=ListServer

Mark Roddy wrote:

Well I sure hope you aren’t going to deploy that implentation.

You cannot consistently claim that spinlocks are ‘supposed to stall a
processor’ and that ‘It may be the case that an interrupt causes a
context switch’. If they are interruptable, they are not stalling a
processor. Spinlocks are busy wait locks. If one can implement an
interruptible spinlock, one can also implement a pre-emptable
spinlock. In at least one commercially deployed OS I know of (AIX)
there was in fact a ‘spin a while, then sleep’ spinlock that
explicitly executed a yield. That OS seemed to work just fine. Non
preemption is an implementation detail and not a mandatory quality of
spinlocks.

Yes. Some of us are arguing about the implied connotations of the
phrase “spinlock”, and some of us are arguing about a specific kernel
synchronization implementation in one or more actual operating systems.
Just because they have the same name does not mean they are the same
concept.

This argument is not useful.


Tim Roberts, xxxxx@probo.com
Providenza & Boekelheide, Inc.

FWIW, this is one link that would lead to other links too.

http://www.cs.washington.edu/homes/tom/pubs/spinlock.pdf

-pro

----- Original Message -----
From:
To: “Windows System Software Devs Interest List”
Sent: Thursday, December 27, 2007 3:27 PM
Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?

> Preemption is allowed, but not suspension :slight_smile:
>
> What really is the motive for coming up with such a synch* primitive? Why
> not mutex? Why not event? Why not semaphore with count == 1 ?
>
> The motive is not to trap the HW in an useless state. If preemption is not
> allowed, how would the system maintain other higher priority problem(s)
> and tasks ( clocks, instruction OP code problems, and other stuff ).
>
> The context switching is one of the culprit ( heavy over head ) of those
> suspendable synch primitive. A suspendable synch primitive is one where
> the acquiring thread could be suspended, and rescheduled, and again
> suspended …
>
> It is definitely this suspension, that motivated spinlock. Now if they
> are also not preemptible then there is a real problem though.
>
> It is altogether a different story, if someone tries to optimize the bus
> traffic by not polling the flag/lock too often, but that is still spinning
> and not suspending or going to wait state where scheduler/dispatcher -
> intervention is needed to bring the said thread into execution.
>
> -pro
>> A spinlock is supposed to stall a processor. It’s a strong tool to be
>> used
>> as an arbiter of last resort. It works like this:
>>
>> top: atomic_test_and_set location,true
>> jump_if_old_value_is_true top
>>
>> Or, in C-like prose,
>>
>> do
>> {
>> old_value = atomic_test_and_set (flag,true);
>> }
>> while (old_value);
>>
>> To clear a spinlock is even simpler:
>>
>> flag = false;
>>
>> There’s no yielding of any sort here. Spinlocks don’t block, don’t yield,
>> and they’re also not aware of processes, threads, or whatever. It may be
>> the case that an interrupt causes a context switch, but once control
>> comes
>> back, the loop carries on. And I’m definitely not sold on the wisdom of
>> allowing certain kinds of interrupts and locks to be preempted.
>>
>> You can dress up a spinlock with all sorts of extra baggage, but the more
>> you add, the less it looks like a spinlock!
>>
>>
>> Alberto.
>>
>>
>>
>>
>> ----- Original Message -----
>> From: Mark Roddy
>> To: Windows System Software Devs Interest List
>> Sent: Wednesday, December 26, 2007 10:57 AM
>> Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?
>>
>>
>>
>>
>>
>> On Dec 26, 2007 9:22 AM, Alberto Moreira wrote:
>>
>> I’m sorry, people, I’m going to put on my computer science hat now
>> and
>> say that whatever this is, it ain’t a spinlock. The whole point of a
>> spinlock is to spin without yielding execution!
>>
>> At least provide an accurate definition. " The whole point of a
>> spinlock
>> is to spin without yielding execution! " No that isn’t the whole
>> point. That is a distinct feature. And everything we have discussed
>> here, with the exception of the AIX style ‘spin a while, then sleep’
>> implementation, doesn’t ‘yield execution’. What we have discussed is
>> that on NT, and most other modern multiprocessor general purpose
>> operating systems, spinlocks are interruptible. The currently executing
>> thread does not yield execution, it is interrupted, runs some isr, and
>> then returns to spinning. Implementations of spinlocks could block all
>> interrupts and never allow the processor to do anything other than busy
>> wait for the lock. Such implementations are generally considered
>> deficient as they block management of timers and TLBs and other critical
>> global OS resources while not providing any added benefit. You are of
>> course free to implement this sort of deficient simplistic private
>> spinlock, but I would suggest not deploying this spinlock of yours on
>> general purpose multiprocessor systems.
>>
>>
>>
>>
>>
>> –
>> Mark Roddy
>> — NTDEV is sponsored by OSR For our schedule of WDF, WDM, debugging
>> and other seminars visit: http://www.osr.com/seminars To unsubscribe,
>> visit the List Server section of OSR Online at
>> http://www.osronline.com/page.cfm?name=ListServer
>> —
>> NTDEV is sponsored by OSR
>>
>> For our schedule of WDF, WDM, debugging and other seminars visit:
>> http://www.osr.com/seminars
>>
>> To unsubscribe, visit the List Server section of OSR Online at
>> http://www.osronline.com/page.cfm?name=ListServer
>
>
>
> —
> NTDEV is sponsored by OSR
>
> For our schedule of WDF, WDM, debugging and other seminars visit:
> http://www.osr.com/seminars
>
> To unsubscribe, visit the List Server section of OSR Online at
> http://www.osronline.com/page.cfm?name=ListServer

> Some of us are arguing about the implied connotations of the phrase “spinlock”,

and some of us are arguing about a specific kernel synchronization implementation
in one or more actual operating systems.

I would rather replace the very term “spinlock” with the more generic “atomic lock”. Once the definition of atomicity is relative and may imply different things, depending on context it is used in (no context switches but all interrupts are allowed; no switches or device interrupts, but clock and IP ones are allowed; all maskable interrupts disabled;etc), various implementation strategies are possible - as long as they ensure the sought atomicity as it is understood in a given context, they will qualify for being “atomic lock” implementations…

Anton Bassov

> Or, in C-like prose,

do

{

old_value = atomic_test_and_set (flag,true);

} while (old_value);

The above code is an an example of how spinlocks should *NOT* be implemented - you do atomic ( which, in this context, means interlocked) operations in a busy loop here, which puts a way too much unnecessary pressure on the bus. Instead, you should poll a spinlock variable as a simple read, and proceed to interlocked test-and-set only if it is zero…

Anton Bassov

> http://www.cs.washington.edu/homes/tom/pubs/spinlock.pdf

Typical academic paper - analysis, graphs and all other bullshit. Academicians just love it…

You want to make sure that spinlock gets acquired by the CPU that has requested it first? No problem. It can be easily done the following way (I assume spinlock is DWORD that is originally initialized to 0; a pointer to it is passed to functions in ECX ; and functions are called at elevated IRQL, so that I ignore IRQL issues here)

ReleaseSpinlock: dec word ptr[ecx+2]
ret

AcquireSpinlock: mov bx,1
lock xadd word ptr[ecx],bx
spin: mov ax,bx
add ax, word ptr[ecx+2]
cmp ax,0
jne spin
ret

So much easier that writing “scientific proposals” of few -dozens- pages- size, don’t you think???

Anton Bassov

Actually my view is quite contrary to yours!.

Over the years I learned not to ignore these sort of papers. Not that I like
it in verbatim, but it gives me the spectrum in case I need to look and
analyze it.

Frankly, any thing of this complexity needs to be looked at with broader
spectrum: the node configurations, the memory types, memory configurations,
interconnect types and thier characterstics, CPU family, cache types and
charaterstics etc. etc.

And I think some of the decisions about implementations of these are
primarily based on -

  1. What we have already
  2. What problems (if any) exists in those synch primitives that we have
  3. What we can add to address those problems.

Majority of this thd was about which one ( contending threads trying to
acquire a lock, and a owning thread of a lock) should have the
interruptibiltiy/preemptibility etc. It is not so much about how to have the
atomicitiy but what happens when …

Couple thing(s) I saw in these thread did not make much sense to me
though —

  1. We all know by now that discussion of this sort always assumes (processes
    or threads ). We are in a multiprogramming situations ( contending
    schedulable entities) fighting for that piece of bread(i.e. the lock ). And
    yet I’ve seen many instances of bear metal ( no thd. or proc ) in this
    discussion.

  2. Any mutually exclusive types lock is by nature implememts atomicity. It
    could be a single instruction or it could be a 3 mile long code that
    executes under atomicity.

  3. As usual I’m also not very succinct in my pervious response.

Finally, the definition of spinlock ( in OS literature) is very shallow as
this paper ( and majority of this thread) tries to point out…

Happy newyear to everyone who cares to read this :slight_smile:

-pro
----- Original Message -----
From:
To: “Windows System Software Devs Interest List”
Sent: Friday, December 28, 2007 3:15 AM
Subject: RE:[ntdev] Are callbacks guaranteed to run consecutively?

>> http://www.cs.washington.edu/homes/tom/pubs/spinlock.pdf
>
> Typical academic paper - analysis, graphs and all other bullshit.
> Academicians just love it…
>
> You want to make sure that spinlock gets acquired by the CPU that has
> requested it first? No problem. It can be easily done the following way (I
> assume spinlock is DWORD that is originally initialized to 0; a pointer
> to it is passed to functions in ECX ; and functions are called at
> elevated IRQL, so that I ignore IRQL issues here)
>
> ReleaseSpinlock: dec word ptr[ecx+2]
> ret
>
>
> AcquireSpinlock: mov bx,1
> lock xadd word ptr[ecx],bx
> spin: mov ax,bx
> add ax, word ptr[ecx+2]
> cmp ax,0
> jne spin
> ret
>
>
> So much easier that writing “scientific proposals” of few -dozens- pages-
> size, don’t you think???
>
> Anton Bassov
>
> —
> NTDEV is sponsored by OSR
>
> For our schedule of WDF, WDM, debugging and other seminars visit:
> http://www.osr.com/seminars
>
> To unsubscribe, visit the List Server section of OSR Online at
> http://www.osronline.com/page.cfm?name=ListServer

What you propose - which is also proposed in the paper, by the way - is
already higher level than the bare bones spinlock. It uses a hardware lock.
What if your processors don’t support a bus level hardware lock ? What if
they’re not bus oriented ?

I would call is a “busy spin mutex” or something in that direction. it’s not
a spinlock any longer! The concept of “acquiring” a spinlock, as you
describe, makes the construct a higher level one, which relies on a bus lock
to work.

The author tried to analyze different hardware approaches to the problem of
efficiently supporting a spinlock construct in hardware. If you read the
paper, you see that the author measures a straight test-and-set spinlock
against a test-and-test-and-set spinlock, and presents actual measured data
on the performance differences. He also mentions that the
test-and-test-and-set protocol has worse measured performance than expected,
which is somewhat of a surprise. He then advocates exactly what you wrote:
adding an acquire protocol to the spinlock.

Then he goes on, examining different alternatives, such as applying delays
to the loop to lower the frontside bus traffic, queuing accesses, and so on.
He concludes by suggesting a few hardware-level mechanisms that he believes
would improve performance, including the tested-and-tried Ethernet-style
exponential backoff.

There’s a lot more in that paper than what your code purports! I find it
well written and to the point.

Alberto.

----- Original Message -----
From:
To: “Windows System Software Devs Interest List”
Sent: Friday, December 28, 2007 6:15 AM
Subject: RE:[ntdev] Are callbacks guaranteed to run consecutively?

>> http://www.cs.washington.edu/homes/tom/pubs/spinlock.pdf
>
> Typical academic paper - analysis, graphs and all other bullshit.
> Academicians just love it…
>
> You want to make sure that spinlock gets acquired by the CPU that has
> requested it first? No problem. It can be easily done the following way (I
> assume spinlock is DWORD that is originally initialized to 0; a pointer
> to it is passed to functions in ECX ; and functions are called at
> elevated IRQL, so that I ignore IRQL issues here)
>
> ReleaseSpinlock: dec word ptr[ecx+2]
> ret
>
>
> AcquireSpinlock: mov bx,1
> lock xadd word ptr[ecx],bx
> spin: mov ax,bx
> add ax, word ptr[ecx+2]
> cmp ax,0
> jne spin
> ret
>
>
> So much easier that writing “scientific proposals” of few -dozens- pages-
> size, don’t you think???
>
> Anton Bassov
>
> —
> NTDEV is sponsored by OSR
>
> For our schedule of WDF, WDM, debugging and other seminars visit:
> http://www.osr.com/seminars
>
> To unsubscribe, visit the List Server section of OSR Online at
> http://www.osronline.com/page.cfm?name=ListServer

But a spinlock doesn’t need to be atomic. The individual read-then-write
access needs to be atomic, and that is enforced by the hardware bus
protocol. The loop, however is not atomic, and it doesn’t need to be. Once
you enforce atomicity, call it a mutex-and-spinlock, or whatever! It’s no
longer a garden variety spinlock.

A standard spinlock requires one bit. That’s it.

Alberto.

----- Original Message -----
From:
To: “Windows System Software Devs Interest List”
Sent: Thursday, December 27, 2007 11:31 PM
Subject: RE:[ntdev] Are callbacks guaranteed to run consecutively?

>> Some of us are arguing about the implied connotations of the phrase
>> “spinlock”,
>> and some of us are arguing about a specific kernel synchronization
>> implementation
>> in one or more actual operating systems.
>
> I would rather replace the very term “spinlock” with the more generic
> “atomic lock”. Once the definition of atomicity is relative and may imply
> different things, depending on context it is used in (no context switches
> but all interrupts are allowed; no switches or device interrupts, but
> clock and IP ones are allowed; all maskable interrupts disabled;etc),
> various implementation strategies are possible - as long as they ensure
> the sought atomicity as it is understood in a given context, they will
> qualify for being “atomic lock” implementations…
>
> Anton Bassov
>
> —
> NTDEV is sponsored by OSR
>
> For our schedule of WDF, WDM, debugging and other seminars visit:
> http://www.osr.com/seminars
>
> To unsubscribe, visit the List Server section of OSR Online at
> http://www.osronline.com/page.cfm?name=ListServer

Preemption here is hardware. An interrupt happens, generates the equivalent
of a forced call to an isr. The isr gets control, does whatever it needs to
do very, very fast, and irets back to the caller, who keeps on spinning. And
the whole point of spinning is exactly that you know that you need to hog
the processor on that spinning loop, because it isn’t safe to proceed
otherwise.

And if you use the opportunity to wrestle processor control away from the
spin loop, you’re engaging in dangerous behavior that can easily lead into a
deadlock or livelock. That’s when that “contract” thing becomes necessary,
and all hell breaks loose because people want to embellish a barebones
construct into something it was never meant to be.

The way I see it, and I may be wrong, even when a spinlock loop can be
preempted by the hardware, it should not be interfered with by the OS.
Spinlocks should be subarchitectural to the OS: the lowest peel of the
onion!

Alberto.

----- Original Message -----
From:
To: “Windows System Software Devs Interest List”
Sent: Thursday, December 27, 2007 6:27 PM
Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?

> Preemption is allowed, but not suspension :slight_smile:
>
> What really is the motive for coming up with such a synch* primitive? Why
> not mutex? Why not event? Why not semaphore with count == 1 ?
>
> The motive is not to trap the HW in an useless state. If preemption is not
> allowed, how would the system maintain other higher priority problem(s)
> and tasks ( clocks, instruction OP code problems, and other stuff ).
>
> The context switching is one of the culprit ( heavy over head ) of those
> suspendable synch primitive. A suspendable synch primitive is one where
> the acquiring thread could be suspended, and rescheduled, and again
> suspended …
>
> It is definitely this suspension, that motivated spinlock. Now if they
> are also not preemptible then there is a real problem though.
>
> It is altogether a different story, if someone tries to optimize the bus
> traffic by not polling the flag/lock too often, but that is still spinning
> and not suspending or going to wait state where scheduler/dispatcher -
> intervention is needed to bring the said thread into execution.
>
> -pro
>> A spinlock is supposed to stall a processor. It’s a strong tool to be
>> used
>> as an arbiter of last resort. It works like this:
>>
>> top: atomic_test_and_set location,true
>> jump_if_old_value_is_true top
>>
>> Or, in C-like prose,
>>
>> do
>> {
>> old_value = atomic_test_and_set (flag,true);
>> }
>> while (old_value);
>>
>> To clear a spinlock is even simpler:
>>
>> flag = false;
>>
>> There’s no yielding of any sort here. Spinlocks don’t block, don’t yield,
>> and they’re also not aware of processes, threads, or whatever. It may be
>> the case that an interrupt causes a context switch, but once control
>> comes
>> back, the loop carries on. And I’m definitely not sold on the wisdom of
>> allowing certain kinds of interrupts and locks to be preempted.
>>
>> You can dress up a spinlock with all sorts of extra baggage, but the more
>> you add, the less it looks like a spinlock!
>>
>>
>> Alberto.
>>
>>
>>
>>
>> ----- Original Message -----
>> From: Mark Roddy
>> To: Windows System Software Devs Interest List
>> Sent: Wednesday, December 26, 2007 10:57 AM
>> Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?
>>
>>
>>
>>
>>
>> On Dec 26, 2007 9:22 AM, Alberto Moreira wrote:
>>
>> I’m sorry, people, I’m going to put on my computer science hat now
>> and
>> say that whatever this is, it ain’t a spinlock. The whole point of a
>> spinlock is to spin without yielding execution!
>>
>> At least provide an accurate definition. " The whole point of a
>> spinlock
>> is to spin without yielding execution! " No that isn’t the whole
>> point. That is a distinct feature. And everything we have discussed
>> here, with the exception of the AIX style ‘spin a while, then sleep’
>> implementation, doesn’t ‘yield execution’. What we have discussed is
>> that on NT, and most other modern multiprocessor general purpose
>> operating systems, spinlocks are interruptible. The currently executing
>> thread does not yield execution, it is interrupted, runs some isr, and
>> then returns to spinning. Implementations of spinlocks could block all
>> interrupts and never allow the processor to do anything other than busy
>> wait for the lock. Such implementations are generally considered
>> deficient as they block management of timers and TLBs and other critical
>> global OS resources while not providing any added benefit. You are of
>> course free to implement this sort of deficient simplistic private
>> spinlock, but I would suggest not deploying this spinlock of yours on
>> general purpose multiprocessor systems.
>>
>>
>>
>>
>>
>> –
>> Mark Roddy
>> — NTDEV is sponsored by OSR For our schedule of WDF, WDM, debugging
>> and other seminars visit: http://www.osr.com/seminars To unsubscribe,
>> visit the List Server section of OSR Online at
>> http://www.osronline.com/page.cfm?name=ListServer
>> —
>> NTDEV is sponsored by OSR
>>
>> For our schedule of WDF, WDM, debugging and other seminars visit:
>> http://www.osr.com/seminars
>>
>> To unsubscribe, visit the List Server section of OSR Online at
>> http://www.osronline.com/page.cfm?name=ListServer
>
>
>
> —
> NTDEV is sponsored by OSR
>
> For our schedule of WDF, WDM, debugging and other seminars visit:
> http://www.osr.com/seminars
>
> To unsubscribe, visit the List Server section of OSR Online at
> http://www.osronline.com/page.cfm?name=ListServer

Ah, now you are speaking :-).

Yes I also agree that OS should not interfare in the sense of taking it out
of execution, put thru the grinding mills of whatever ( round robin,
priority based round robin … ) types of scheduling. But as you said the
interruptiblity should be allowed. There has to have a mechnism to let the
other high priority work to keep that processor’s sanity.

But as mark said, AIX has that yielding ( and I assume it pump the thread to
the process/thd table for it tobe scheduled later). Well it is not really a
spinlock in true spirit. And that is why I mentioned that the whole purpose
of coming up with spinlock is to reduce scheduling overhead ( as acquiring
thd finds it is wokenup and goes back to sleep, … ).

But I never said it is not “Art of computer programming”. It is very much an
art :slight_smile:

-pro

----- Original Message -----
From: “Alberto Moreira”
To: “Windows System Software Devs Interest List”
Sent: Friday, December 28, 2007 7:40 AM
Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?

> Preemption here is hardware. An interrupt happens, generates the
> equivalent of a forced call to an isr. The isr gets control, does whatever
> it needs to do very, very fast, and irets back to the caller, who keeps on
> spinning. And the whole point of spinning is exactly that you know that
> you need to hog the processor on that spinning loop, because it isn’t safe
> to proceed otherwise.
>
> And if you use the opportunity to wrestle processor control away from the
> spin loop, you’re engaging in dangerous behavior that can easily lead into
> a deadlock or livelock. That’s when that “contract” thing becomes
> necessary, and all hell breaks loose because people want to embellish a
> barebones construct into something it was never meant to be.
>
> The way I see it, and I may be wrong, even when a spinlock loop can be
> preempted by the hardware, it should not be interfered with by the OS.
> Spinlocks should be subarchitectural to the OS: the lowest peel of the
> onion!
>
> Alberto.
>
>
>
> ----- Original Message -----
> From:
> To: “Windows System Software Devs Interest List”
> Sent: Thursday, December 27, 2007 6:27 PM
> Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?
>
>
>> Preemption is allowed, but not suspension :slight_smile:
>>
>> What really is the motive for coming up with such a synch* primitive? Why
>> not mutex? Why not event? Why not semaphore with count == 1 ?
>>
>> The motive is not to trap the HW in an useless state. If preemption is
>> not
>> allowed, how would the system maintain other higher priority problem(s)
>> and tasks ( clocks, instruction OP code problems, and other stuff ).
>>
>> The context switching is one of the culprit ( heavy over head ) of those
>> suspendable synch primitive. A suspendable synch primitive is one where
>> the acquiring thread could be suspended, and rescheduled, and again
>> suspended …
>>
>> It is definitely this suspension, that motivated spinlock. Now if they
>> are also not preemptible then there is a real problem though.
>>
>> It is altogether a different story, if someone tries to optimize the bus
>> traffic by not polling the flag/lock too often, but that is still
>> spinning
>> and not suspending or going to wait state where scheduler/dispatcher -
>> intervention is needed to bring the said thread into execution.
>>
>> -pro
>>> A spinlock is supposed to stall a processor. It’s a strong tool to be
>>> used
>>> as an arbiter of last resort. It works like this:
>>>
>>> top: atomic_test_and_set location,true
>>> jump_if_old_value_is_true top
>>>
>>> Or, in C-like prose,
>>>
>>> do
>>> {
>>> old_value = atomic_test_and_set (flag,true);
>>> }
>>> while (old_value);
>>>
>>> To clear a spinlock is even simpler:
>>>
>>> flag = false;
>>>
>>> There’s no yielding of any sort here. Spinlocks don’t block, don’t
>>> yield,
>>> and they’re also not aware of processes, threads, or whatever. It may be
>>> the case that an interrupt causes a context switch, but once control
>>> comes
>>> back, the loop carries on. And I’m definitely not sold on the wisdom of
>>> allowing certain kinds of interrupts and locks to be preempted.
>>>
>>> You can dress up a spinlock with all sorts of extra baggage, but the
>>> more
>>> you add, the less it looks like a spinlock!
>>>
>>>
>>> Alberto.
>>>
>>>
>>>
>>>
>>> ----- Original Message -----
>>> From: Mark Roddy
>>> To: Windows System Software Devs Interest List
>>> Sent: Wednesday, December 26, 2007 10:57 AM
>>> Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?
>>>
>>>
>>>
>>>
>>>
>>> On Dec 26, 2007 9:22 AM, Alberto Moreira wrote:
>>>
>>> I’m sorry, people, I’m going to put on my computer science hat now
>>> and
>>> say that whatever this is, it ain’t a spinlock. The whole point of a
>>> spinlock is to spin without yielding execution!
>>>
>>> At least provide an accurate definition. " The whole point of a
>>> spinlock
>>> is to spin without yielding execution! " No that isn’t the whole
>>> point. That is a distinct feature. And everything we have discussed
>>> here, with the exception of the AIX style ‘spin a while, then sleep’
>>> implementation, doesn’t ‘yield execution’. What we have discussed is
>>> that on NT, and most other modern multiprocessor general purpose
>>> operating systems, spinlocks are interruptible. The currently executing
>>> thread does not yield execution, it is interrupted, runs some isr, and
>>> then returns to spinning. Implementations of spinlocks could block all
>>> interrupts and never allow the processor to do anything other than busy
>>> wait for the lock. Such implementations are generally considered
>>> deficient as they block management of timers and TLBs and other critical
>>> global OS resources while not providing any added benefit. You are of
>>> course free to implement this sort of deficient simplistic private
>>> spinlock, but I would suggest not deploying this spinlock of yours on
>>> general purpose multiprocessor systems.
>>>
>>>
>>>
>>>
>>>
>>> –
>>> Mark Roddy
>>> — NTDEV is sponsored by OSR For our schedule of WDF, WDM, debugging
>>> and other seminars visit: http://www.osr.com/seminars To unsubscribe,
>>> visit the List Server section of OSR Online at
>>> http://www.osronline.com/page.cfm?name=ListServer
>>> —
>>> NTDEV is sponsored by OSR
>>>
>>> For our schedule of WDF, WDM, debugging and other seminars visit:
>>> http://www.osr.com/seminars
>>>
>>> To unsubscribe, visit the List Server section of OSR Online at
>>> http://www.osronline.com/page.cfm?name=ListServer
>>
>>
>>
>> —
>> NTDEV is sponsored by OSR
>>
>> For our schedule of WDF, WDM, debugging and other seminars visit:
>> http://www.osr.com/seminars
>>
>> To unsubscribe, visit the List Server section of OSR Online at
>> http://www.osronline.com/page.cfm?name=ListServer
>
>
> —
> NTDEV is sponsored by OSR
>
> For our schedule of WDF, WDM, debugging and other seminars visit:
> http://www.osr.com/seminars
>
> To unsubscribe, visit the List Server section of OSR Online at
> http://www.osronline.com/page.cfm?name=ListServer

On an MP system there simply is no guarantee of that “very, very fast”
quality. The spinlock busy wait can be deferred indefinately by
interrupts, unless of course the spinlock busy wait is executed at a high
enough interrupt level to prevent such indeterminacy.

On Dec 28, 2007 10:40 AM, Alberto Moreira wrote:

> Preemption here is hardware. An interrupt happens, generates the
> equivalent
> of a forced call to an isr. The isr gets control, does whatever it needs
> to
> do very, very fast, and irets back to the caller, who keeps on spinning.
> And
> the whole point of spinning is exactly that you know that you need to hog
> the processor on that spinning loop, because it isn’t safe to proceed
> otherwise.
>
> And if you use the opportunity to wrestle processor control away from the
> spin loop, you’re engaging in dangerous behavior that can easily lead into
> a
> deadlock or livelock. That’s when that “contract” thing becomes necessary,
> and all hell breaks loose because people want to embellish a barebones
> construct into something it was never meant to be.
>
> The way I see it, and I may be wrong, even when a spinlock loop can be
> preempted by the hardware, it should not be interfered with by the OS.
> Spinlocks should be subarchitectural to the OS: the lowest peel of the
> onion!
>
> Alberto.
>
>
>
> ----- Original Message -----
> From:
> To: “Windows System Software Devs Interest List”
> Sent: Thursday, December 27, 2007 6:27 PM
> Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?
>
>
> > Preemption is allowed, but not suspension :slight_smile:
> >
> > What really is the motive for coming up with such a synch* primitive?
> Why
> > not mutex? Why not event? Why not semaphore with count == 1 ?
> >
> > The motive is not to trap the HW in an useless state. If preemption is
> not
> > allowed, how would the system maintain other higher priority problem(s)
> > and tasks ( clocks, instruction OP code problems, and other stuff ).
> >
> > The context switching is one of the culprit ( heavy over head ) of those
> > suspendable synch primitive. A suspendable synch primitive is one where
> > the acquiring thread could be suspended, and rescheduled, and again
> > suspended …
> >
> > It is definitely this suspension, that motivated spinlock. Now if they
> > are also not preemptible then there is a real problem though.
> >
> > It is altogether a different story, if someone tries to optimize the bus
> > traffic by not polling the flag/lock too often, but that is still
> spinning
> > and not suspending or going to wait state where scheduler/dispatcher -
> > intervention is needed to bring the said thread into execution.
> >
> > -pro
> >> A spinlock is supposed to stall a processor. It’s a strong tool to be
> >> used
> >> as an arbiter of last resort. It works like this:
> >>
> >> top: atomic_test_and_set location,true
> >> jump_if_old_value_is_true top
> >>
> >> Or, in C-like prose,
> >>
> >> do
> >> {
> >> old_value = atomic_test_and_set (flag,true);
> >> }
> >> while (old_value);
> >>
> >> To clear a spinlock is even simpler:
> >>
> >> flag = false;
> >>
> >> There’s no yielding of any sort here. Spinlocks don’t block, don’t
> yield,
> >> and they’re also not aware of processes, threads, or whatever. It may
> be
> >> the case that an interrupt causes a context switch, but once control
> >> comes
> >> back, the loop carries on. And I’m definitely not sold on the wisdom of
> >> allowing certain kinds of interrupts and locks to be preempted.
> >>
> >> You can dress up a spinlock with all sorts of extra baggage, but the
> more
> >> you add, the less it looks like a spinlock!
> >>
> >>
> >> Alberto.
> >>
> >>
> >>
> >>
> >> ----- Original Message -----
> >> From: Mark Roddy
> >> To: Windows System Software Devs Interest List
> >> Sent: Wednesday, December 26, 2007 10:57 AM
> >> Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?
> >>
> >>
> >>
> >>
> >>
> >> On Dec 26, 2007 9:22 AM, Alberto Moreira wrote:
> >>
> >> I’m sorry, people, I’m going to put on my computer science hat now
> >> and
> >> say that whatever this is, it ain’t a spinlock. The whole point of a
> >> spinlock is to spin without yielding execution!
> >>
> >> At least provide an accurate definition. " The whole point of a
> >> spinlock
> >> is to spin without yielding execution! " No that isn’t the whole
> >> point. That is a distinct feature. And everything we have discussed
> >> here, with the exception of the AIX style ‘spin a while, then sleep’
> >> implementation, doesn’t ‘yield execution’. What we have discussed is
> >> that on NT, and most other modern multiprocessor general purpose
> >> operating systems, spinlocks are interruptible. The currently executing
> >> thread does not yield execution, it is interrupted, runs some isr, and
> >> then returns to spinning. Implementations of spinlocks could block all
> >> interrupts and never allow the processor to do anything other than busy
> >> wait for the lock. Such implementations are generally considered
> >> deficient as they block management of timers and TLBs and other
> critical
> >> global OS resources while not providing any added benefit. You are of
> >> course free to implement this sort of deficient simplistic private
> >> spinlock, but I would suggest not deploying this spinlock of yours on
> >> general purpose multiprocessor systems.
> >>
> >>
> >>
> >>
> >>
> >> –
> >> Mark Roddy
> >> — NTDEV is sponsored by OSR For our schedule of WDF, WDM, debugging
> >> and other seminars visit: http://www.osr.com/seminars To unsubscribe,
> >> visit the List Server section of OSR Online at
> >> http://www.osronline.com/page.cfm?name=ListServer
> >> —
> >> NTDEV is sponsored by OSR
> >>
> >> For our schedule of WDF, WDM, debugging and other seminars visit:
> >> http://www.osr.com/seminars
> >>
> >> To unsubscribe, visit the List Server section of OSR Online at
> >> http://www.osronline.com/page.cfm?name=ListServer
> >
> >
> >
> > —
> > NTDEV is sponsored by OSR
> >
> > For our schedule of WDF, WDM, debugging and other seminars visit:
> > http://www.osr.com/seminars
> >
> > To unsubscribe, visit the List Server section of OSR Online at
> > http://www.osronline.com/page.cfm?name=ListServer
>
>
> —
> NTDEV is sponsored by OSR
>
> For our schedule of WDF, WDM, debugging and other seminars visit:
> http://www.osr.com/seminars
>
> To unsubscribe, visit the List Server section of OSR Online at
> http://www.osronline.com/page.cfm?name=ListServer
>


Mark Roddy

> What you propose - which is also proposed in the paper, by the way…

Actually, I don’t propose anything - I just showed what the paper is *essentially* about, and essentially it is all about a thing that can get done in less than 10 assembly instructions (plus few lines of comments). However, they somehow managed to write few -dozens- pages- size document with “scientific proposals” out of it. This is one of the reasons why I take all these “scientists” and academicians rather ironically. What they are really good at is taking a simple concept , adding various bullshit that is expressed in “sophisticated” terms to it (academicians just cannot live without trying to sound “clever”), and, as a result, arriving to a huge document with “scientific proposals”. However, ask them to write a piece of code that is meant to work *in real life*, and you will see what they are actually worth - the only thing they are good at is speaking…

…is already higher level than the bare bones spinlock

I just wonder what “bare bones spinlock” is …

It uses a hardware lock.

Well, all spinlock do - otherwise, it already would not be a construct that is able to provide MP safety. More on it below…

What if your processors don’t support a bus level hardware lock ?

I am afraid the whole concept of a spinlock is plainly infeasible on such system. There are numerous ways to implement a spinlock - it can be set-and-test; it can be exchange-and-add;
it can be decrementing zero or incrementing 0xFFFFFFFF so that you are able to check overflow flag ;etc;etc;etc. However, all these strategies involve more than one action at the hardware level (i.e. changing variable and setting flag in EFLAGS; adding source and destination and exchanging them; etc). In order to make the very concept of a spinlock workable, all these actions have to be performed atomically by the hardware, which means they require bus locking - you just cannot ensure MP safety if some other bus agent is able to sneak in and modify the target memory location before your operation has been accomplished. This is why all spinlocks use LOCK prefix…

The author tried to analyze different hardware approaches to the problem of
efficiently supporting a spinlock construct in hardware.

… on the system that does not even provide a bus-level hardware lock ??? I wish him good luck…

Anton Bassov

Furthermore, it’s almost a guarantee on a virtualized system that
you’ll end up some day with your virtual processor unscheduled right
in the middle of something that you thought was “very, very fast.”

  • Jake Oshins

“Mark Roddy” wrote in message
news:xxxxx@ntdev…
On an MP system there simply is no guarantee of that “very, very fast”
quality. The spinlock busy wait can be deferred indefinately by
interrupts, unless of course the spinlock busy wait is executed at a
high enough interrupt level to prevent such indeterminacy.

On Dec 28, 2007 10:40 AM, Alberto Moreira wrote:

Preemption here is hardware. An interrupt happens, generates the
equivalent
of a forced call to an isr. The isr gets control, does whatever it
needs to
do very, very fast, and irets back to the caller, who keeps on
spinning. And
the whole point of spinning is exactly that you know that you need to
hog
the processor on that spinning loop, because it isn’t safe to proceed
otherwise.

And if you use the opportunity to wrestle processor control away from
the
spin loop, you’re engaging in dangerous behavior that can easily lead
into a
deadlock or livelock. That’s when that “contract” thing becomes
necessary,
and all hell breaks loose because people want to embellish a barebones
construct into something it was never meant to be.

The way I see it, and I may be wrong, even when a spinlock loop can be
preempted by the hardware, it should not be interfered with by the OS.
Spinlocks should be subarchitectural to the OS: the lowest peel of the
onion!

Alberto.

----- Original Message -----
From:
To: “Windows System Software Devs Interest List”
Sent: Thursday, December 27, 2007 6:27 PM
Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?

> Preemption is allowed, but not suspension :slight_smile:
>
> What really is the motive for coming up with such a synch*
> primitive? Why
> not mutex? Why not event? Why not semaphore with count == 1 ?
>
> The motive is not to trap the HW in an useless state. If preemption
> is not
> allowed, how would the system maintain other higher priority
> problem(s)
> and tasks ( clocks, instruction OP code problems, and other stuff ).
>
> The context switching is one of the culprit ( heavy over head ) of
> those
> suspendable synch primitive. A suspendable synch primitive is one
> where
> the acquiring thread could be suspended, and rescheduled, and again
> suspended …
>
> It is definitely this suspension, that motivated spinlock. Now if
> they
> are also not preemptible then there is a real problem though.
>
> It is altogether a different story, if someone tries to optimize the
> bus
> traffic by not polling the flag/lock too often, but that is still
> spinning
> and not suspending or going to wait state where
> scheduler/dispatcher -
> intervention is needed to bring the said thread into execution.
>
> -pro
>> A spinlock is supposed to stall a processor. It’s a strong tool to
>> be
>> used
>> as an arbiter of last resort. It works like this:
>>
>> top: atomic_test_and_set location,true
>> jump_if_old_value_is_true top
>>
>> Or, in C-like prose,
>>
>> do
>> {
>> old_value = atomic_test_and_set (flag,true);
>> }
>> while (old_value);
>>
>> To clear a spinlock is even simpler:
>>
>> flag = false;
>>
>> There’s no yielding of any sort here. Spinlocks don’t block, don’t
>> yield,
>> and they’re also not aware of processes, threads, or whatever. It
>> may be
>> the case that an interrupt causes a context switch, but once
>> control
>> comes
>> back, the loop carries on. And I’m definitely not sold on the
>> wisdom of
>> allowing certain kinds of interrupts and locks to be preempted.
>>
>> You can dress up a spinlock with all sorts of extra baggage, but
>> the more
>> you add, the less it looks like a spinlock!
>>
>>
>> Alberto.
>>
>>
>>
>>
>> ----- Original Message -----
>> From: Mark Roddy
>> To: Windows System Software Devs Interest List
>> Sent: Wednesday, December 26, 2007 10:57 AM
>> Subject: Re: [ntdev] Are callbacks guaranteed to run
>> consecutively?
>>
>>
>>
>>
>>
>> On Dec 26, 2007 9:22 AM, Alberto Moreira < xxxxx@ieee.org>
>> wrote:
>>
>> I’m sorry, people, I’m going to put on my computer science hat
>> now
>> and
>> say that whatever this is, it ain’t a spinlock. The whole point of
>> a
>> spinlock is to spin without yielding execution!
>>
>> At least provide an accurate definition. " The whole point of a
>> spinlock
>> is to spin without yielding execution! " No that isn’t the whole
>> point. That is a distinct feature. And everything we have discussed
>> here, with the exception of the AIX style ‘spin a while, then
>> sleep’
>> implementation, doesn’t ‘yield execution’. What we have discussed
>> is
>> that on NT, and most other modern multiprocessor general purpose
>> operating systems, spinlocks are interruptible. The currently
>> executing
>> thread does not yield execution, it is interrupted, runs some isr,
>> and
>> then returns to spinning. Implementations of spinlocks could block
>> all
>> interrupts and never allow the processor to do anything other than
>> busy
>> wait for the lock. Such implementations are generally considered
>> deficient as they block management of timers and TLBs and other
>> critical
>> global OS resources while not providing any added benefit. You are
>> of
>> course free to implement this sort of deficient simplistic private
>> spinlock, but I would suggest not deploying this spinlock of yours
>> on
>> general purpose multiprocessor systems.
>>
>>
>>
>>
>>
>> –
>> Mark Roddy
>> — NTDEV is sponsored by OSR For our schedule of WDF, WDM,
>> debugging
>> and other seminars visit: http://www.osr.com/seminars To
>> unsubscribe,
>> visit the List Server section of OSR Online at
>> http://www.osronline.com/page.cfm?name=ListServer
>> —
>> NTDEV is sponsored by OSR
>>
>> For our schedule of WDF, WDM, debugging and other seminars visit:
>> http://www.osr.com/seminars
>>
>> To unsubscribe, visit the List Server section of OSR Online at
>> http://www.osronline.com/page.cfm?name=ListServer
>
>
>
> —
> NTDEV is sponsored by OSR
>
> For our schedule of WDF, WDM, debugging and other seminars visit:
> http://www.osr.com/seminars
>
> To unsubscribe, visit the List Server section of OSR Online at
> http://www.osronline.com/page.cfm?name=ListServer


NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at
http://www.osronline.com/page.cfm?name=ListServer


Mark Roddy

> On an MP system there simply is no guarantee of that “very, very fast” quality.

The spinlock busy wait can be deferred indefinately by interrupts, unless of course
the spinlock busy wait is executed at a high enough interrupt level to prevent
such indeterminacy.

Well, you can disable all maskable interrupts, but even then your spinning can get interrupted by SMI that is non-maskable and is completely transparent to the OS software…

Anton Bassov

> A standard spinlock requires one bit. That’s it.

Wrong!!! In addition to changing the target bit a "standard "spinlock requires also setting the flag in EFLAGS that tells you whether the state of the bit got changed by your set-and-test operation.

Therefore, spinlock acquisition requires changing at least two operands, and these operands have to be changed by the CPU as an atomic operation that cannot be disrupted by any other bus agent. This is why, as I have already said in my previous post. there is no way to write a spinlock that ensures MP safety if the target hardware does not support bus locking…

Anton Bassov

The flag is automatically maintained by the processor and saved/restored by
the hardware when an interrupt occurs. There is no need whatsoever that the
test and the conditional jump are done in one atomic operation, unless of
course an interrupt is ill-behaved enough that it doesn’t return back to the
interrupted code with an iret and an intact stack. The test-and-set
instruction must be atomic, and the hardware guarantees it.

The flag has nothing to do with being multiprocessor safe. There is no way
on earth that another processor or any bus agent can change the zero flag on
the looping processor. What can be interfered by another processor or bus
agent is the read-modify-write cycle that’s required to do a test-and-set on
shared memory, because another processor or another bus agent may insert one
or more cycles between the read and the write that are part of the execution
of the test and set operation.
The code

top: test-and-set bit, true
jump-if-not-zero top

is one hundred per cent multiprocessor safe on a bus-based i386 SMP. Mind
you, the memory location being referenced doesn’t even need to be
noncacheable, because the MESI protocol takes care of it for you.

Alberto.

----- Original Message -----
From:
To: “Windows System Software Devs Interest List”
Sent: Friday, December 28, 2007 7:06 PM
Subject: RE:[ntdev] Are callbacks guaranteed to run consecutively?

>> A standard spinlock requires one bit. That’s it.
>
> Wrong!!! In addition to changing the target bit a "standard "spinlock
> requires also setting the flag in EFLAGS that tells you whether the state
> of the bit got changed by your set-and-test operation.
>
> Therefore, spinlock acquisition requires changing at least two operands,
> and these operands have to be changed by the CPU as an atomic operation
> that cannot be disrupted by any other bus agent. This is why, as I have
> already said in my previous post. there is no way to write a spinlock that
> ensures MP safety if the target hardware does not support bus locking…
>
> Anton Bassov
>
> —
> NTDEV is sponsored by OSR
>
> For our schedule of WDF, WDM, debugging and other seminars visit:
> http://www.osr.com/seminars
>
> To unsubscribe, visit the List Server section of OSR Online at
> http://www.osronline.com/page.cfm?name=ListServer

I disagree. If an interrupt routine runs unpreempted, whatever happens in other processors is irrelevant. Just get in with interrupts disabled, do the job fast, and get out.

But hey, if you allow unlimited preemption by interrupt routines, virtualization stuff going on inside subarchitectural loops, and what not, then obviously your “very fast” is up for grabs. Yet, blame it on the OS design, not on the concept!

Look at it this way. If I’m running a spinlock A which is interrupted by isr B which is interrupted by isr C, if you allow unlimited preemption what you’re really doing is queuing A behind B and B behind C. Given that we’re talking about one processor here (even in an SMP, eh ?), this preemption generates overhead in terms of saving and restoring registers, switching context, and so on, which could be avoided: the place to queue interrupts is in the APIC, independent of the code being executed by the processor.

That’s what I mean when I say “do it fast”. Do not preempt - it’s unnecessary, wastes time burning overhead cycles, and generates complexity and deadlock/livelock dangers that we could do without.

Alberto.

----- Original Message -----
From: Mark Roddy
To: Windows System Software Devs Interest List
Sent: Friday, December 28, 2007 11:09 AM
Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?

On an MP system there simply is no guarantee of that “very, very fast” quality. The spinlock busy wait can be deferred indefinately by interrupts, unless of course the spinlock busy wait is executed at a high enough interrupt level to prevent such indeterminacy.

On Dec 28, 2007 10:40 AM, Alberto Moreira wrote:

Preemption here is hardware. An interrupt happens, generates the equivalent
of a forced call to an isr. The isr gets control, does whatever it needs to
do very, very fast, and irets back to the caller, who keeps on spinning. And
the whole point of spinning is exactly that you know that you need to hog
the processor on that spinning loop, because it isn’t safe to proceed
otherwise.

And if you use the opportunity to wrestle processor control away from the
spin loop, you’re engaging in dangerous behavior that can easily lead into a
deadlock or livelock. That’s when that “contract” thing becomes necessary,
and all hell breaks loose because people want to embellish a barebones
construct into something it was never meant to be.

The way I see it, and I may be wrong, even when a spinlock loop can be
preempted by the hardware, it should not be interfered with by the OS.
Spinlocks should be subarchitectural to the OS: the lowest peel of the
onion!

Alberto.

----- Original Message -----
From:
To: “Windows System Software Devs Interest List”
Sent: Thursday, December 27, 2007 6:27 PM
Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?

> Preemption is allowed, but not suspension :slight_smile:
>
> What really is the motive for coming up with such a synch* primitive? Why
> not mutex? Why not event? Why not semaphore with count == 1 ?
>
> The motive is not to trap the HW in an useless state. If preemption is not
> allowed, how would the system maintain other higher priority problem(s)
> and tasks ( clocks, instruction OP code problems, and other stuff ).
>
> The context switching is one of the culprit ( heavy over head ) of those
> suspendable synch primitive. A suspendable synch primitive is one where
> the acquiring thread could be suspended, and rescheduled, and again
> suspended …
>
> It is definitely this suspension, that motivated spinlock. Now if they
> are also not preemptible then there is a real problem though.
>
> It is altogether a different story, if someone tries to optimize the bus
> traffic by not polling the flag/lock too often, but that is still spinning
> and not suspending or going to wait state where scheduler/dispatcher -
> intervention is needed to bring the said thread into execution.
>
> -pro
>> A spinlock is supposed to stall a processor. It’s a strong tool to be
>> used
>> as an arbiter of last resort. It works like this:
>>
>> top: atomic_test_and_set location,true
>> jump_if_old_value_is_true top
>>
>> Or, in C-like prose,
>>
>> do
>> {
>> old_value = atomic_test_and_set (flag,true);
>> }
>> while (old_value);
>>
>> To clear a spinlock is even simpler:
>>
>> flag = false;
>>
>> There’s no yielding of any sort here. Spinlocks don’t block, don’t yield,
>> and they’re also not aware of processes, threads, or whatever. It may be
>> the case that an interrupt causes a context switch, but once control
>> comes
>> back, the loop carries on. And I’m definitely not sold on the wisdom of
>> allowing certain kinds of interrupts and locks to be preempted.
>>
>> You can dress up a spinlock with all sorts of extra baggage, but the more
>> you add, the less it looks like a spinlock!
>>
>>
>> Alberto.
>>
>>
>>
>>
>> ----- Original Message -----
>> From: Mark Roddy
>> To: Windows System Software Devs Interest List
>> Sent: Wednesday, December 26, 2007 10:57 AM
>> Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?
>>
>>
>>
>>
>>
>> On Dec 26, 2007 9:22 AM, Alberto Moreira < xxxxx@ieee.org> wrote:
>>
>> I’m sorry, people, I’m going to put on my computer science hat now
>> and
>> say that whatever this is, it ain’t a spinlock. The whole point of a
>> spinlock is to spin without yielding execution!
>>
>> At least provide an accurate definition. " The whole point of a
>> spinlock
>> is to spin without yielding execution! " No that isn’t the whole
>> point. That is a distinct feature. And everything we have discussed
>> here, with the exception of the AIX style ‘spin a while, then sleep’
>> implementation, doesn’t ‘yield execution’. What we have discussed is
>> that on NT, and most other modern multiprocessor general purpose
>> operating systems, spinlocks are interruptible. The currently executing
>> thread does not yield execution, it is interrupted, runs some isr, and
>> then returns to spinning. Implementations of spinlocks could block all
>> interrupts and never allow the processor to do anything other than busy
>> wait for the lock. Such implementations are generally considered
>> deficient as they block management of timers and TLBs and other critical
>> global OS resources while not providing any added benefit. You are of
>> course free to implement this sort of deficient simplistic private
>> spinlock, but I would suggest not deploying this spinlock of yours on
>> general purpose multiprocessor systems.
>>
>>
>>
>>
>>
>> –
>> Mark Roddy
>> — NTDEV is sponsored by OSR For our schedule of WDF, WDM, debugging
>> and other seminars visit: http://www.osr.com/seminars To unsubscribe,
>> visit the List Server section of OSR Online at
>> http://www.osronline.com/page.cfm?name=ListServer
>> —
>> NTDEV is sponsored by OSR
>>
>> For our schedule of WDF, WDM, debugging and other seminars visit:
>> http://www.osr.com/seminars
>>
>> To unsubscribe, visit the List Server section of OSR Online at
>> http://www.osronline.com/page.cfm?name=ListServer
>
>
>
> —
> NTDEV is sponsored by OSR
>
> For our schedule of WDF, WDM, debugging and other seminars visit:
> http://www.osr.com/seminars
>
> To unsubscribe, visit the List Server section of OSR Online at
> http://www.osronline.com/page.cfm?name=ListServer


NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer


Mark Roddy — NTDEV is sponsored by OSR For our schedule of WDF, WDM, debugging and other seminars visit: http://www.osr.com/seminars To unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer

Alberto,

I am afraid all your statements on the subject are just bound to be wrong, because they are based on the totally wrong assumption that is quoted below:

[begin quote]

The test-and-set instruction must be atomic, and the hardware guarantees it.

[end quote]

This is the root of all your errors. Hardware does * NOT* guarantee atomicity of test-and-set in itself - it guarantees atomicity if and only if test-and-set is used with LOCK prefix. As I tried to explain to you already, at the hardware level test-and-set involves modification of 2 operands, i.e. of the target memory location and EFLAGS register. It involves 2 steps:

  1. CF flag in EFLAGS = target bit of the target variable;
  2. Target bit of the target variable=1;

Now imagine what happens if CPU X does step 1, then CPU Y sneaks in, and then CPU X does step 2 - if spinlock is not originally held by anyone, each CPU will believe that it has exclusively acquired a spinlock, so that a spinlock will have 2 holders at once . This scenario may occur if you do test-and-set without LOCK prefix. This is the reason why spinlock acquisition always has to be done as *locked* test-and-set - if the above mention scenario occurs, spinlock is already not an MP-safe construct, is it???

The code
top: test-and-set bit, true
jump-if-not-zero top

is one hundred per cent multiprocessor safe on a bus-based i386 SMP.

I hope by now you already understand that it is NOT MP-safe at all, because you do test-and-set without LOCK prefix…

Anton Bassov