Are callbacks guaranteed to run consecutively?

NTDEV
41

The term “block” refers to the ability of the OS Dispatcher, when so
instructed by a control construct to stop the progress of a thread until it
is released by the control construct. By the very definition of the term, a
“blocked” thread is waiting for a control construct to happen. Note that
blocking isn’t the only way a thread can stop making progress: for example,
it can also be context-switched at the time-slice tick, or it can just spin
on a memory location, or the OS can just decide to preempt it every time the
thread crosses the user-kernel boundary.

“Blocked” refers to a thread not making progress because of a
synchronization construct. A thread can be suspended without being blocked,
and it can stop making progress without being context-switched.

At the application level, however, things are less clear. A blocking request
will block the thread, but there’s no guarantee that a non-blocking request
will return control to the thread presto and pronto. An OS may take the
chance of a non-blocking request to context-switch the thread out and
requeue it at the tail of its dispatch queue, and if that thread has the
unhappy fate of finding itself behind one or more higher priority compute
bound threads, it will be de-facto suspended - not blocked - until the
weather improves. Unless you’re running in a Real-Time Executive, there is
no guarantee that your thread will get control immediately after a call.

Now, if kernel-side code cannot be preempted by the OS, indeed the only way
such thread can be context-switched is if the thread itself yields control.
A spinlock, strictly speaking, does not block: it spins, de-facto preventing
the progress of the thread. While we normally say “block” when we refer to
actions taken by the dispatcher, a spinlock is really a block, although it
stops not only the thread’s progress but also that CPU’s progress. Now, an
OS can decide to allow preemption of a spinlock, but when it does that, it
is in fact blocking that thread!

I believe that the good policy is, do not, ever, expect determinism in the
sequence of OS-level events. It won’t happen.

About multiprocessors 40 years ago, my memory is going, but I remember that
a 3x2 configuration (three central processors and two i/o processors) for
the Univac 1108 was already available in 1968. I know that because that’s
the year I graduated, and I immediately joined Sperry Univac after college:
on the first day of my job my boss dumped a pile of Univac 1108 technical
manuals on my desk, “learn it!”. And I do not remember it any longer, but I
believe the Univac 490, which was designed by Seymour Cray when he was at
Univac, had two processors, and it predated the 1108.

Alberto.

----- Original Message -----
From: “Maxim S. Shatskih”
Newsgroups: ntdev
To: “Windows System Software Devs Interest List”
Sent: Monday, December 24, 2007 6:06 AM
Subject: Re:[ntdev] Are callbacks guaranteed to run consecutively?

>> Interesting definition of ‘blocking’ that I think doesn’t match the
>> common
>> English usage.
>
> It matches the UNIX usage, Anton was correct in this.
>
> The UNIX usage was developed due to non-preemptive nature of the kernel of
> most
> UNIXen, where “blocking” (dispatcher-implemented waiting) is the only way
> to
> switch the current thread while executing the kernel code.
>
> –
> Maxim Shatskih, Windows DDK MVP
> StorageCraft Corporation
> xxxxx@storagecraft.com
> http://www.storagecraft.com
>
>
> —
> 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

42

A “spinlock” is a busy-waiting loop. If a thread is spinning on a lock, it’s spinning on the lock: the only way the thread can progress is if the lock is cleared. That thread is not blocked, uh ? But if we’re talking about a synchronization construct, and that should include a spinlock, a thread shouldn’t be able to block on that synchronization construct and be allowed to make progress before the lock is cleared.

It should take another thread to clear a spinlock. If a thread can spin on a spinlock and yet be free to make additional progress and clear its own spinlock, that’s not a spinlock as I understand it. There’s no contract here, just a memory location that can be set or clear. I also take a little exception to the concept of “owning” a spinlock: by definition, such a lock is a lowest-level subarchitectural construct, that has no “owner” as such. For example, a spinlock should be clearable from an I/O peripheral through DMA, and if a thread owns a spinlock and no other thread can access that lock, I’d call it a “deadlock” or a “livelock”, not a spinlock.

I don’t know what “acquiring” a spinlock means, but when a thread is spinning on a lock, it shouldn’t be able to do anything else until the lock is cleared, necessarily by another thread. If a thread can spin on a lock, then happily leave the lock and go shopping, and then reset its own lock, well, I cannot call it a “lock” any longer!

About “block”, the term usually means to be suspended by the dispatcher due to waiting on a control construct. Threads block on such things as a semaphore, a mutex, an event. A spinlock, by its very nature, is independent of the dispatcher - or I cannot call it “spinlock” any longer. Therefore, a thread doesn’t “block” on a spinlock, it just ceases to make progress. A spinlock is a construct that operates on processors, not on threads!

Alberto.

----- Original Message -----
From: Mark Roddy
To: Windows System Software Devs Interest List
Sent: Sunday, December 23, 2007 3:18 PM
Subject: Re: Re:[ntdev] Are callbacks guaranteed to run consecutively?

Maybe we are having a terminology problem. “Should” does not mean “can’t”. Spinlocks are software constructs. It is up to the implementation to decide if, for example, it is going to refuse to honor a release request from anyone except the current thread owner. The spinlock implementation in NT does not enforce such a rule, consequently you can release a spinlock from a non-owning thread. That does not mean that you should do that, it means that you can do that but that doing so violates the contract, just as modifying the object covered by the spinlock without holding that spinlock violates the contract. An assertion was made that one can’t release a spinlock this way, that assertion is wrong.

“a protocol that users of the mechanism have to adhere to” has approximately the same meaning to me as “a contract”, so I fail to see any real difference here.

Finally, another assertion was made (not by you) that one cannot block after acquiring a spinlock. This is of course not true at all. A spinlock owning thread is free to acquire another spinlock and will of course block waiting for the current owner of that lock to release it. Once again perhaps we all are just having a terminology problem, and that ‘block’ meant ‘wait on an event’ in the poster’s terminology.

On Dec 23, 2007 2:11 AM, Alberto Moreira wrote:

I’m not sure I follow you guys. If thread A grabs a lock, no other thread
should be able to release it, or it’s not really a lock. But then, as you
yourself have pointed out, the IRQL implementation is far from a
straightfoward interrupt management, so, hey, everything’s possible.

Synchronization constructs shouldn’t be regarded as contracts: they’re
engines that should have highly predictable behavior. It’s the usage of
synchronization constructs that may be regarded as a contract, and even
then, the better the synchronization construct the less one has to treat it
as a contract. For example, if I have a self-synchronizing object or data
structure - also called a “Monitor” in computer science parlance - accesses
to its data are synchronized as a matter of fact, by the object itself,
contract or no contract. The mutual exclusion is enforced by the data
itself, not by the users of the data. And that can permeate all the way to
the language level, if you doubt it I invite you to read the Concurrent
Pascal language spec.

On the other hand, if you have a simple-minded construct such as a mutex or
even a semaphore, there’s a protocol that users of the mechanism have to
adhere to, otherwise synchronization is not going to work. But jot this one
down to the weakness of the mechanism, not on the fact that its usage might
or not require something like a “contract” among threads.

As far as the OS goes, its duty is to implement the mechanism so that users
can take advantage of it. I do not thing it’s an OS call to tell users what
they can or cannot do, as long as applications use the mechanism through the
OS’s published APIs. It is also not the OS’s call to tell drivers what they
will or will not do with well published and well specified synchronization
mechanisms, again, as long as drivers respect the API and use it properly.
And, in a well designed OS drivers sit between the hardware and the OS.
Hardware should be driven by drivers, not by the OS, and IMHO the OS has no
business sitting between a driver and its hardware. OS’s aren’t the owners
of the machine - they’re a service layer. An OS isn’t a ruler or a
president, but a public servant that is at all times at the command of its
users.

If you want to shield the OS from driver problems you should begin by
running them in different protection rings. I find it mind boggling that
even though the i386 architecture implements such a large array of security
oriented features, the OS uses none of them, all under the excuse of being
compatible with machines that do not have nearly a fraction of that
functionality. Go figure!

Alberto.

----- Original Message -----
From: “Don Burn”
Newsgroups: ntdev
To: “Windows System Software Devs Interest List” < xxxxx@lists.osr.com>
Sent: Saturday, December 22, 2007 6:10 PM
Subject: Re:[ntdev] Are callbacks guaranteed to run consecutively?

> As Mark Roddy pointed out, a thread on a second processor could release
> the lock. You seem to be thinking uni-processoor which shows a great gap
> in thinking about synchronization. By the way, there have been many
> spin-lock implementations that do not block scheduling, many of them test
> the spinlock n times, and if they do not get it yield. As far as IRQL
> remember this is a Windows (and I think VMS concept), it is definitely not
> a generic OS concept.
>
> Every synchronization mechanism is a contract, if you violate the contract
> you fail. Saying something is not a sync mechanism just because you don’t
> like the contract, is just garbage tha same as saying that the OS does not
> have the right to dictate what your driver can do. Perhaps you can get
> away with it some time, but sooner or later people catch on to bad code,
> or stupid claims.
>
>
> –
> Don Burn (MVP, Windows DDK)
> Windows 2k/XP/2k3 Filesystem and Driver Consulting
> Website: http://www.windrvr.com
> Blog: http://msmvps.com/blogs/WinDrvr
> Remove StopSpam to reply
>
>
>
> wrote in message news:xxxxx@ntdev…
>> Don,
>>
>>> By your definition SPINLOCKS do not nessecarily synchronize, since one
>>> thread can
>>> decide to release a spinlock that another took,
>>
>> How on Earth may something like that possibly happen??? If thread X
>> takes a spinlock, no other thread should have a chance to run on a given
>> CPU until spinlock gets released. This is why spinlock holders always run
>> at elevated IRQL. This is not just some implementation feature, but,
>> instead, just a conceptual thing - if context switches were possible
>> while spinlock is being held, it would make the very concept of a
>> spinlock unworkable…
>>
>>
>>> Callbacks have been a synchronization mechanism long before windows.
>>
>> …but only on uniprocessor systems (that were prevalent at the time)
>>
>> 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

—
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

43

> I don’t know what “acquiring” a spinlock means,

It means everything you do *BEFORE* your test-and-set is successful (including test-and-set itself). This is acquisition process. From the moment your test-and-set is successful, you are already is spinlock holder…

but when a thread is spinning on a lock, it shouldn’t be able to do anything
else until the lock is cleared

Not necessarily. For example, KeAcquireSpinlock() could be implemented the following way:

  1. Save current IRQL in a local variable
  2. If IRQL < DPC level, raise IRQL to DPC level
  3. Do locked test-and-set. If it is successful, return success
  4. If the original IRQL that we have earlier saved in a local variable == DPC level, go to (8)
  5. Restore IRQL
  6. Yield execution
  7. Go to (2)
  8. Poll the spinlock variable in a busy loop until it is clear
  9. Go to (3)

This implementation is fully consistent with the idea that if caller’s IRQL is below DPC level,
a call to KeAcquireSpinlock() in a client code and write to TPR in KeAcquireSpinlock()'s actual implementation do not necessarily run in an atomic context, so that a subtle context switch in between these two is still possible…

Anton Bassov

44

That is more or less the AIX implementation of spinlocks I mentioned
previously. Note that the NT implementation, as it does not prevent
interrupts in the acquiring thread or owning thread, also allows the thread
in lock acquisition mode to be doing something other than spinning, i.e. it
can be running some isr for a while.

On Dec 24, 2007 11:48 PM, wrote:

> > I don’t know what “acquiring” a spinlock means,
>
> It means everything you do BEFORE your test-and-set is successful
> (including test-and-set itself). This is acquisition process. From the
> moment your test-and-set is successful, you are already is spinlock
> holder…
>
> > but when a thread is spinning on a lock, it shouldn’t be able to do
> anything
> > else until the lock is cleared
>
> Not necessarily. For example, KeAcquireSpinlock() could be implemented the
> following way:
>
> 1. Save current IRQL in a local variable
> 2. If IRQL < DPC level, raise IRQL to DPC level
> 3. Do locked test-and-set. If it is successful, return success
> 4. If the original IRQL that we have earlier saved in a local variable ==
> DPC level, go to (8)
> 5. Restore IRQL
> 6. Yield execution
> 7. Go to (2)
> 8. Poll the spinlock variable in a busy loop until it is clear
> 9. Go to (3)
>
> This implementation is fully consistent with the idea that if caller’s
> IRQL is below DPC level,
> a call to KeAcquireSpinlock() in a client code and write to TPR in
> KeAcquireSpinlock()'s actual implementation do not necessarily run in an
> atomic context, so that a subtle context switch in between these two is
> still possible…
>
> 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
>

–
Mark Roddy

45

> Note that the NT implementation, as it does not prevent interrupts in the

acquiring thread or owning thread, also allows the thread in lock acquisition mode
to be doing something other than spinning,

Well, the above applies not only to spinlock acquisition - once a holder of a “conventional”
spinlock runs at DPC level, it can be interrupted. However, when it comes to interrupt spinlock, it gets acquired at DIRQL. In addition to the above, there are also spinlocks that disable all device interrupts (they are reserved for the internal OS use) by raising IRQL to SYNCH level. They come in 2 flavours. i.e. KeAcquireSpinlockAtSynchLevel() and KeAcquireSpinlockRaiseToSynch() - the former cannot get interrupted while either acquiring a spinlock or holding it, and the latter can get interrupted while acquiring a spinlock but not while holding it…

Anton Bassov

46

Actually, the former I’ve never heard of and is not in the source tree for
Windows and the latter has been documented as being worthless see
http://www.osronline.com/article.cfm?article=146

–
Don Burn (MVP, Windows DDK)
Windows 2k/XP/2k3 Filesystem and Driver Consulting
Website: http://www.windrvr.com
Blog: http://msmvps.com/blogs/WinDrvr
Remove StopSpam to reply

wrote in message news:xxxxx@ntdev…
>> Note that the NT implementation, as it does not prevent interrupts in the
>> acquiring thread or owning thread, also allows the thread in lock
>> acquisition mode
>> to be doing something other than spinning,
>
> Well, the above applies not only to spinlock acquisition - once a holder
> of a “conventional”
> spinlock runs at DPC level, it can be interrupted. However, when it
> comes to interrupt spinlock, it gets acquired at DIRQL. In addition to the
> above, there are also spinlocks that disable all device interrupts (they
> are reserved for the internal OS use) by raising IRQL to SYNCH level. They
> come in 2 flavours. i.e. KeAcquireSpinlockAtSynchLevel() and
> KeAcquireSpinlockRaiseToSynch() - the former cannot get interrupted while
> either acquiring a spinlock or holding it, and the latter can get
> interrupted while acquiring a spinlock but not while holding it…
>
> Anton Bassov
>

47

Neither DIRQL not SYNC_LEVEL block all interrupts. DIRQL is a placeholder
for ‘your driver’s interrupt level’ and is interruptable by all driver
interrupt levels higher than yours, plus the profile, clock, and IPI levels
used by the OS. SYNC_LEVEL blocks profile interrupts but allows timer and
IPI interrupts.

I agree that this applies to both acquiring threads and lock holding
threads. The point being that while conceptually it is convenient to think
of spinlock acquisition as a continuous busy wait, and of spinlock holders
as executing continuously until they release their held lock, the actual
details are quite different. Further, this illustrates why the combining of
interrupt levels and spinlocks in NT is simply a feature of NT’s
implementation of spinlocks, and not some inherent quality of the spinlock
concept.

On Dec 25, 2007 3:52 PM, wrote:

> > Note that the NT implementation, as it does not prevent interrupts in
> the
> > acquiring thread or owning thread, also allows the thread in lock
> acquisition mode
> > to be doing something other than spinning,
>
> Well, the above applies not only to spinlock acquisition - once a holder
> of a “conventional”
> spinlock runs at DPC level, it can be interrupted. However, when it
> comes to interrupt spinlock, it gets acquired at DIRQL. In addition to the
> above, there are also spinlocks that disable all device interrupts (they are
> reserved for the internal OS use) by raising IRQL to SYNCH level. They come
> in 2 flavours. i.e. KeAcquireSpinlockAtSynchLevel() and
> KeAcquireSpinlockRaiseToSynch() - the former cannot get interrupted while
> either acquiring a spinlock or holding it, and the latter can get
> interrupted while acquiring a spinlock but not while holding it…
>
> 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
>

–
Mark Roddy

48

> Actually, the former I’ve never heard of and is not in the source tree for Windows

Let me double-check it - as far as I remember, there are 2 types of spinlock acquisition that are related to SYNCH_LEVEL. However, I may be wrong here, so let me check it again - maybe it is just my ill imagination…

the latter has been documented as being worthless
see http://www.osronline.com/article.cfm?article=146

Well, it is not worthless in itself, but we are *explicitly* told by WDK documentation not to use it,
because it is reserved for the OS use only…

Anton Bassov

49

> Neither DIRQL not SYNC_LEVEL block all interrupts

Sure - DIRQL blocks only interrupts of lower priority, and SYNCH blocks all *device* interrupts - CPU still receives IP and timer interrupts at IRQL==SYNCH_LEVEL…

Anton Bassov

50

Well since you can’t rely on it since SYNCH_LEVEL can be DISPATCH_LEVEL it
isn’t real useful.

–
Don Burn (MVP, Windows DDK)
Windows 2k/XP/2k3 Filesystem and Driver Consulting
Website: http://www.windrvr.com
Blog: http://msmvps.com/blogs/WinDrvr
Remove StopSpam to reply

wrote in message news:xxxxx@ntdev…
>> Actually, the former I’ve never heard of and is not in the source tree
>> for Windows
>
> Let me double-check it - as far as I remember, there are 2 types of
> spinlock acquisition that are related to SYNCH_LEVEL. However, I may be
> wrong here, so let me check it again - maybe it is just my ill
> imagination…
>
>> the latter has been documented as being worthless
>> see http://www.osronline.com/article.cfm?article=146
>
> Well, it is not worthless in itself, but we are explicitly told by WDK
> documentation not to use it,
> because it is reserved for the OS use only…
>
> Anton Bassov
>

51

SYNC_LEVEL is defined only for x64 platforms in the WDK include files, but
conceptually what SYNC_LEVEL is has always existed in NT: the lowest IRQL my
thread needs to execute at to guarantee that it will not be interrupted by
device driver interrupts. This ends up being an interesting interrupt level
in some cases, distinct from HIGH_LEVEL which raising your thread to has
unfortunate effects on important OS activities.

On Dec 25, 2007 6:06 PM, wrote:

> > Actually, the former I’ve never heard of and is not in the source tree
> for Windows
>
> Let me double-check it - as far as I remember, there are 2 types of
> spinlock acquisition that are related to SYNCH_LEVEL. However, I may be
> wrong here, so let me check it again - maybe it is just my ill
> imagination…
>
> > the latter has been documented as being worthless
> > see http://www.osronline.com/article.cfm?article=146
>
> Well, it is not worthless in itself, but we are explicitly told by WDK
> documentation not to use it,
> because it is reserved for the OS use only…
>
> 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
>

–
Mark Roddy

52

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! Because a spinlock is the weapon of last resource, and it doesn’t know about threads or processes. It only knows about processors. You don’t spin a thread, you spin a processor!

Say you want to implement a multiprocessor safe synchronization construct, such as a mutex or a semaphore. At some point in time, deep down inside the construct, you’re going to need to keep two processors away from each other. You have already dealt with IRQLs, yielding execution, DPCs and what not: you’re down at the bare bottom of the heap, dealing directly with the iron. At this level, there are no threads, no processes, no interrupts: there are only processors and a system bus. At that level, a safe way to keep a piece of shared memory whole is to spin a processor on a lock until the lock’s available.

Spinlocks aren’t thread level constructs! They’re processor level constructs. You know, this whole discussion reinforces my belief that when I want a real spinlock, I can’t rely on the OS: I must spin my own lock.

Alberto.

----- Original Message -----
From: Mark Roddy
To: Windows System Software Devs Interest List
Sent: Tuesday, December 25, 2007 3:26 PM
Subject: Re: [ntdev] Are callbacks guaranteed to run consecutively?

That is more or less the AIX implementation of spinlocks I mentioned previously. Note that the NT implementation, as it does not prevent interrupts in the acquiring thread or owning thread, also allows the thread in lock acquisition mode to be doing something other than spinning, i.e. it can be running some isr for a while.

On Dec 24, 2007 11:48 PM, wrote:

> I don’t know what “acquiring” a spinlock means,

It means everything you do BEFORE your test-and-set is successful (including test-and-set itself). This is acquisition process. From the moment your test-and-set is successful, you are already is spinlock holder…

> but when a thread is spinning on a lock, it shouldn’t be able to do anything
> else until the lock is cleared

Not necessarily. For example, KeAcquireSpinlock() could be implemented the following way:

1. Save current IRQL in a local variable
2. If IRQL < DPC level, raise IRQL to DPC level
3. Do locked test-and-set. If it is successful, return success
4. If the original IRQL that we have earlier saved in a local variable == DPC level, go to (8)
5. Restore IRQL
6. Yield execution
7. Go to (2)
8. Poll the spinlock variable in a busy loop until it is clear
9. Go to (3)

This implementation is fully consistent with the idea that if caller’s IRQL is below DPC level,
a call to KeAcquireSpinlock() in a client code and write to TPR in KeAcquireSpinlock()'s actual implementation do not necessarily run in an atomic context, so that a subtle context switch in between these two is still possible…

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

–
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

53

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
>

54

> The whole point of a spinlock is to spin *without* yielding execution!

Wrong!!! The whole point of a spinlock is to provide MP-safe synchronization for a code that has to be executed atomically (for the purpose of this discussion I assume “atomically” means just without yielding execution, although it may mean with blocked interrupts as well - it depends on context in which spinlock is used). Although the code that requests access to the target critical region *MAY* be already running in an atomic context (for example, in DPC) at the time it approaches the critical region, it does not necessarily imply that it always does. If it does, than, indeed, it has no option, other than spinning until test-and-set is successful. However, if it does not, it can yield execution prior to having performed successful test-and-set without a slightest problem - it is not going to make other CPUs wait for itself until it performs test-and-set successfully, so it can do whatever it likes …

Anton Bassov

55

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

56

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.
On Dec 27, 2007 5: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
>

–
Mark Roddy

57

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
>

58

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

59

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.

60

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