Re: MSI interrupts

In article <8uzEP.115550$Xq5f.66883@fx38.iad>,
EricP  <ThatWouldBeTelling@thevillage.com> wrote:

Dan Cross wrote:

In article <kVgEP.1277108$_N6e.605199@fx17.iad>,
EricP  <ThatWouldBeTelling@thevillage.com> wrote:

Dan Cross wrote:

In article <fe9715fa347144df1e584463375107cf@www.novabbs.org>,
MitchAlsup1 <mitchalsup@aol.com> wrote:

On Thu, 20 Mar 2025 12:44:08 +0000, Dan Cross wrote:

Sometimes you really don't want to be interrupted.

And sometimes you don't want to be interrupted unless the
"house is on fire"; I cannot see a time when "the house is
on fire" that you would not want to take the interrupt.
>
Is there one ?!?

Consider a thread that takes a spinlock; suppose some
high-priority interrupt comes in while the thread is holding
that lock.  In response to the interrupt, software decides to
suspend the thread and switch some other thread; that thread
wants to lock the spin lock that the now-descheduled thread is
holding: a classic deadlock scenario.

>
Terminology: mutexes coordinate mutual exclusion between threads,
spinlocks coordinate mutual exclusion between cpu cores.
Windows "critical sections" are mutexes with a fast path.

 
A spin lock is simply any lock where you spin trying to acquire
the lock, as opposed to a blocking synchronization protocol.
Here I'm using the terminology of Herlihy and Shavit [Her08].

>
I'm using terminology in common use on multiprocessor systems like
VMS since 1980's and later WinNT.
>
Each OS data structure has different reentrancy requirements.
- Ones accessed by threads are guarded by mutexes.
  Example on Windows would be the page tables as paging is done by threads.
- Ones accessed by OS software interrupt level are guarded by spinlocks.
  Example on Windows is the Scheduler tables.
- Ones accessed by HW interrupts are guarded by interrupt spinlocks.
  Example on Windows is device interrupt service routines.

I'm not sure what you're saying here, or rather, how it is
relevant.

Your earlier statement was that "mutexes coordinate mutual
exclusion between threads, spinlocks coordinate mutual exclusion
between cpu cores."  But this is not the case.

Taking VMS as an example, from [Gol94], sec 9.5 (page 255):

|A thread of execution running on one processor acquires a
|spinlock to serialize access to the data with threads of
|execution running on other processors.  Before acquiring
|the spinlock, the thread of executions raises IPL to block
|accesses by other threads of execution running on the same
|processor.  The IPL value is determined by the spinlock being
|locked.

Goldberg and Saravanan seems quite explicit that threads can
acquire and hold spinlocks on OpenVMS, which seems to be
something that you were objecting to?

Turning to Windows, [Rus12] says about spin locks on page 179:

|Testing and acquiring the lock in one instruction prevents a
|second thread from grabbing the lock between the time the first
|thread tests the variable and the time it acquires the lock.

Note that, again, the language here is thread-centric.

By the way, regarding terminology, on page 177 [Rus12] also
says,

|Sections of code that access a nonshareable resource are called
|_critical_ sections.  To ensure correct code, only one thread
|at a time can execute in a critical section.

This is the generic definition of a critical section and note
that this is the context in which we are using the term
throughout this thread.

What you referred to earlier as a "critical section" in Windows
is a _userspace_ synchronization primitive with a kernel assist
and mostly unrelated to concerns around interruptibility.  From
the description on page 201 of [Rus12], they seem similar to
futexes on Linux, though somewhat more limited: Russinovich et
al states that they cannot be used between processes, while a
Linux futex can if it's in a region of memory shared between
cooperating processes.

Traditional Unix "sleep" and "wakeup" are an example of a
blocking protocol, where a thread may "sleep" on some "channel",
yielding the locking thread while the lock cannot be acquired,
presumably scheduling something else until the thread is later
marked runnable by virtual of something else calling "wakeup" on
the sleep channel.
 
But note that I am deliberately simplifying in order to
construct a particular scenario in which a light-weight
synchronization primitive is being used for mutual exclusion
between concurrent entities, hence mentioning spinlocks
specifically.
 
Suggesting that spin locks iare only applicable to
multiprocessing scenarios is flatly incorrect.

>
I didn't.

Your exacty words were, "spinlocks coordinate mutual exclusion
between cpu cores."  See the text quoted above.  This is
incorrect in that it ignores that threads are, in contxt, the
software primitive for the computational entities that are doing
the acquiring, and while the "between cpu core" part is the
usual case, it is not the only case.

I am saying the OS by design guards *ITS* different data structures
with different mechanisms, and those mechanism must only be used in
a very controlled manner. And if you want to do something that requires
access to one of *ITS* data structures then you must obey *ITS* rules.

This is axiomatic.

But I fail to see how it's relevant to the topic at hand.  In
context we're discussing scenarios where a system may want to
disable interrupts entirely, and whether a particular aspect of
a hardware design is sufficient to implement critical sections
generally.

In Windows and VMS and from what I understand of *nix spinlocks guard most
of the core OS data structures with spinlocks acquired at the software
interrupt level. If you are not at that level then the spinlock will not
provide the necessary synchronization for access to that data.

Precisely.

Software may use
the technique to spin on a "busy" bit on some IP in a device for
example, even on a uniprocessor system.
 

A valid response here might be, "don't context switch from the
interrupt handler; use a DPC instead".  That may be valid, but
it puts a constraint on the software designer that may be onerus
in practice: suppose the interrupt happens in the scheduler,
while examining a run queue or something.  A DPC object must be
available, etc.

That is exactly what DPC/SoftIrq are design to do - allow the bulk of
the kernel, like the scheduler, non-paged heap management, IO pre and
post processing, to be interrupted without causing reentrancy.
The higher level device interrupt enqueues a request to the lower software
interrupt level, which is processed when it will not cause reentrancy.
>
That constraint is by design and any good OS will crash if violated.

 
Yes, I'm aware of the technique.  That wasn't the point.
 

Further, software must now consider the complexity of
potentially interruptable critical sections.  From the
standpoint of reasoning about already-complex concurrency issues
it's simpler to be able to assert that (almost) all interrupt
delivery can be cheaply disabled entirely, save for very
special, specific, scenarios like NMIs.  Potentially switching
away from a thread holding a spinlock sort of defeats the
purpose of a spinlock in the first place, which is a mutex
primitive designed to avoid the overhead of switching.

(It occurs to me that perhaps this is why you are going on about
how VMS and windows uses spin locks, and how they interact with
interrupt priority levels.)

This is why I mentioned the terminology thing: threads do not hold
spinlocks, they hold mutexes.

 
See above.  Threads can certainly "hold" a spin lock, as they
can hold any kind of lock.  To quote from sec 7.6.1 of [Val96],
page 202:

>
When a particular OS defined spinlock is used to guard a particular OS
defined data structure, exactly WHEN the OS allows this decides how
the OS avoids all the nasty interrupt pitfalls you identified.

How is this relevant to what you wrote earlier and my response,
quoted just above?  My statement was that threads can hold spin
locks.  This is obviously true.

|On a uniprocessor, if a thread tries to acquire a spin lock
|that is already held, it will loop forever.  Multiprocessor
|algorithms, however, must operate correctly regardless of the
|number of processors, which means that they should handle the
|uniprocessor case as well.  This requires strict adherence to
|the rule that threads not relinquish control of the CPU while
|holding a spin lock.

>
Yes, which is what I was saying.
I am describing HOW that is accomplished inside an OS.

Why?  First, it's well-known, and second, that's not relevant to
the discussion at hand.

But it also doesn't seem like that's what you're saying; you
asserted that a thread (a software thread in this context) does
not "hold" a spin lock; that's incorrect.

The way you prevent a thread from relinquishing control while holding a
spinlock is to first switch hats from thread level to software interrupt
level, which blocks the scheduler because it also runs at SWIL,
then acquire the spinlock.
>
Raising the interrupt priority level from passive (aka thread) level
to SWI level (called dispatch level on Windows) blocks the thread switch.
This ensures non-reentrant algorithms are serialized.
The core may then acquire spinlocks guarding data structures.

Just so.  Earlier you said that threads cannot hold spin locks;
in the text quoted just above, you said that they do.

As for this specific scenario of specific interrupt priority
levels, I would go further and say that is just a detail.  In
the simplest systems, ie, the kind we might reach for as an
expository example when discussing these kinds of issues, one
just disables interrupts completely when holding a spinlock.

Threads and mutexes are a fiction created
by the OS scheduler, and switching threads while waiting for a mutex
is exactly what they are supposed to do.
>
Spinlocks are used by cores to coordinate access to shared memory by
things like a OS scheduler looking at list of threads waiting for a mutex.

 
Spinlocks, of the form I was describing, are an optimization for
cases where the critical section guarded by the lock is short,
and the overhead of invoking a scheduler and context switching
to some other thread is higher than just spinning until the lock
becomes available again.  The whole point is to avoid blocking
and switching.
 
E.g., as [Vaj11] puts it (page 98):
 
|Spin locks have the advantage of preventing pre-emption by the
|OS (due to blocking while waiting for the lock)
 
That is, the advantage is because the thread does not block and
yield.

>
And I am describing HOW the OS accomplishes this.

Well, what you are describing is how _a_ specific family of
operating systems that you are familiar with accomplishes this,
and that's all well and good, but it's not all that relevant to
discussing the pitfalls of this "ATOMIC event" proposal or
addressing the OP's questions about scenarios in which interrupt
disable is used.

Disabling the scheduler is the same as raising the priority to SWI level.
Once the scheduler is disabled THEN you may acquire a spinlock
that guards a shared data structure accessed at SWI level.
>
But you may NOT access a shared data structure accessed at interrupt level.
For that you'd need an interrupt spinlock acquired at the device ISR
priority interrupt level. And note that the ISR interrupt priority level
is assigned by the OS itself, usually when the device is mounted.

You are presuming a very specific system architecture and going
into great detail about its implementation.  That's fine, and
perhaps useful I suppose, but again, I don't think it's very
relevant to the context of this discussion.

I like to think of it as all having to do with hats.
The cpu is wearing one of three hats: a thread hat when it pretends to be
a time shared execution machine; a core hat when it acts as a single
execution machine running non-reentrant things like a scheduler which
creates the fiction of threads and processes (multiple virtual spaces);
and an interrupt hat when executing nestable reentrant interrupts.
>
The interrupt mechanism coordinates exactly when and how we switch hats.

 
I suppose you are lumping system calls into the overall bucket
of "interrupts" in this model, regardless of whether one might
use a dedicated supervisor call instruction (e.g., something
like x86 SYSENTER or SYSCALL or ARM SVC or RISC-V's ECALL)?

>
Syscall switches a thread from user mode to supervisor mode.

Your statement was that "the interrupt mechanism coordinates
exactly when and how we switch hats".  But that's incomplete; if
a system call blocks, for example, the typical behavior is to
yield to the scheduler to pick something else to do.  Clearly,
that is another way that coordinates this business of changing
one's hat.

The hat analogy feels strained to me, and too colloquial to be
useful.

>
I offered it because it answers your prior questions about how
OS avoid the kinds of deadlocks and race conditions you described.

I'm afraid you answered a question that I did not ask, then.

I am discussing the specifics of this architectural proposal,
and specifically two aspects of it: one is addressing the
proposer's questions about scenarios where one might want to
disable interrupts entirely.

Another, which has emerged somewhat more recently in the thread,
is this mechanism which seems to be a semi-transactional
elaboration of LL-SC primitives.

Any questions I did ask were Socratic in nature, and in the
context of these architectural discussions.  I did not ask any
questions about basic design or implementation of
synchronization primitives.

- Dan C.

References:

[Gol94] Ruth E. Goldberg and Saro Saravanan. 1994. _OpenVMS AXP
Internals and Data Structures_ (Vers. 1.5). Digital Press,
Newton, MA.

[Rus12] Mark Russinovich, David A. Solomon and Alex Ionescu.
2012. _Windows Internals: Part 1_. Microsoft Press, Redmond, WA.