On Sun, 16 Mar 2025 21:35:29 +0000, Robert Finch wrote:

On 2025-03-15 6:28 p.m., MitchAlsup1 wrote:

On Sat, 15 Mar 2025 20:46:41 +0000, Robert Finch wrote:

On 2025-03-15 1:46 p.m., MitchAlsup1 wrote:

On Sat, 15 Mar 2025 2:10:48 +0000, Robert Finch wrote:

------------

The SoC system is limited to 64 CPU cores by the use of a 6-bit core
number. So, a 64-bit vector containing which cores to send the interrupt >>> to could be used. A find-first-one responding could be used to mask
things so that only one CPU sees the interrupt.

Consider that you have a pool of 4 cores setup to receive interrupts.
That those 4 cores are running at differing priorities and the interrupt
is at a still different priority. You want the core operating at the
lowest
priority (with the right software stack) to accept the interrupt !!

Okay, I wrote a naive hardware filter for this which should work okay
for small numbers of CPUs but does not scale up very well.
What happens if there is no core ready? Place the IRQ back into the
queue (regenerate the IRQ as an IRQ miss IRQ)? Or just wait for an
available core. I do not like the idea of waiting as it could stall the system.

I can't talk about this for another week or so.

To identify the CPU pool, with a max of 63 CPU per interrupt controller,

Terminology:: My 66000 has 1 interrupt controller (per chip) that can
process MSI-X messages for an unbounded number of interrupt tables and
an unbounded number of cores. Each interrupt table is associated with a
Guest OS (VM) or HyprrVisor (VMM) or ...

The only limitation is the size of the interrupt aperture--

OH, and BTW, I use the word aperture rather than range as the range
may be sparse with unbounded number of holes of unbounded length in
the range {begin..end}. And the service port only services things
in the aperture not in necessarily the range.

the pool could be represented directly as a 64-bit word in the interrupt vector table. I have been thinking of using a 256-bit vector entry
instead of 128-bits. I allocated 96-bit for an instruction / address
field.

I think you are drifting towards "affinity" (and a flat version of that itself). Not a wrong way to go, but fraught with peril.

You might be better off heading into a vector of 64-bit containers
which specify participation in one or more affinity groups per core.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Sun, 23 Mar 2025 16:16:16 +0000, EricP wrote:

MitchAlsup1 wrote:

On Thu, 20 Mar 2025 12:50:09 +0000, Dan Cross wrote:

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

But let me turn it around, what real-world problem does this
interrupt prioritization scheme solve coupled with the inability
to disable interrupts solve?

The OS does not have to "walk" its schedule queues in order to
context switch.

The SVR (SuperVisor Return) instruction checks the priority of
the thread that had been interrupted, and if it is of lower
priority than what is pending in the interrupt table, the
one on the interrupt table receives control while the lower
priority thread remains interrupted.

Thus, the return path from an ISR, just does an SVR. If a
DPC/softIRQ has been setup, or another interrupt has become
pending, HW chooses the path--acting as if HW returned control
to the interrupted thread, and then immediately took the inter-
rupt of highest priority still pending--without having executed
a single instruction in the interrupted thread.

Is anyone complaining that the
ability to disable interrupts is somehow a serious burden?

This thread started with the notion of MSI interrupts and the
inherent need to DI upon arrival at ISR dispatcher. This sub-
thread is investigating whether one can perform ISRs without
disabling interrupts. Thus, making IDisablement an unnecessary
part of interrupt servicing itself.

Your (and EricP)'s contribution is to annotate those instances
where one can arrive at an ISR IE and still want/need to DI and EI
independent of the control transfer from and back to interrupted
thread (even if control arrives reentrantly from interrupted thread).

Supervisor return, whatever it is called - sysret, rei, svr -
is traditionally another point where a number of OS race conditions
can force it to briefly disable interrupts.

The classic case is when a DPC/SoftIrq may be posted by an Interrupt
Service Routine (ISR) and causes the First Level Interrupt Handler
(FLIH),
which is the ISR nested first on the stack of priority interrupts,
to exit into the OS rather than return to its prior thread.

The race condition occurs between the point when the FLIH ISR epilogue
checks for pending a pending DPC, and not finding one decides to return
to the prior thread. Between that check and the SVR instruction a higher priority interrupt occurs and posts a DPC.

I remove that race condition by removing the need for FLIR (which I
call the dispatcher) to check. All the checks are done AT* the SVR
instruction. (*) and during

Another race condition can be how does an epilogue know if it is a FLIH
or nested one? A counter for each core incremented by the ISR prologue
and checked by the epilogue would do but what if the nested interrupt
catches a lower level prologue just before it increments the counter.

How to know:: It COULD look at the value in its stack pointer. An
empty stack implies it is leaving, a non-empty stack implies it
has more to do.

But in practice, it does not need to know as interrupts are properly
nested and serviced in priority order.

There are a number of non-interruptible checks and control flag changes
that supervisor return must perform.

To do this I have a single instruction CSVR Conditional Supervisor
Return
which handles all interrupt, exception, and SysCall returns. It performs
a model specific test on an interrupt control register and if True
changes
the ICR state and returns to the prior context. If False makes other ICR state changes and falls through the CSVR instruction where code can
determine what just changed. This would typically be a jump into the OS Dispatcher to flush any DPC/SoftIrq and check for thread rescheduling.
This whole return sequence is performed without having to disable
interrupts.

I, too, have a single instruction (SVR) that delivers control to the
highest priority still pending thread, regardless of whether it is
a new interrupt, a scheduled DPC/softIRQ, a local timer, an IPI, or
the thread the interrupt stack was placed upon.

SVR looks at the priority of the thread to receive control, and the
priorities of pending 'interrupts' (of which DPC/softIRQ and IPIs
are part) and transfers control to the highest priority pending thread--occasionally that thread is the interrupted one.

Should a higher priority thread become pending while SVR is in progress,
the higher priority thread will receive control before the first inst-
ruction of the mis-receiving thread is performed.

As far as you have explained these things to me, I see no race
conditions
in the architected means.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

MitchAlsup1 wrote:

On Thu, 20 Mar 2025 12:50:09 +0000, Dan Cross wrote:

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

But let me turn it around, what real-world problem does this
interrupt prioritization scheme solve coupled with the inability
to disable interrupts solve?

The OS does not have to "walk" its schedule queues in order to
context switch.

The SVR (SuperVisor Return) instruction checks the priority of
the thread that had been interrupted, and if it is of lower
priority than what is pending in the interrupt table, the
one on the interrupt table receives control while the lower
priority thread remains interrupted.

Thus, the return path from an ISR, just does an SVR. If a
DPC/softIRQ has been setup, or another interrupt has become
pending, HW chooses the path--acting as if HW returned control
to the interrupted thread, and then immediately took the inter-
rupt of highest priority still pending--without having executed
a single instruction in the interrupted thread.

Is anyone complaining that the
ability to disable interrupts is somehow a serious burden?

This thread started with the notion of MSI interrupts and the
inherent need to DI upon arrival at ISR dispatcher. This sub-
thread is investigating whether one can perform ISRs without
disabling interrupts. Thus, making IDisablement an unnecessary
part of interrupt servicing itself.

Your (and EricP)'s contribution is to annotate those instances
where one can arrive at an ISR IE and still want/need to DI and EI independent of the control transfer from and back to interrupted
thread (even if control arrives reentrantly from interrupted thread).

Supervisor return, whatever it is called - sysret, rei, svr -
is traditionally another point where a number of OS race conditions
can force it to briefly disable interrupts.

The classic case is when a DPC/SoftIrq may be posted by an Interrupt
Service Routine (ISR) and causes the First Level Interrupt Handler (FLIH), which is the ISR nested first on the stack of priority interrupts,
to exit into the OS rather than return to its prior thread.

The race condition occurs between the point when the FLIH ISR epilogue
checks for pending a pending DPC, and not finding one decides to return
to the prior thread. Between that check and the SVR instruction a higher priority interrupt occurs and posts a DPC.

Another race condition can be how does an epilogue know if it is a FLIH
or nested one? A counter for each core incremented by the ISR prologue
and checked by the epilogue would do but what if the nested interrupt
catches a lower level prologue just before it increments the counter.

There are a number of non-interruptible checks and control flag changes
that supervisor return must perform.

To do this I have a single instruction CSVR Conditional Supervisor Return
which handles all interrupt, exception, and SysCall returns. It performs
a model specific test on an interrupt control register and if True changes
the ICR state and returns to the prior context. If False makes other ICR
state changes and falls through the CSVR instruction where code can
determine what just changed. This would typically be a jump into the OS Dispatcher to flush any DPC/SoftIrq and check for thread rescheduling.
This whole return sequence is performed without having to disable interrupts.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Robert Finch <robfi680@gmail.com> writes:

<please trim posts>

Consider that you have a pool of 4 cores setup to receive interrupts.
That those 4 cores are running at differing priorities and the interrupt
is at a still different priority. You want the core operating at the
lowest
priority (with the right software stack) to accept the interrupt !!

Okay, I wrote a naive hardware filter for this which should work okay
for small numbers of CPUs but does not scale up very well.
What happens if there is no core ready? Place the IRQ back into the
queue (regenerate the IRQ as an IRQ miss IRQ)? Or just wait for an
available core. I do not like the idea of waiting as it could stall the >system.

Use a fifo to hold up to N pending IRQ. Define a signal that asserts when
the fifo is non-empty. The CPU can mask the signal to prevent
interruption, when the signal is unmasked the CPU pops the
first IRQ from the FIFO. Or use a bitmap in flops or SRAM
(prioritization happensin the logic that asserts the fact
hat an interrupt is pending to the CPU).

Choose whether you want a FIFO/bitmap per target CPU, or global
pending data with the logic to select highest priority pending
IRQ when the CPU signals that interrups are not masked.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 17 Mar 2025 13:38:12 GMT
scott@slp53.sl.home (Scott Lurndal) wrote:

Robert Finch <robfi680@gmail.com> writes:

<please trim posts>

Consider that you have a pool of 4 cores setup to receive
interrupts. That those 4 cores are running at differing priorities
and the interrupt is at a still different priority. You want the
core operating at the lowest
priority (with the right software stack) to accept the interrupt
!!

Okay, I wrote a naive hardware filter for this which should work
okay for small numbers of CPUs but does not scale up very well.
What happens if there is no core ready? Place the IRQ back into the
queue (regenerate the IRQ as an IRQ miss IRQ)? Or just wait for an >available core. I do not like the idea of waiting as it could stall
the system.

Use a fifo to hold up to N pending IRQ. Define a signal that asserts
when the fifo is non-empty. The CPU can mask the signal to prevent interruption, when the signal is unmasked the CPU pops the
first IRQ from the FIFO. Or use a bitmap in flops or SRAM
(prioritization happensin the logic that asserts the fact
hat an interrupt is pending to the CPU).

Choose whether you want a FIFO/bitmap per target CPU, or global
pending data with the logic to select highest priority pending
IRQ when the CPU signals that interrups are not masked.

The problem Robert is talking about arises when there are many
interrupt source and many target CPUs.
The required routing/prioritization/acknowledgment logic (at least a
naive logic I am having in mind) would be either non-scalable or
relatively complicated. Process of selection for the second case will
take multiple cycles (I am thinking about ring).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Michael S <already5chosen@yahoo.com> writes:

On Mon, 17 Mar 2025 13:38:12 GMT
scott@slp53.sl.home (Scott Lurndal) wrote:

Robert Finch <robfi680@gmail.com> writes:

<please trim posts>

Consider that you have a pool of 4 cores setup to receive
interrupts. That those 4 cores are running at differing priorities
and the interrupt is at a still different priority. You want the
core operating at the lowest
priority (with the right software stack) to accept the interrupt
!!

Okay, I wrote a naive hardware filter for this which should work
okay for small numbers of CPUs but does not scale up very well.
What happens if there is no core ready? Place the IRQ back into the
queue (regenerate the IRQ as an IRQ miss IRQ)? Or just wait for an
available core. I do not like the idea of waiting as it could stall
the system.

Use a fifo to hold up to N pending IRQ. Define a signal that asserts
when the fifo is non-empty. The CPU can mask the signal to prevent
interruption, when the signal is unmasked the CPU pops the
first IRQ from the FIFO. Or use a bitmap in flops or SRAM
(prioritization happensin the logic that asserts the fact
hat an interrupt is pending to the CPU).

Choose whether you want a FIFO/bitmap per target CPU, or global
pending data with the logic to select highest priority pending
IRQ when the CPU signals that interrups are not masked.

The problem Robert is talking about arises when there are many
interrupt source and many target CPUs.

I work with socs with many (> 64) CPUs and several hundred
interrupt sources, with 10s to 100s of individual vectors
per source. We use the ARM GICv3 as the interrupt
controller, which provides the necessary logic to support
individual enables, priorities, security state and target
routing information for each IRQ. It's a fairly complex IP block when
support for virtualization is included. Many routing
and configuration tables are kept in DRAM allocated by the
hypervisor or bare-metal OS and cached as necessary. There
is a class of interrupt for which the configuration information
is kept in flops (SPI) that can be used for a limited number
of latency sensitive interrupts and for level-sensitive interrupts.

The required routing/prioritization/acknowledgment logic (at least a
naive logic I am having in mind) would be either non-scalable or
relatively complicated.

Indeed, to provide the full set of interrupt routing capabilities
is not something that can be done with naive logic.

For a scalable design, it's useful to consider how the logic
will scale as the core counts and device counts increase with
time.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Robert Finch <robfi680@gmail.com> writes:

On 2025-03-17 9:38 a.m., Scott Lurndal wrote:

Robert Finch <robfi680@gmail.com> writes:

Been reading up on the RISCV AIA.

For RISCV the CPU core handling the interrupt is indirectly specified by
the I/O address set in the device as there is an IMSIC for each RISCV
hart. So only a single IMSIC would be responding at that address. It
would be up to software to set the I/O address to pick a particular CPU
core. It seems to me that MSI interrupt handling using AIA would be >heavy-weight. Having a controller for every hart could be a lot of logic
if there are a lot of harts. There may be more than one hart per CPU.

Reading that the I/O addresses need to be translated by an IOMMU. In Q+
since an interrupt controller number is being used instead of an I/O
address there is no need to translate the address. Software needs to >determine which group of cores will be handling the interrupt, and
select an interrupt controller appropriately.

The Q+ controller looks a bit like an IMSIC controller as it has pending
and enable bits. I note that there is an enable bit in the vector table
and an enable bit array. So, I assume both bits must be enabled for an >interrupt to occur.

Here's a copy of a slide I did a decade ago for ARM64 (GICv3) interrupts,
not much has changed since.

Interrupt Gates

There are a number of gates that must be open to pass an interrupt
from the source to the destination Core

¡ Device Interrupt Enable Register (e.g. A NIC receive interrupt enable)
¡ MSI-X Vector Enable (mask bit in each MSI-X vector control register)
¡ MSI-X PCI-Express Capability Enable (enable bit and function mask in MSI-X
Capability message control field)
¡ The PCI CMD register must have bus mastering enabled
¡ GICv3 Distributor/Redistributor/LPI Properties per-interrupt enable bit
¡ GICv3 Group Enable in distributor (GICD_CTLR)
¡ GICv3 Group Enable in Target core (ICC_IGRPEN{01}_EL1)
¡ Priority Mask register and current running priority on target core
¡ ARM64 core interrupt signal Mask (PSTATE.A/I/F)

Interrupt group, in this context, defines the security state of
the interrupt (group 0: secure, group 1: non-secure) and is a
configuration bit associated with each interrupt.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Michael S wrote:

On Mon, 17 Mar 2025 13:38:12 GMT
scott@slp53.sl.home (Scott Lurndal) wrote:

Robert Finch <robfi680@gmail.com> writes:

<please trim posts>

Consider that you have a pool of 4 cores setup to receive
interrupts. That those 4 cores are running at differing priorities
and the interrupt is at a still different priority. You want the
core operating at the lowest
priority (with the right software stack) to accept the interrupt
!!

Okay, I wrote a naive hardware filter for this which should work
okay for small numbers of CPUs but does not scale up very well.
What happens if there is no core ready? Place the IRQ back into the
queue (regenerate the IRQ as an IRQ miss IRQ)? Or just wait for an
available core. I do not like the idea of waiting as it could stall
the system.

Use a fifo to hold up to N pending IRQ. Define a signal that asserts
when the fifo is non-empty. The CPU can mask the signal to prevent
interruption, when the signal is unmasked the CPU pops the
first IRQ from the FIFO. Or use a bitmap in flops or SRAM
(prioritization happensin the logic that asserts the fact
hat an interrupt is pending to the CPU).

Choose whether you want a FIFO/bitmap per target CPU, or global
pending data with the logic to select highest priority pending
IRQ when the CPU signals that interrups are not masked.

The problem Robert is talking about arises when there are many
interrupt source and many target CPUs.
The required routing/prioritization/acknowledgment logic (at least a
naive logic I am having in mind) would be either non-scalable or
relatively complicated. Process of selection for the second case will
take multiple cycles (I am thinking about ring).

Another problem is what does the core do with the in flight instructions.

Method 1 is simplest, it injects the interrupt request at Retire
as that's where the state of everything is synchronized.
The consequence is that, like exceptions, the in flight instructions all
get purged, and we save the committed RIP, RSP and interrupt control word. While that might be acceptable for a 5 stage in-order pipeline,
it could be pretty expensive for an OoO 200+ instruction queue
potentially tossing hundreds of cycles of near finished work.

Method 2 pipelines the switch by injecting the interrupt request at Fetch. Decode converts the request to a special uOp that travels down the IQ
to Retire and allows all the older work to complete.
This is more complex as it requires a two phase hand-off from the
Interrupt Control Unit (ICU) to the core as a branch mispredict in the
in flight instructions might cause a tentative interrupt acceptance to later
be withdrawn.

The ICU believes the core is in a state to accept a higher priority
interrupt. It sends a request to core, which checks its current state and
sends back an immediate INT_ACK if _might_ accept and stalls Fetch, or a NAK. When the special uOp reaches Retire, it sends a signal to Fetch which
then sends an INT_ACCEPT signal to ICU to complete the handoff.
If a branch mispredict occurs that causes interrupts to be disabled,
then Fetch sends an INT_REJECT to ICU, and unstalls its fetching.
(Yes that is not optimal - make it work first, make it work well second.)

This also raises a question about what the ICU is doing during this
long latency handoff. One wouldn't want ICU to sit idle so it might
have to manage the handoff of multiple interrupts to multiple cores
at the same time, each as its own little state machine.

One should see that this decision on how the core handles the
handoff has a large impact on the design complexity of the ICU.

Personally, I would use method 1 first to get something working
then if this is OoO think about getting fancy with method 2.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 17 Mar 2025 15:53:42 +0000, Scott Lurndal wrote:

Robert Finch <robfi680@gmail.com> writes:

Here's a copy of a slide I did a decade ago for ARM64 (GICv3)
interrupts, not much has changed since.

Interrupt Gates

There are a number of gates that must be open to pass an interrupt
from the source to the destination Core

Here are the enablement's in My 66000 {Borrowing Scott's list}

� Device Interrupt Enable Register (e.g. A NIC receive interrupt
enable)
� MSI-X Vector Enable (mask bit in each MSI-X vector control
register)
� MSI-X PCI-Express Capability Enable (enable bit and function mask
in
MSI-X Capability message control field)
� The PCI CMD register must have bus mastering enabled
� Interrupt table must be enabled to receive this priority
� Interrupt table must be enabled to deliver this priority
� Core Priority must be lower than interrupt priority

Although there is an interrupt enable bit in each core, when control
arrives at dispatcher core is already re-entrant, at the proper SW
stack level, and priority, with the old register file saved in memory
and the register file of that SW stack level loaded. So, many/most
taken interrupts do not need to disable interrupts even for a short
period of time.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 17 Mar 2025 18:33:09 +0000, EricP wrote:

Michael S wrote:

On Mon, 17 Mar 2025 13:38:12 GMT
scott@slp53.sl.home (Scott Lurndal) wrote:

------------------

The problem Robert is talking about arises when there are many
interrupt source and many target CPUs.
The required routing/prioritization/acknowledgment logic (at least a
naive logic I am having in mind) would be either non-scalable or
relatively complicated. Process of selection for the second case will
take multiple cycles (I am thinking about ring).

Another problem is what does the core do with the in flight
instructions.

Method 1 is simplest, it injects the interrupt request at Retire
as that's where the state of everything is synchronized.
The consequence is that, like exceptions, the in flight instructions all
get purged, and we save the committed RIP, RSP and interrupt control
word.
While that might be acceptable for a 5 stage in-order pipeline,
it could be pretty expensive for an OoO 200+ instruction queue
potentially tossing hundreds of cycles of near finished work.

Lowest interrupt Latency
Highest waste of power (i.e., work)

Method 2 pipelines the switch by injecting the interrupt request at
Fetch.
Decode converts the request to a special uOp that travels down the IQ
to Retire and allows all the older work to complete.
This is more complex as it requires a two phase hand-off from the
Interrupt Control Unit (ICU) to the core as a branch mispredict in the
in flight instructions might cause a tentative interrupt acceptance to
later be withdrawn.

Interrupt latency is dependent on executing instructions,
Lowest waste of power

But note: In most cases, it already took the interrupt ~150 nanoseconds
to arrive at the interrupt service port. 1 trip from device to DRAM
(possibly serviced by L3), 1 trip from DRAM back to device, 1 tip from
device to interrupt service port; and 4 DRAM (or L3) accesses to log
interrupt into table.

Also, in most cases, the 200-odd instructions in the window will finish
in 100-cycles or as little as 20ns--but if the FDIV unit is saturated, interrupt latency could be as high as 640 cycles and as long as 640ns.

The ICU believes the core is in a state to accept a higher priority interrupt. It sends a request to core, which checks its current state
and
sends back an immediate INT_ACK if _might_ accept and stalls Fetch, or a
NAK.

In My 66000, ICU knows nothing about the priority level (or state)
of any core in the system. Instead, when a new higher priority
interrupt is raised, the ISP broadcasts a 64-bit mask indicating
which priority levels in the interrupt table have pending inter-
rupts with an MMI/O message to the address of the interrupt table.

All cores monitoring that interrupt table capture the broadcast,
and each core decides to negotiate for an (not that) interrupt
by requesting the highest priority interrupt from the table.

When the request returns, and it is still at a higher priority
than the core is running, core performs interrupt control transfer.
If the interrupt is below the core's priority it is returned to
ISP as if NAKed.

Prior to interrupt control transfer, core remains running what-
ever it was running--and all the interrupt stuff is done by state
machines at the edge of the core and the L3/DRAM controller.

When the special uOp reaches Retire, it sends a signal to Fetch which
then sends an INT_ACCEPT signal to ICU to complete the handoff.
If a branch mispredict occurs that causes interrupts to be disabled,
then Fetch sends an INT_REJECT to ICU, and unstalls its fetching.
(Yes that is not optimal - make it work first, make it work well
second.)

This also raises a question about what the ICU is doing during this
long latency handoff. One wouldn't want ICU to sit idle so it might
have to manage the handoff of multiple interrupts to multiple cores
at the same time, each as its own little state machine.

One must assume that ISP is capable of taking a new interrupt
from a device every 5-ish cycles and interrupt handoff is in the
range of 50 cycles, and that each interrupt could be to a different
interrupt table.

My 66000 ISP treats successive requests to any one table as strongly
ordered, and requests to different tables as completely unordered.

One should see that this decision on how the core handles the
handoff has a large impact on the design complexity of the ICU.

I did not "see" that in My 66000's interrupt architecture. The ISP
complexity is fixed, and the core's interrupt negotiator is a small
state machine (~10-states).

ISP essentially performs 4-5 64-bit memory accesses, and possibly
1 MMI/O 64-bit broadcast on arrival of MSI-X interrupt. Then if
a core negotiates, it performs 3 more memory accesses per negotiator.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

mitchalsup@aol.com (MitchAlsup1) writes:

On Mon, 17 Mar 2025 18:33:09 +0000, EricP wrote:

Michael S wrote:

On Mon, 17 Mar 2025 13:38:12 GMT
scott@slp53.sl.home (Scott Lurndal) wrote:

------------------

The problem Robert is talking about arises when there are many
interrupt source and many target CPUs.
The required routing/prioritization/acknowledgment logic (at least a
naive logic I am having in mind) would be either non-scalable or
relatively complicated. Process of selection for the second case will
take multiple cycles (I am thinking about ring).

Another problem is what does the core do with the in flight
instructions.

Method 1 is simplest, it injects the interrupt request at Retire
as that's where the state of everything is synchronized.
The consequence is that, like exceptions, the in flight instructions all
get purged, and we save the committed RIP, RSP and interrupt control
word.
While that might be acceptable for a 5 stage in-order pipeline,
it could be pretty expensive for an OoO 200+ instruction queue
potentially tossing hundreds of cycles of near finished work.

Lowest interrupt Latency
Highest waste of power (i.e., work)

Method 2 pipelines the switch by injecting the interrupt request at
Fetch.
Decode converts the request to a special uOp that travels down the IQ
to Retire and allows all the older work to complete.
This is more complex as it requires a two phase hand-off from the
Interrupt Control Unit (ICU) to the core as a branch mispredict in the
in flight instructions might cause a tentative interrupt acceptance to
later be withdrawn.

Interrupt latency is dependent on executing instructions,
Lowest waste of power

But note: In most cases, it already took the interrupt ~150 nanoseconds
to arrive at the interrupt service port. 1 trip from device to DRAM
(possibly serviced by L3), 1 trip from DRAM back to device, 1 tip from
device to interrupt service port; and 4 DRAM (or L3) accesses to log >interrupt into table.

How do you handle timer interrupts? Those are generally not
message based, but rather internal signals within the core that
raise an interrupt (perhaps coordinating with the interrupt controller
for priority, security state, and enable bit). These are generally
wired (and the enables/state/priority are flops) for low latency.

There will generally be at least one general purpose timer per
core plus any watchdog timers.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

On Thu, 20 Mar 2025 20:25:59 +0000, 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:

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

On Wed, 19 Mar 2025 14:03:56 +0000, Dan Cross wrote:

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

I want to address the elephant in the room::

Why disable interrupts AT ALL !!

So that you can have some mechanism for building critical
sections that span multiple instructions, where just having
access to atomics and spin locks isn't enough.

You can do this with priority, too.

In the limit, disabling interrupts is just setting the priority
mask to infinity, so in some sense this is de facto true. But I
don't see how having a prioritization scheme is all that useful.
Consider that when you're starting the system up, you need to
do things like set up an interrupt handler vector, and so on;

The Interrupt vector is completely software. HW delivers the MSI-X >>>message and the service for which this message is for, and SW decides >>>what to do with this message to that service provider. No HW vectoring >>>but HW does deliver all the bits needed to guide SW to its goal.

Maybe I'm missing the context here, and apologies if I am. But
which interrupt disable are we talking about here, and where? I

We are talking about the core's Interrupt Disablement and nothing
of the gates farther out in the system that control interrupt
deliveries (or not).

Ok, that's what I thought.

am coming at this from the perspective of systems software
running on some CPU core somewhere; if I want that software to
enter a critical section that cannot be interrupted, then it
seems to me that MSI-X delivery is just a detail at that point.
I might want to prevent IPIs, or delivery or local interrupts
attached directly to the CPU (or something like an IOAPIC or
GIC distributor).

All of those flow through the same mechanism; even a locally
generated timer interrupt.

Right. So whether those interrupts come from MSI-X or anything
else is mostly irrelevant.

[snip/]
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.

If we can s/taken/attempts/ in the first line of that paragraph::

If it has merely attempted, then it's a completely different
scenario. Something that is more transactional in nature is no
longer just a simple CAS-based spinlock. It may be _better_,
but it is definitely different.

My architecture has a mechanism to perform ATOMIC stuff over multiple >instruction time frames that has the property that a higher priority
thread which interferers with a lower priority thread, the HPT wins
and the LPT fails its ATOMIC event. It is for exactly this reason
that I drag priority through the memory hierarchy--so that real-time
things remain closer to real-time (no or limited priority inversions).

Without being able to see this in practice, it's difficult to
speculate as to how well it will actually work in real-world
scenarios. What is the scope of what's covered by this atomic
thing?

Consider something as simple as popping an item off of the front
of a queue and inserting it into an ordered singly-linked list:
In this case, I'm probably going to want to take a lock on the
queue, then lock the list, then pop the first element off of the
queue by taking a pointer to the head. Then I'll set the head
to the next element of that item, then walk the list, finding
the place to insert (make sure I'm keeping track of the "prev"
pointer somehow), then do the dance to insert the item: set the
item's next to the thing after where I'm inserting, set the
prev's next to the item if it's not nil, or set the list head
to the item. Then I unlock the list and then the queue (suppose
for some reason that it's important that I hold the lock on the
queue until the element is fully added to the list).

This isn't complicated, and for a relatively small list it's not
expensive. Depending on the circumstances, I'd feel comfortable
doing this with only a spinlocks protecting both the queue and
the list. But it's more than a two or three instructions, and
doesn't feel like something that would fit well into the "may
fail atomic" model.

Mandating to SW that typ SW must use this mechanism will not fly,
at least in the first several iterations of an OS for the system.
So the std. methods must remain available.

AND to a large extend this sub-thread is attempting to get a
usefully large number of them annotated.

It sounds like the whole model is fairly different, and would
require software writers to consider interrupts occuring in
places that wouldn't have to in a more conventional design. I
suspect you'd have a fairly serious porting issue with existing
systems, but maybe I misunderstand.

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.

This seems to be onerous on SW mainly because of too many unknowns
to track down and deal with.

Yes.

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.

Agreed.

The idea of priority as described above seems to prize latency
above other considerations, but it's not clear to me that that
is the right tradeoff. Exactly what problem is being solved?

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

cross@spitfire.i.gajendra.net (Dan Cross) writes:

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

My architecture has a mechanism to perform ATOMIC stuff over multiple >>instruction time frames that has the property that a higher priority
thread which interferers with a lower priority thread, the HPT wins
and the LPT fails its ATOMIC event. It is for exactly this reason
that I drag priority through the memory hierarchy--so that real-time
things remain closer to real-time (no or limited priority inversions).

Without being able to see this in practice, it's difficult to
speculate as to how well it will actually work in real-world
scenarios. What is the scope of what's covered by this atomic
thing?

Sounds a lot like transactional memory. Something that has
yet to prove to be usable in the general case.

Consider something as simple as popping an item off of the front
of a queue and inserting it into an ordered singly-linked list:
In this case, I'm probably going to want to take a lock on the
queue, then lock the list, then pop the first element off of the
queue by taking a pointer to the head.

Which can be done with compare and exchange, atomically;
a lock may not be necessary.

The insert into an ordered list will likely require a
spin lock (or a reader-writer lock of some form).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

MitchAlsup1 wrote:

On Sun, 23 Mar 2025 16:16:16 +0000, EricP wrote:

MitchAlsup1 wrote:

On Thu, 20 Mar 2025 12:50:09 +0000, Dan Cross wrote:

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

But let me turn it around, what real-world problem does this
interrupt prioritization scheme solve coupled with the inability
to disable interrupts solve?

The OS does not have to "walk" its schedule queues in order to
context switch.

The SVR (SuperVisor Return) instruction checks the priority of
the thread that had been interrupted, and if it is of lower
priority than what is pending in the interrupt table, the
one on the interrupt table receives control while the lower
priority thread remains interrupted.

Thus, the return path from an ISR, just does an SVR. If a
DPC/softIRQ has been setup, or another interrupt has become
pending, HW chooses the path--acting as if HW returned control
to the interrupted thread, and then immediately took the inter-
rupt of highest priority still pending--without having executed
a single instruction in the interrupted thread.

Is anyone complaining that the
ability to disable interrupts is somehow a serious burden?

This thread started with the notion of MSI interrupts and the
inherent need to DI upon arrival at ISR dispatcher. This sub-
thread is investigating whether one can perform ISRs without
disabling interrupts. Thus, making IDisablement an unnecessary
part of interrupt servicing itself.

Your (and EricP)'s contribution is to annotate those instances
where one can arrive at an ISR IE and still want/need to DI and EI
independent of the control transfer from and back to interrupted
thread (even if control arrives reentrantly from interrupted thread).

Supervisor return, whatever it is called - sysret, rei, svr -
is traditionally another point where a number of OS race conditions
can force it to briefly disable interrupts.

The classic case is when a DPC/SoftIrq may be posted by an Interrupt
Service Routine (ISR) and causes the First Level Interrupt Handler
(FLIH),
which is the ISR nested first on the stack of priority interrupts,
to exit into the OS rather than return to its prior thread.

The race condition occurs between the point when the FLIH ISR epilogue
checks for pending a pending DPC, and not finding one decides to return
to the prior thread. Between that check and the SVR instruction a higher
priority interrupt occurs and posts a DPC.

I remove that race condition by removing the need for FLIR (which I
call the dispatcher) to check. All the checks are done AT* the SVR instruction. (*) and during

Ok you have that but other platforms must deal with this in code.
VAX used a real priority-1 (lowest) interrupt looped back to itself
to request a software interrupt, eliminating this check.

Intel APIC allows this kind of self interrupt loop back too but
I don't know if any OS uses it for its internal scheduling.

On platforms without something like this the OS has to deal
with this race condition, which requires disabling interrupts.

Also on PC's the 8259 PIC has an End Of Interrupt (EOI) race condition,
and it looks like the APIC has the same one, which requires briefly
disabling interrupts in the return path.

Another race condition can be how does an epilogue know if it is a FLIH
or nested one? A counter for each core incremented by the ISR prologue
and checked by the epilogue would do but what if the nested interrupt
catches a lower level prologue just before it increments the counter.

How to know:: It COULD look at the value in its stack pointer. An
empty stack implies it is leaving, a non-empty stack implies it
has more to do.

The stack pointer might be too dynamic for this.
It can test the if the return RIP is in a certain range.
If it is inside a prologue you know it is nested.
If inside the epilogue then it might have just caught the exit race
so reset the return RIP to the start of the epilogue exit sequence.

By arranging for all the prologues and epilogue to be at the highest
addresses then a CMP and BGEU filters out the 99.999% usual cases.

But all of this adds to the return from interrupt code path length.

But in practice, it does not need to know as interrupts are properly
nested and serviced in priority order.

It is not checking whether they are properly nested.
Only the FLIH does the check whether to return or exit through the OS.
That is to prevent Dispatcher reentrancy.

And this check can be replaced by a priority-1 self interrupt capability
to trap into the software interrupt dispatcher.

There are a number of non-interruptible checks and control flag changes
that supervisor return must perform.

To do this I have a single instruction CSVR Conditional Supervisor
Return
which handles all interrupt, exception, and SysCall returns. It performs
a model specific test on an interrupt control register and if True
changes
the ICR state and returns to the prior context. If False makes other ICR
state changes and falls through the CSVR instruction where code can
determine what just changed. This would typically be a jump into the OS
Dispatcher to flush any DPC/SoftIrq and check for thread rescheduling.
This whole return sequence is performed without having to disable
interrupts.

I, too, have a single instruction (SVR) that delivers control to the
highest priority still pending thread, regardless of whether it is
a new interrupt, a scheduled DPC/softIRQ, a local timer, an IPI, or
the thread the interrupt stack was placed upon.

SVR looks at the priority of the thread to receive control, and the priorities of pending 'interrupts' (of which DPC/softIRQ and IPIs
are part) and transfers control to the highest priority pending thread--occasionally that thread is the interrupted one.

The new idea I'm proposing is CSVR *Conditional* Supervisor Return
which can fall through in the unlikely event something disturbs the non-interruptible return sequence.

This can be used to optimize the return path by avoiding returning from
an interrupt only to immediately take a priority-1 software interrupt.

Should a higher priority thread become pending while SVR is in progress,
the higher priority thread will receive control before the first inst- ruction of the mis-receiving thread is performed.

As far as you have explained these things to me, I see no race
conditions
in the architected means.

Perhaps not for your approach but I'm looking at other optimizations
that might introduce them. One was optimizing the common return path:

Before a supervisor return starts to reload the saved register set
it tests if a DPC is pending and about to generate a software interrupt,
and if so jumps back into the Dispatcher. This saves reloading the registers only to immediately take another interrupt, a pipeline drain and fill,
and resave the same registers.

To do this optimization, before it starts to reload the registers
it tests the Interrupt Control Register (ICR) to check if it is about to trigger a SWI and if so adjusts the ICR and jumps into the Dispatcher. Otherwise it restores registers and does a Conditional Supervisor Return
which reperforms the same test and can fall through if the test fails.

This also requires that kernel/interrupt stacks be switched a certain way, which just so happens to be the same as the x86 way. That is, hardware only switches stacks if interrupted mode is User. This leaves it up to OS
software to decide which stack to use at what points inside the kernel.

Also I'd save the interrupt context, the old RIP, old RSP and old interrupt status in hardware registers, not on the stack, and the interrupt vector
RIP address is calculated based on the priority. This eliminates all memory access from the exception and interrupt entry and exit transition sequences, and thereby eliminates page faults and memory error possibility and
cache access latency.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

MitchAlsup1 [2025-03-24 17:36:28] wrote:

On Mon, 24 Mar 2025 12:37:13 +0000, Dan Cross wrote:

Consider something as simple as popping an item off of the front
of a queue and inserting it into an ordered singly-linked list:

[...]

I have almost that in the documentation for my ATOMIC stuff::
The following code moves a doubly linked element from one place
in a concurrent data structure to another without any interested
3rd party being able to see that the element is now within the
CDS at any time::

Would your "ATOMIC stuff" really handle Dan's example, tho?
A key element in Dan's example if the "ordered singly-linked list",
i.e. you need to walk the list an unbounded number of steps until you
can find the insertion point, so I don't think you can do the whole
thing inside your ATOMIC stuff.

IOW, you'd have to somehow move the list-walk outside of the atomic section. E.g. if you know elements are only ever removed from the tail of the
list, you can presumably walk the list outside of the ATOMIC stuff and
then do the "remove from the queue and insert into the list" atomically
since it's a small&finite number of steps (with a test to loop back to
the list-walk if someone else inserted or removed anything at that point
in the mean time).


Stefan

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 24 Mar 2025 13:59:49 +0000, Scott Lurndal wrote:

cross@spitfire.i.gajendra.net (Dan Cross) writes:

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

My architecture has a mechanism to perform ATOMIC stuff over multiple >>>instruction time frames that has the property that a higher priority >>>thread which interferers with a lower priority thread, the HPT wins
and the LPT fails its ATOMIC event. It is for exactly this reason
that I drag priority through the memory hierarchy--so that real-time >>>things remain closer to real-time (no or limited priority inversions).

Without being able to see this in practice, it's difficult to
speculate as to how well it will actually work in real-world
scenarios. What is the scope of what's covered by this atomic
thing?

Sounds a lot like transactional memory. Something that has
yet to prove to be usable in the general case.

It is not TM, but can be used to implement TM should you like.
It is a set of instructions that can implement any (known)
ATOMIC process (TestAndSet, TestAndTestAndSet; lock, unlock,
LD-locked, ST-conditional, CompareSwap, CompareDouble, SwapDouble CompareTriple, SwapTriple, RemoveElement, InsertElement,
MoveElement, ...}

It is basically a recipe book so SW can implement whatever kinds
of ATOMIC things SW wants, leaving HW out of the loop.

you can also consider it a fully pipelined version of LDL and STC
with up to 8 cache lines of data available for the event.

Consider something as simple as popping an item off of the front
of a queue and inserting it into an ordered singly-linked list:
In this case, I'm probably going to want to take a lock on the
queue, then lock the list, then pop the first element off of the
queue by taking a pointer to the head.

Which can be done with compare and exchange, atomically;
a lock may not be necessary.

The insert into an ordered list will likely require a
spin lock (or a reader-writer lock of some form).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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 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.

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.

- Dan C.

This is why I mentioned the terminology thing: threads do not hold
spinlocks, they hold mutexes. 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.

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 24 Mar 2025 12:37:13 +0000, Dan Cross wrote:

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

---------------------

My architecture has a mechanism to perform ATOMIC stuff over multiple >>instruction time frames that has the property that a higher priority
thread which interferers with a lower priority thread, the HPT wins
and the LPT fails its ATOMIC event. It is for exactly this reason
that I drag priority through the memory hierarchy--so that real-time
things remain closer to real-time (no or limited priority inversions).

Without being able to see this in practice, it's difficult to
speculate as to how well it will actually work in real-world
scenarios. What is the scope of what's covered by this atomic
thing?

Consider something as simple as popping an item off of the front
of a queue and inserting it into an ordered singly-linked list:
In this case, I'm probably going to want to take a lock on the
queue, then lock the list, then pop the first element off of the
queue by taking a pointer to the head. Then I'll set the head
to the next element of that item, then walk the list, finding
the place to insert (make sure I'm keeping track of the "prev"
pointer somehow), then do the dance to insert the item: set the
item's next to the thing after where I'm inserting, set the
prev's next to the item if it's not nil, or set the list head
to the item. Then I unlock the list and then the queue (suppose
for some reason that it's important that I hold the lock on the
queue until the element is fully added to the list).

I have almost that in the documentation for my ATOMIC stuff::
The following code moves a doubly linked element from one place
in a concurrent data structure to another without any interested
3rd party being able to see that the element is now within the
CDS at any time::

BOOLEAN MoveElement( Element *fr, Element *to )
{
Element *fn = esmLOCKload( fr->next );
Element *fp = esmLOCKload( fr->prev );
Element *tn = esmLOCKload( to->next );
esmLOCKprefetch( fn );
esmLOCKprefetch( fp );
esmLOCKprefetch( tn );
if( !esmINTERFERENCE() )
{
fp->next = fn;
fn->prev = fp;
to->next = fr;
tn->prev = fr;
fr->prev = to;
esmLOCKstore( fr->next, tn );
return TRUE;
}
return FALSE;
}

The ESM macros simply tell the compiler to set a bit in the LD/ST
instructions. esmINTERFERENCE is a query on the state of the event
and whether a 2nd party has performed a memory action that kills
the event.

It is required to touch every cache line participating in the event
prior to attempting the ATOMIC update--this is what esmLOCKprefetch
does. One can use up to 8 cache lines in a single ATOMIC event.

Either everyone in the system sees the update and at the same
instant in time, or no one sees any update at all.

Technically, there is no one holding a lock ...

This isn't complicated, and for a relatively small list it's not
expensive. Depending on the circumstances, I'd feel comfortable
doing this with only a spinlocks protecting both the queue and
the list. But it's more than a two or three instructions, and
doesn't feel like something that would fit well into the "may
fail atomic" model.

Should be obvious how to change the insertion into a singly linked
list in a different data structure.

Mandating to SW that typ SW must use this mechanism will not fly,
at least in the first several iterations of an OS for the system.
So the std. methods must remain available.

AND to a large extend this sub-thread is attempting to get a
usefully large number of them annotated.

It sounds like the whole model is fairly different, and would
require software writers to consider interrupts occuring in
places that wouldn't have to in a more conventional design. I
suspect you'd have a fairly serious porting issue with existing
systems, but maybe I misunderstand.

Which is why ID is available.

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.

This seems to be onerous on SW mainly because of too many unknowns
to track down and deal with.

Yes.

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.

Agreed.

The idea of priority as described above seems to prize latency
above other considerations, but it's not clear to me that that
is the right tradeoff. Exactly what problem is being solved?

The instruction path into and out of handlers is shorter. Basically
nobody has to look at the schedule queues because HW will do it for
you. For example: GuestOS interrupt dispatcher is approximately::

-- +-------------+-----+------------------------+
R0 | ----------- | ISR | --- MSI-X message ---- |
-- +-------------+-----+------------------------+

Dispatcher:
// at this point we are reentrant
SR R7,R0,<39:32>
CMP R2,R7,MaxTable
PLO R2,TTTF
SR R1,R0,<32:0>
CALX [IP,R7<<3,Table-.]
SVR
// if we get here R0<37:32>
// was out of bounds

This does all of the register file saving and restoring, all of
the DPC/softIRQ stuff, all of the checking for additional ISRs,
IPIs, ... Changes priority, privilege, ROOT pointers and associated
ASIDs from and back to.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <pzdEP.126362$f5K3.26821@fx36.iad>,
Scott Lurndal <slp53@pacbell.net> wrote:

cross@spitfire.i.gajendra.net (Dan Cross) writes:

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

My architecture has a mechanism to perform ATOMIC stuff over multiple >>>instruction time frames that has the property that a higher priority >>>thread which interferers with a lower priority thread, the HPT wins
and the LPT fails its ATOMIC event. It is for exactly this reason
that I drag priority through the memory hierarchy--so that real-time >>>things remain closer to real-time (no or limited priority inversions).

Without being able to see this in practice, it's difficult to
speculate as to how well it will actually work in real-world
scenarios. What is the scope of what's covered by this atomic
thing?

Sounds a lot like transactional memory. Something that has
yet to prove to be usable in the general case.

I understand that some mallocs have done it; McRT-Malloc from
Intel, if I'm not mistaken.

Consider something as simple as popping an item off of the front
of a queue and inserting it into an ordered singly-linked list:
In this case, I'm probably going to want to take a lock on the
queue, then lock the list, then pop the first element off of the
queue by taking a pointer to the head.

Which can be done with compare and exchange, atomically;
a lock may not be necessary.

The insert into an ordered list will likely require a
spin lock (or a reader-writer lock of some form).

I'm sure one could do a lockless pop using a cmp exchange, but I
wanted to a scenario where one would want to hold onto both
locks throughout the critical section for some reason.
I just don't see how this works in the proposed scenario.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

On Thu, 20 Mar 2025 12:50:09 +0000, Dan Cross wrote:

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

But let me turn it around, what real-world problem does this
interrupt prioritization scheme solve coupled with the inability
to disable interrupts solve?

The OS does not have to "walk" its schedule queues in order to
context switch.

Of course it does. The OS is the entity that selects the next
thing to run and assigns priorities. Even in a scheme where the
hardware has a notion of priority that the operating system can
rely on directly, priorities can change over time and the OS has
to be able to account for that.

The SVR (SuperVisor Return) instruction checks the priority of
the thread that had been interrupted, and if it is of lower
priority than what is pending in the interrupt table, the
one on the interrupt table receives control while the lower
priority thread remains interrupted.

First, this sounds completely non-portable. Second, how does
one handle scheduling policies around threads that are all at
the same priority level? Third, as an OS person, this is a pet
peeve of mine, from both hardware and language perspectives: how
does the hardware guarantee that it's notion of a "thread" is
the same as mine? I don't like it when systems force a
particular "shape" of a solution on me. POSIX threads in
hardware is something that I explicitly do not want, because any
impedence mismatch between the hardware idea and what I need in
the OS create friction, and limits my ability to build the
system that I want.

Thus, the return path from an ISR, just does an SVR. If a
DPC/softIRQ has been setup, or another interrupt has become
pending, HW chooses the path--acting as if HW returned control
to the interrupted thread, and then immediately took the inter-
rupt of highest priority still pending--without having executed
a single instruction in the interrupted thread.

See above. As an OS person, I find this level of intimacy with
the hardware horrifying. It reminds me of the VAX queue
instructions; neat idea, VMS used them, but awful in practice
and Unix largely ignored them. As a result, it made VMS harder
to port than was necessary.

Is anyone complaining that the
ability to disable interrupts is somehow a serious burden?

This thread started with the notion of MSI interrupts and the
inherent need to DI upon arrival at ISR dispatcher. This sub-
thread is investigating whether one can perform ISRs without
disabling interrupts. Thus, making IDisablement an unnecessary
part of interrupt servicing itself.

Yes, but why?

I can see some neat symmetry with, say, replacing NMIs with
"infinite priority" interrupts, and perhaps using an interrupt
priority mask to de facto disable interrupt delivery at the
local core; maybe that's useful internally. But I'm not seeing
the use case beyond that.

Your (and EricP)'s contribution is to annotate those instances
where one can arrive at an ISR IE and still want/need to DI and EI >independent of the control transfer from and back to interrupted
thread (even if control arrives reentrantly from interrupted thread).

Many computer designers copy/modify their interrupt architectures
from machines architected prior to the virtualization of Operating
Systems, virtualization of interrupts, HyperVisors, Paranoid threads
(like banking applications) that have survived into the present.

I went the other way, trying to develop a system whereby the path
across context switching domains is cheap and easy*. Not needing
to DI at entry to ISR or exception handlers (more or less) fell
out for free due to the way "the rest of the system" evolved.

(*) cheap for HW, and easy expressly for SW

Not being employed, and not having an OS guy to bounce ideas off
and discuss consequences of going this way or that way is not
available, so I lean on a few people hear to "beat me up" when
my ideas lead me astray.

18 months ago I had a real-time version of the architecture,
with the property that at any instant in time, each core was
executing the highest priority thread, cores had a means to
message back and forth as if it were a remote procedure call
which could return (synchronous; or not--asynchronous) without
an OS mediating these things. I abandoned it not because it
was not good for real time, but because there was no way to
make it Linux Friendly.

Where I am now, is my attempt at being Linux friendly.

This sounds like it may be interesting for a hard real-time
controller type application with a very thin RTOS, but it's not
all that useful for a general-purpose system.

Here's the problem, though. Being "Linux friendly" is going to
impose design constraints on you that will force you in the
direction of producing an architecture that is far more
conventional than what you are proposing above. If that's what
you want, that's totally fine of course; but if you want to
experiment with a substantially different system architecture,
you're not going to accept that you're software story is going
to be largely bespoke and unportable. That's not to say your
_userspace_ story has to be like that, but your OS will.

Moreover, there's the issue of, how do you expose these
primitives through a high-level language? Most programmers are
not going to be willing to drop down to assembler for these
atomic sequences; maybe to build a mutex primitive or something,
but not for much larger things.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

On Mon, 24 Mar 2025 12:37:13 +0000, Dan Cross wrote:

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

---------------------

My architecture has a mechanism to perform ATOMIC stuff over multiple >>>instruction time frames that has the property that a higher priority >>>thread which interferers with a lower priority thread, the HPT wins
and the LPT fails its ATOMIC event. It is for exactly this reason
that I drag priority through the memory hierarchy--so that real-time >>>things remain closer to real-time (no or limited priority inversions).

Without being able to see this in practice, it's difficult to
speculate as to how well it will actually work in real-world
scenarios. What is the scope of what's covered by this atomic
thing?

Consider something as simple as popping an item off of the front
of a queue and inserting it into an ordered singly-linked list:
In this case, I'm probably going to want to take a lock on the
queue, then lock the list, then pop the first element off of the
queue by taking a pointer to the head. Then I'll set the head
to the next element of that item, then walk the list, finding
the place to insert (make sure I'm keeping track of the "prev"
pointer somehow), then do the dance to insert the item: set the
item's next to the thing after where I'm inserting, set the
prev's next to the item if it's not nil, or set the list head
to the item. Then I unlock the list and then the queue (suppose
for some reason that it's important that I hold the lock on the
queue until the element is fully added to the list).

I have almost that in the documentation for my ATOMIC stuff::
The following code moves a doubly linked element from one place
in a concurrent data structure to another without any interested
3rd party being able to see that the element is now within the
CDS at any time::

BOOLEAN MoveElement( Element *fr, Element *to )
{
Element *fn = esmLOCKload( fr->next );
Element *fp = esmLOCKload( fr->prev );
Element *tn = esmLOCKload( to->next );
esmLOCKprefetch( fn );
esmLOCKprefetch( fp );
esmLOCKprefetch( tn );
if( !esmINTERFERENCE() )
{
fp->next = fn;
fn->prev = fp;
to->next = fr;
tn->prev = fr;
fr->prev = to;
esmLOCKstore( fr->next, tn );
return TRUE;
}
return FALSE;
}

The ESM macros simply tell the compiler to set a bit in the LD/ST >instructions. esmINTERFERENCE is a query on the state of the event
and whether a 2nd party has performed a memory action that kills
the event.

It is required to touch every cache line participating in the event
prior to attempting the ATOMIC update--this is what esmLOCKprefetch
does. One can use up to 8 cache lines in a single ATOMIC event.

Either everyone in the system sees the update and at the same
instant in time, or no one sees any update at all.

Technically, there is no one holding a lock ...

Suppose I need to get the first two elements of the list.

This isn't complicated, and for a relatively small list it's not
expensive. Depending on the circumstances, I'd feel comfortable
doing this with only a spinlocks protecting both the queue and
the list. But it's more than a two or three instructions, and
doesn't feel like something that would fit well into the "may
fail atomic" model.

Should be obvious how to change the insertion into a singly linked
list in a different data structure.

Mandating to SW that typ SW must use this mechanism will not fly,
at least in the first several iterations of an OS for the system.
So the std. methods must remain available.

AND to a large extend this sub-thread is attempting to get a
usefully large number of them annotated.

It sounds like the whole model is fairly different, and would
require software writers to consider interrupts occuring in
places that wouldn't have to in a more conventional design. I
suspect you'd have a fairly serious porting issue with existing
systems, but maybe I misunderstand.

Which is why ID is available.

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.

This seems to be onerous on SW mainly because of too many unknowns
to track down and deal with.

Yes.

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.

Agreed.

The idea of priority as described above seems to prize latency
above other considerations, but it's not clear to me that that
is the right tradeoff. Exactly what problem is being solved?

The instruction path into and out of handlers is shorter. Basically
nobody has to look at the schedule queues because HW will do it for
you. For example: GuestOS interrupt dispatcher is approximately::

-- +-------------+-----+------------------------+
R0 | ----------- | ISR | --- MSI-X message ---- |
-- +-------------+-----+------------------------+

Dispatcher:
// at this point we are reentrant
SR R7,R0,<39:32>
CMP R2,R7,MaxTable
PLO R2,TTTF
SR R1,R0,<32:0>
CALX [IP,R7<<3,Table-.]
SVR
// if we get here R0<37:32>
// was out of bounds

This does all of the register file saving and restoring, all of
the DPC/softIRQ stuff, all of the checking for additional ISRs,
IPIs, ... Changes priority, privilege, ROOT pointers and associated
ASIDs from and back to.

But again, why is that important? Is that a significant
bottleneck for systems software? Is it particularly burdensome
for software for some reason?

I explicitly don't want the hardware to have that level of
control in my scheduling subsystem.

This sounds like a solution looking for a problem.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 24 Mar 2025 15:55:33 +0000, EricP wrote:

MitchAlsup1 wrote:

On Sun, 23 Mar 2025 16:16:16 +0000, EricP wrote:

I may come back to the snipped stuff later

But all of this adds to the return from interrupt code path length.

As noted in my response to Dan C, the return from interrupt code path
length is the RET instruction from the ISR back to Dispatcher and the
SVR instruction at the Dispatcher. Is this short enough?

------------------

I, too, have a single instruction (SVR) that delivers control to the
highest priority still pending thread, regardless of whether it is
a new interrupt, a scheduled DPC/softIRQ, a local timer, an IPI, or
the thread the interrupt stack was placed upon.

SVR looks at the priority of the thread to receive control, and the
priorities of pending 'interrupts' (of which DPC/softIRQ and IPIs
are part) and transfers control to the highest priority pending
thread--occasionally that thread is the interrupted one.

The new idea I'm proposing is CSVR *Conditional* Supervisor Return
which can fall through in the unlikely event something disturbs the non-interruptible return sequence.

I detected that. My SVR has most of those properties (can do several
different return sequences including take the next interrupt) and does
not necessarily return whence the interrupt was taken.

This can be used to optimize the return path by avoiding returning from
an interrupt only to immediately take a priority-1 software interrupt.

My 66000 SVR exits a current handler, but instead of returning to the interrupted thread, it checks for any other interrupt disturbances
and if it finds one of higher priority than the interrupted thread, it
does the higher priority one(s) first, leaving the interrupted thread
for later.

SW does not have to look. SW just has to send DPCs/softIRQs as MSI-X
messages to the interrupt table of its choice. So, setting up a DPC/
softIRQ requires storing some data in a SW controlled place and manner,
and performing a single ST to the interrupt aperture to enQueue the
message at chosen priority and privilege, to be serviced by chosen
handler.

Should a higher priority thread become pending while SVR is in progress,
the higher priority thread will receive control before the first inst-
ruction of the mis-receiving thread is performed.

As far as you have explained these things to me, I see no race
conditions
in the architected means.

Perhaps not for your approach but I'm looking at other optimizations
that might introduce them. One was optimizing the common return path:

It is currently standing at 2 instructions--an RET from ISR back to its dispatcher, followed immediately by a SVR.

Before a supervisor return starts to reload the saved register set
it tests if a DPC is pending and about to generate a software interrupt,
and if so jumps back into the Dispatcher. This saves reloading the
registers
only to immediately take another interrupt, a pipeline drain and fill,
and resave the same registers.

Yes, yes, my SVR does that.

To do this optimization, before it starts to reload the registers
it tests the Interrupt Control Register (ICR) to check if it is about to trigger a SWI and if so adjusts the ICR and jumps into the Dispatcher. Otherwise it restores registers and does a Conditional Supervisor Return which reperforms the same test and can fall through if the test fails.

Because I do things in HW, I can start the RF reload (bring in the 5
cache lines of the thread) and while waiting for them to arrive, look
at the pending interrupts and abandon the return, ignoring the fetched
thread state; and proceed back to the top of Dispatcher. So, if SVR
finds more stuff to do, it can continue to use the RF it has.

But, because the next interrupt may be Hyper instead of Super (or
even vice versa) architecture states that HW uses the RF of the
current privilege level. This may require doing nothing (super->super)
or swapping RF (hyper->super or super->secure, from != to)

Architecturally, HW is always using the thread-state of core SW-stack
context pointers indexed by the privilege level.

This also requires that kernel/interrupt stacks be switched a certain
way,
which just so happens to be the same as the x86 way. That is, hardware
only
switches stacks if interrupted mode is User. This leaves it up to OS
software to decide which stack to use at what points inside the kernel.

Does x86 HW switch stacks when going from super to hyper or hyper to
Secure ?? like it does from user to super ??
--------
My 66000 has the property that a core runs a SW stack, each element
on the stack points at thread-state. Thread-state has all the control
registers needed to run a thread and a register file for each level
on the stack.

It is possible to program the system such that a (semi-trusted) user
(no privilege) is allowed to "take" his own interrupts. When doing
so, he really wants to use his own (non-privileged) stack.

It is also possible for a single interrupt table to hold interrupts
for any privilege level at any priority.
---------
You may ask why ? One of the goals here is to take the same number of
cycles to context switch between user processes as it does to switch
between different HyperVisors. Currently these are in the 1000 cycle
range (user->user) and 10,000 range for (Guest OS[1]->Guest OS[3]).
I want both of these down in the sub-100 range close; to >20 cycles
plus memory latency.

For example, one can context switch the user process by overwriting
its core software stack CR with the new process' Thread-state pointer
(and then when SVR happens the new process runs instead of the old
process) -- context switch is essentially 1 instruction. This happens
at Guest OS, and Hypervisor levels of the SW stack, too.

Supervisory software has the same path to figure out what to do
(next) and then once decided the code-path to "make it happen"
is tiny.

Also I'd save the interrupt context, the old RIP, old RSP and old
interrupt
status in hardware registers, not on the stack, and the interrupt vector
RIP address is calculated based on the priority. This eliminates all
memory
access from the exception and interrupt entry and exit transition
sequences,
and thereby eliminates page faults and memory error possibility and
cache access latency.

As you remain aware, all thread control registers have a known memory
address from which they are read and written, these do not go on any
stack. Along with the RF they occupy 5 sequential cache lines. HW
treats them (essentially) as a write back cache.

The only things on the supervisor stack is the original value in R0
(which I had to clobber to put the MSI-X message in. And a 2-bit
of the interrupted privilege level and a 4-bit token telling SVR
what kind of stack it is dealing with {Interrupt, exception, SVC}.)
{{Looking at this now, I could probably get rid of R0 on the stack))

One of the reasons I want HW doing these things, is HW strips off
bits SW is not supposed to be looking at. It is not clear is even
supervisory SW can be so trusted--witness we have (essentially
unprivileged) units of SW that do not even want GuetOS to look at
their data (banking applications, video, rented audio, ...). They
want GuestOS to perform the I/O but not look at any of the data.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 24 Mar 2025 18:02:25 +0000, Stefan Monnier wrote:

MitchAlsup1 [2025-03-24 17:36:28] wrote:

On Mon, 24 Mar 2025 12:37:13 +0000, Dan Cross wrote:

Consider something as simple as popping an item off of the front
of a queue and inserting it into an ordered singly-linked list:

[...]

I have almost that in the documentation for my ATOMIC stuff::
The following code moves a doubly linked element from one place
in a concurrent data structure to another without any interested
3rd party being able to see that the element is now within the
CDS at any time::

Would your "ATOMIC stuff" really handle Dan's example, tho?
A key element in Dan's example if the "ordered singly-linked list",
i.e. you need to walk the list an unbounded number of steps until you
can find the insertion point, so I don't think you can do the whole
thing inside your ATOMIC stuff.

Technically, yes, you can put a search loop in an ATOOMIC event.
Whether you want to or not is a different story. My example
illustrated the ATOMIC manipulation of the event without a search.

In addition, if the search it long, code developer should either
to the search before the event, or grab a Mutex to prevent
interference during the search and rest of the critical region.

IOW, you'd have to somehow move the list-walk outside of the atomic
section.

Yes,

E.g. if you know elements are only ever removed from the tail of the
list, you can presumably walk the list outside of the ATOMIC stuff and
then do the "remove from the queue and insert into the list" atomically
since it's a small&finite number of steps (with a test to loop back to
the list-walk if someone else inserted or removed anything at that point
in the mean time).

Or maintain a tail pointer.

Stefan

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:

On 3/24/2025 11:49 AM, Dan Cross wrote:

In article <pzdEP.126362$f5K3.26821@fx36.iad>,
Scott Lurndal <slp53@pacbell.net> wrote:

cross@spitfire.i.gajendra.net (Dan Cross) writes:

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

My architecture has a mechanism to perform ATOMIC stuff over multiple >>>>> instruction time frames that has the property that a higher priority >>>>> thread which interferers with a lower priority thread, the HPT wins
and the LPT fails its ATOMIC event. It is for exactly this reason
that I drag priority through the memory hierarchy--so that real-time >>>>> things remain closer to real-time (no or limited priority inversions). >>>>

Without being able to see this in practice, it's difficult to
speculate as to how well it will actually work in real-world
scenarios. What is the scope of what's covered by this atomic
thing?

Sounds a lot like transactional memory. Something that has
yet to prove to be usable in the general case.

I understand that some mallocs have done it; McRT-Malloc from
Intel, if I'm not mistaken.

Consider something as simple as popping an item off of the front
of a queue and inserting it into an ordered singly-linked list:
In this case, I'm probably going to want to take a lock on the
queue, then lock the list, then pop the first element off of the
queue by taking a pointer to the head.

Which can be done with compare and exchange, atomically;
a lock may not be necessary.

The insert into an ordered list will likely require a
spin lock (or a reader-writer lock of some form).

I'm sure one could do a lockless pop using a cmp exchange, but I
wanted to a scenario where one would want to hold onto both
locks throughout the critical section for some reason.
I just don't see how this works in the proposed scenario.

You want to hold lock A while lock B us being used? That can be tricky.
Well, there is a locking order.

Architecturally, we implemented locks in the hardware in the Burroughs
V-Series mainframes. Each lock was assigned (by the programmer) a 'canonical lock number' (CLN) which was a four digit value between 0 and 9999. The
CPU would track the currently active CLN and fault any lock instruction
that attempted to acquire a lock with a CLN less than or equal to
the current CLN. Unlocks would fault if the locks were not released
in the reverse order. This guaranteed deadlock-free locking, but
complicated the programming - with lots of locks, assigning
the CLN to a particular lock was tricky. We used it in the operating
system (four-cpu system) very successfully.

There were similar instructions to implement condition variables
with wait and signal semantics.

A small microkernel was responsible for scheduling, if a lock
was already held, the thread would be added to a waiting list
and a runnable thread dispatched. microkernel interrupts were
relatively low cost compared with normal interrupts. A single
instruction was used to dispatch the next task (BRV - Branch
Virutal Reinstate).

When a lock was unlocked, and there was a pending waiter, the
instruction would trap to the microkernel to handle the case
and place the waiting thread on a runnable queue (by priority).

When a lock acquisition failed because another thread owned
the lock, the instruction would trap to the microkernel which
would dispatch the next runnable task.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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].

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. 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.

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:

|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.

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.

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)?

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

- Dan C.

References:

[Her08] Maurice Herlihy and Nir Shavit. 2008. _The Art of
Multiprocessor Programming_. Morgan Kaufmann, Burlington, MA.

[Vah96] Uresh Vahalia. 1996. _Unix Internals: The New
Frontiers_. Prentice Hall, Upper Saddle River, NJ.

[Vaj11] Andras Vajda. 2011. _Programming Many-Core Chips_.
Springer, New York, NY.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <vrsaro$1faj3$9@dont-email.me>,
Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:

On 3/24/2025 11:49 AM, Dan Cross wrote:

[snip]
I'm sure one could do a lockless pop using a cmp exchange, but I
wanted to a scenario where one would want to hold onto both
locks throughout the critical section for some reason.
I just don't see how this works in the proposed scenario.

You want to hold lock A while lock B us being used? That can be tricky.

Really? This happens all the time. Of course it can be tricky,
as concurrent programming always is, but it's incredibly normal.

Well, there is a locking order. Check out this older work of mine, multex:

https://groups.google.com/g/comp.lang.c++/c/sV4WC_cBb9Q/m/SkSqpSxGCAAJ

Not sure if this is relevant or not.

It doesn't appear to be; sorry.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

On Mon, 24 Mar 2025 18:02:25 +0000, Stefan Monnier wrote:

MitchAlsup1 [2025-03-24 17:36:28] wrote:

On Mon, 24 Mar 2025 12:37:13 +0000, Dan Cross wrote:

Consider something as simple as popping an item off of the front
of a queue and inserting it into an ordered singly-linked list:

[...]

I have almost that in the documentation for my ATOMIC stuff::
The following code moves a doubly linked element from one place
in a concurrent data structure to another without any interested
3rd party being able to see that the element is now within the
CDS at any time::

Would your "ATOMIC stuff" really handle Dan's example, tho?
A key element in Dan's example if the "ordered singly-linked list",
i.e. you need to walk the list an unbounded number of steps until you
can find the insertion point, so I don't think you can do the whole
thing inside your ATOMIC stuff.

Technically, yes, you can put a search loop in an ATOOMIC event.
Whether you want to or not is a different story. My example
illustrated the ATOMIC manipulation of the event without a search.

In addition, if the search it long, code developer should either
to the search before the event, or grab a Mutex to prevent
interference during the search and rest of the critical region.

The problem, as specified, excluded this idea that the list was
long.

The point was simply to show a scenario where your atomic
operation proposal breaks down, and where you might want to
disable interrupt delivery. The point wasn't to ask whether
the specific problem could be recast in a different way; it
probably can. The question was to ask whether your proposal
could support that specific problem. I don't see how it can.

IOW, you'd have to somehow move the list-walk outside of the atomic
section.

Yes,

E.g. if you know elements are only ever removed from the tail of the
list, you can presumably walk the list outside of the ATOMIC stuff and
then do the "remove from the queue and insert into the list" atomically
since it's a small&finite number of steps (with a test to loop back to
the list-walk if someone else inserted or removed anything at that point
in the mean time).

Or maintain a tail pointer.

There's no guarantee that the tail is the correct place to
insert the element, vis the order of the elements.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 24 Mar 2025 20:28:40 +0000, Dan Cross wrote:

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

On Mon, 24 Mar 2025 18:02:25 +0000, Stefan Monnier wrote:

MitchAlsup1 [2025-03-24 17:36:28] wrote:

On Mon, 24 Mar 2025 12:37:13 +0000, Dan Cross wrote:

Consider something as simple as popping an item off of the front
of a queue and inserting it into an ordered singly-linked list:

[...]

I have almost that in the documentation for my ATOMIC stuff::
The following code moves a doubly linked element from one place
in a concurrent data structure to another without any interested
3rd party being able to see that the element is now within the
CDS at any time::

Would your "ATOMIC stuff" really handle Dan's example, tho?
A key element in Dan's example if the "ordered singly-linked list",
i.e. you need to walk the list an unbounded number of steps until you
can find the insertion point, so I don't think you can do the whole
thing inside your ATOMIC stuff.

Technically, yes, you can put a search loop in an ATOOMIC event.
Whether you want to or not is a different story. My example
illustrated the ATOMIC manipulation of the event without a search.

In addition, if the search it long, code developer should either
to the search before the event, or grab a Mutex to prevent
interference during the search and rest of the critical region.

The problem, as specified, excluded this idea that the list was
long.

The point was simply to show a scenario where your atomic
operation proposal breaks down, and where you might want to
disable interrupt delivery.

My ATOMIC stuff allows for the construction, in SW, of pretty
much any ATOMIC primitive anyone would like. It is, in general,
not suited to guard critical regions, but to grab the lock which
does.

Most uses of My ATOMIC stuff is to grab/change/update data
that then guards various critical regions. More like a multi-
valued version of LDL-STC.

The point wasn't to ask whether
the specific problem could be recast in a different way; it
probably can. The question was to ask whether your proposal
could support that specific problem. I don't see how it can.

To the question posed, you should just grab the lock/mutex.

IOW, you'd have to somehow move the list-walk outside of the atomic
section.

Yes,

E.g. if you know elements are only ever removed from the tail of the
list, you can presumably walk the list outside of the ATOMIC stuff and
then do the "remove from the queue and insert into the list" atomically
since it's a small&finite number of steps (with a test to loop back to
the list-walk if someone else inserted or removed anything at that point >>> in the mean time).

Or maintain a tail pointer.

There's no guarantee that the tail is the correct place to
insert the element, vis the order of the elements.

If the element pointer updates and the tail pointer update are inside
one of my ATOMIC events, then you are sure that the tail pointer is
always pointing at the last element in the list (if there is one).

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 24 Mar 2025 20:11:46 +0000, 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:

-------------------

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:

|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.

My 66000 ATOMIC stuff is designed such that if control has to leave
the ATOMIC event, all HW knowledge of being in that event disappears
and IP is modified (prior to control transfer) such that upon return
SW knows the event failed (or never started), and that no update of participating data in the event ever becomes visible.

HW can do this with address-based events, but not with data-based
events. LDL-STC are address-based events used to manipulate data-
based events. Mine just allow more LDs and STs in the event than 1.

So, if you want the property whereby the lock disappears on any
control transfer out of the event {exception, interrupt, SVC, SVR, ...};
then you want to use my ATOMIC stuff; otherwise, you can use the
normal ATOMIC primitives everyone and his brother provide.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

On Mon, 24 Mar 2025 20:11:46 +0000, 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:

-------------------

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:

|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.

My 66000 ATOMIC stuff is designed such that if control has to leave
the ATOMIC event, all HW knowledge of being in that event disappears
and IP is modified (prior to control transfer) such that upon return
SW knows the event failed (or never started), and that no update of >participating data in the event ever becomes visible.

HW can do this with address-based events, but not with data-based
events. LDL-STC are address-based events used to manipulate data-
based events. Mine just allow more LDs and STs in the event than 1.

So, if you want the property whereby the lock disappears on any
control transfer out of the event {exception, interrupt, SVC, SVR, ...};
then you want to use my ATOMIC stuff; otherwise, you can use the
normal ATOMIC primitives everyone and his brother provide.

I definitely do Not want that property. Having a lock
"disappear" on delivery of an interrupt seems like it would be a
great way to introduce silent corruption.

If your atomic primitives are not sufficient to cover an entire
critical section, as I believe we have established, and are
mostly intended to be used for building concurrency primitives
like locks, then I expect that software would take the lock, see
that it succeeded, and enter the critical section. If at that
point the lock were silently discarded on receipt of an
interrupt, then potentially some other thread could subsequently
take the lock, enter the critical section, and observe a data
structure in an inconsistent state (leading to a crash in the
best case). This is precisely the sort of thing we build mutual
exclusion primitives to wrap around critical sections to avoid.

If, on the other hand, the atomic primitives are just meant for
the spin loop, then I don't really see how that's all that
useful compared to LL/SC. And you still need some way to ensure
that the critical section is not interrupted.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

On Mon, 24 Mar 2025 20:28:40 +0000, Dan Cross wrote:

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

On Mon, 24 Mar 2025 18:02:25 +0000, Stefan Monnier wrote:

MitchAlsup1 [2025-03-24 17:36:28] wrote:

On Mon, 24 Mar 2025 12:37:13 +0000, Dan Cross wrote:

Consider something as simple as popping an item off of the front
of a queue and inserting it into an ordered singly-linked list:

[...]

I have almost that in the documentation for my ATOMIC stuff::
The following code moves a doubly linked element from one place
in a concurrent data structure to another without any interested
3rd party being able to see that the element is now within the
CDS at any time::

Would your "ATOMIC stuff" really handle Dan's example, tho?
A key element in Dan's example if the "ordered singly-linked list",
i.e. you need to walk the list an unbounded number of steps until you
can find the insertion point, so I don't think you can do the whole
thing inside your ATOMIC stuff.

Technically, yes, you can put a search loop in an ATOOMIC event.
Whether you want to or not is a different story. My example
illustrated the ATOMIC manipulation of the event without a search.

In addition, if the search it long, code developer should either
to the search before the event, or grab a Mutex to prevent
interference during the search and rest of the critical region.

The problem, as specified, excluded this idea that the list was
long.

The point was simply to show a scenario where your atomic
operation proposal breaks down, and where you might want to
disable interrupt delivery.

My ATOMIC stuff allows for the construction, in SW, of pretty
much any ATOMIC primitive anyone would like. It is, in general,
not suited to guard critical regions, but to grab the lock which
does.

Ok, that's good to understand.

Most uses of My ATOMIC stuff is to grab/change/update data
that then guards various critical regions. More like a multi-
valued version of LDL-STC.

I don't see how constructing the primitive that way is terribly
useful compared to just issuing multiple load-locked/store-cond
instructions; in particular, it doesn't seem like the sort of
thing that composes well: every sequence that uses it must be
coded to use it, explicitly, instead of just nesting calls to
"lock".

The point wasn't to ask whether
the specific problem could be recast in a different way; it
probably can. The question was to ask whether your proposal
could support that specific problem. I don't see how it can.

To the question posed, you should just grab the lock/mutex.

That's fine, then. But this is another example of a place where
one probably wants to disable interrupts while in the critical
section, to avoid being preempted while holding the lock.

IOW, you'd have to somehow move the list-walk outside of the atomic
section.

Yes,

E.g. if you know elements are only ever removed from the tail of the
list, you can presumably walk the list outside of the ATOMIC stuff and >>>> then do the "remove from the queue and insert into the list" atomically >>>> since it's a small&finite number of steps (with a test to loop back to >>>> the list-walk if someone else inserted or removed anything at that point >>>> in the mean time).

Or maintain a tail pointer.

There's no guarantee that the tail is the correct place to
insert the element, vis the order of the elements.

If the element pointer updates and the tail pointer update are inside
one of my ATOMIC events, then you are sure that the tail pointer is
always pointing at the last element in the list (if there is one).

But that's irrelevant. The goal is to insert into a sorted list
and, again, the last element is not necessarily the correct
place to insert (or append).

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 24 Mar 2025 23:45:49 +0000, Dan Cross wrote:

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

On Mon, 24 Mar 2025 20:11:46 +0000, 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:

-------------------

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:

|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.

My 66000 ATOMIC stuff is designed such that if control has to leave
the ATOMIC event, all HW knowledge of being in that event disappears
and IP is modified (prior to control transfer) such that upon return
SW knows the event failed (or never started), and that no update of >>participating data in the event ever becomes visible.

HW can do this with address-based events, but not with data-based
events. LDL-STC are address-based events used to manipulate data-
based events. Mine just allow more LDs and STs in the event than 1.

So, if you want the property whereby the lock disappears on any
control transfer out of the event {exception, interrupt, SVC, SVR, ...}; >>then you want to use my ATOMIC stuff; otherwise, you can use the
normal ATOMIC primitives everyone and his brother provide.

I definitely do Not want that property. Having a lock
"disappear" on delivery of an interrupt seems like it would be a
great way to introduce silent corruption.

It means that if a thread owning a lock is interrupted, that
thread gives the lock back--so there is no priority inversion
and no lock-starvation. Associated with the give back, and the
IP of the interrupted thread no longer points inside the
critical section.

Nothing gets lost.

{{Perhaps disappear was a poorly chosen word.}}

If your atomic primitives are not sufficient to cover an entire
critical section, as I believe we have established, and are
mostly intended to be used for building concurrency primitives
like locks, then I expect that software would take the lock, see
that it succeeded, and enter the critical section.

If at that
point the lock were silently discarded on receipt of an
interrupt,

At this point your thread in not IN the critical section !!

The closest you can be is at the first instruction beginning
an ATOMIC event (the never happened case) or you can also
be at the point where you KNOW that some other interfered
with your actions, and that they saw a completely consistent
state--now it is your turn (again) observing a completely
consistent but new state.

then potentially some other thread could subsequently
take the lock,

Since you are not in the critical section, you don't care.
No critical data has been modified, there is no inconsistent
state to be observed; and YOUR Instruction Pointer is not
pointing into instructions within the ATOMIC event !!

enter the critical section, and observe a data
structure in an inconsistent state (leading to a crash in the
best case).

There is no inconsistent state--in rather the same way a core backs
up a branch mispredict, the core backs up the ATOMIC event to appear
as if it never even started !!

This is precisely the sort of thing we build mutual
exclusion primitives to wrap around critical sections to avoid.

And also why those primitives give rise to priority inversion
and lock-starvation.

If, on the other hand, the atomic primitives are just meant for
the spin loop, then I don't really see how that's all that
useful compared to LL/SC.

Any number of respected people have ask for a pipelined LL-SC;
where one can LL multiple datums and later SC multiple datums.
This is what ESM can provide.

And you still need some way to ensure
that the critical section is not interrupted.

Just a way to detect if it happened; and if it happens;
means to back upto a point where it does not matter if
interference happened "right there"--that is: outside of
a critical section.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

It means that if a thread owning a lock is interrupted, that
thread gives the lock back--so there is no priority inversion
and no lock-starvation. Associated with the give back, and the
IP of the interrupted thread no longer points inside the
critical section.

I think the discussion is a bit confusing because we have 2 different
notions of "critical section" at play, here:

Mitch's ESM/ATOMIC provides a kind of middle-point between LL/SC and transactional memory, which handles only "very small" atomic sequences
(IIUC there's no limit to the number of instructions, but there's
a limit of 8 data cache lines touched).

A "critical section" can refer to such an atomic sequence. But that can
be used only for critical sections of limited size, so as you point out
it can't really be composed. For this reason, as Mitch said, it's meant
mostly as a tool to implement synchronization primitives (lock,
semaphore, read/write lock, younameit), tho it seems sufficiently
flexible that it should also be usable for some lock-free operations.

A "critical section" can also refer to the arbitrary code protected by
a lock, where the lock primitives would be presumably themselves
implemented using ESM and would then each be made of their own "critical section".

The small ATOMIC-style critical sections don't hold locks. Instead they
use an optimistic-synchronization approach, which is why they don't
suffer from priority inversion.

The lock-based critical sections you can build on top of the ATOMIC-style critical sections, OTOH, are just your usual lock-based critical
sections: the fact that they're built out of ESM primitives rather than
out of test&set or LL/SC doesn't really make any difference: they can
indeed suffer from priority inversion.


Stefan

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Tue, 18 Mar 2025 1:34:40 +0000, Scott Lurndal wrote:

mitchalsup@aol.com (MitchAlsup1) writes:

On Mon, 17 Mar 2025 18:33:09 +0000, EricP wrote:

Interrupt latency is dependent on executing instructions,
Lowest waste of power

But note: In most cases, it already took the interrupt ~150 nanoseconds
to arrive at the interrupt service port. 1 trip from device to DRAM >>(possibly serviced by L3), 1 trip from DRAM back to device, 1 tip from >>device to interrupt service port; and 4 DRAM (or L3) accesses to log >>interrupt into table.

How do you handle timer interrupts? Those are generally not
message based, but rather internal signals within the core that
raise an interrupt (perhaps coordinating with the interrupt controller
for priority, security state, and enable bit). These are generally
wired (and the enables/state/priority are flops) for low latency.

Wired interrupts are converted into MSI-X interrupts under control
of INTk->MSI-X control registers in HostBridge. Then these
smell just like any other interrupt and take similar paths.

There will generally be at least one general purpose timer per
core plus any watchdog timers.

There are 8 performance counting "things" per major block on die.
major block include {core[*], L2[*], interconnect, L3[*], DRAM[*]
config[*] and MMI/O[*]}.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Robert Finch wrote:

On 2025-03-17 2:33 p.m., EricP wrote:

Another problem is what does the core do with the in flight instructions.


Method 2 pipelines the switch by injecting the interrupt request at
Fetch.
Decode converts the request to a special uOp that travels down the IQ
to Retire and allows all the older work to complete.
This is more complex as it requires a two phase hand-off from the
Interrupt Control Unit (ICU) to the core as a branch mispredict in the
in flight instructions might cause a tentative interrupt acceptance to
later
be withdrawn.

Oh my, I forgot.
Method 2 will be used as it is desired to able to insert either an instruction at the fetch stage or a vector address.

The ICU believes the core is in a state to accept a higher priority
interrupt. It sends a request to core, which checks its current state and
sends back an immediate INT_ACK if _might_ accept and stalls Fetch, or
a NAK.
When the special uOp reaches Retire, it sends a signal to Fetch which
then sends an INT_ACCEPT signal to ICU to complete the handoff.
If a branch mispredict occurs that causes interrupts to be disabled,
then Fetch sends an INT_REJECT to ICU, and unstalls its fetching.
(Yes that is not optimal - make it work first, make it work well second.)

This also raises a question about what the ICU is doing during this
long latency handoff. One wouldn't want ICU to sit idle so it might
have to manage the handoff of multiple interrupts to multiple cores
at the same time, each as its own little state machine.

One should see that this decision on how the core handles the
handoff has a large impact on the design complexity of the ICU.

Personally, I would use method 1 first to get something working
then if this is OoO think about getting fancy with method 2.

Would it not be rare for this to occur? If so, I think the pipeline
could just be flushed from the int disabling instruction on. Then the interrupted address recorded as the int disabling instruction. <- this requires identification of an int disabling instruction though. It might
just be a store to a specific I/O address, therefore a special store
opcode to make it easy to detect?

It likely is rare but the possibility that the existing instructions,
a branch mispredict or an exception throw, could retroactively change
the state of the interrupt enable flag to disabled creates this
Window of Uncertainty (WoU) that is the length of the pipeline.

Unless one can find a way to make WoU go away the ICU needs to deal
with the possibility that there could be hundreds of clocks between
when ICU asks a core if it can accept an interrupt and when the core does.

I had a few ideas walking in the park yesterday. I had been assuming that
when an exception is delivered that it would also automatically disable interrupts. That may not be a good idea as it means that any instruction
that can throw an exception could cause this retroactive disabling.

If I remove that exception side effect then the only things that can
manipulate the core's master Interrupt Enable flag are the enable INTEN
and disable INTDI instructions, and the actual delivery of an interrupt.
And those three things can be tracked with a counter in Decode as they
move down the pipeline to Retire. If the counter >0 then there is a
flag change in flight and we don't accept a new interrupt. When count == 0
and Interrupt Enable flag == 1 then core accepts interrupts, which are
injected at Decode and cause a light weight purge of the Fetch buffer.

Another pipeline issue is Privileged Control Register (PCR) reads and writes. PCR's don't behave like general registers in that they are not renamed,
and in general operations cannot be replayed or performed out of order.
They behave more like atomic stores that must be performed at Retire
and must not be bypassed by any memory and other PCR ops. (This is why
many of the x86/x64 MSR ops are serialized with a pipeline drain.)

This affects what it can do with PCR inside the WoU if it causes a state
change that cannot be undone, for example, reading the interrupt data FIFO.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 17 Mar 2025 21:49:18 +0000, MitchAlsup1 wrote:

On Mon, 17 Mar 2025 18:33:09 +0000, EricP wrote:

Michael S wrote:

On Mon, 17 Mar 2025 13:38:12 GMT
scott@slp53.sl.home (Scott Lurndal) wrote:

------------------

The problem Robert is talking about arises when there are many
interrupt source and many target CPUs.
The required routing/prioritization/acknowledgment logic (at least a
naive logic I am having in mind) would be either non-scalable or
relatively complicated. Process of selection for the second case will
take multiple cycles (I am thinking about ring).

Another problem is what does the core do with the in flight
instructions.

Method 1 is simplest, it injects the interrupt request at Retire
as that's where the state of everything is synchronized.
The consequence is that, like exceptions, the in flight instructions all
get purged, and we save the committed RIP, RSP and interrupt control
word.
While that might be acceptable for a 5 stage in-order pipeline,
it could be pretty expensive for an OoO 200+ instruction queue
potentially tossing hundreds of cycles of near finished work.

Lowest interrupt Latency
Highest waste of power (i.e., work)

Method 2 pipelines the switch by injecting the interrupt request at
Fetch.
Decode converts the request to a special uOp that travels down the IQ
to Retire and allows all the older work to complete.
This is more complex as it requires a two phase hand-off from the
Interrupt Control Unit (ICU) to the core as a branch mispredict in the
in flight instructions might cause a tentative interrupt acceptance to
later be withdrawn.

Interrupt latency is dependent on executing instructions,
Lowest waste of power

Highest chance of mucking it all up

But note: In most cases, it already took the interrupt ~150 nanoseconds
to arrive at the interrupt service port. 1 trip from device to DRAM
(possibly serviced by L3), 1 trip from DRAM back to device, 1 tip from
device to interrupt service port; and 4 DRAM (or L3) accesses to log interrupt into table.

Also, in most cases, the 200-odd instructions in the window will finish
in 100-cycles or as little as 20ns--but if the FDIV unit is saturated, interrupt latency could be as high as 640 cycles and as long as 640ns.

There is the other issue adding complexity to method 2,
The instructions in the window may raise exceptions.

The general rule is that the instruction raising the first exception
has its address in IP, and then the retire logic has to flush subseq-
uent instructions until it arrives at the first instruction of the
Interrupt dispatcher.

The exception will be handled when control returns from interruption.

The ICU believes the core is in a state to accept a higher priority
interrupt. It sends a request to core, which checks its current state
and
sends back an immediate INT_ACK if _might_ accept and stalls Fetch, or a
NAK.

In My 66000, ICU knows nothing about the priority level (or state)
of any core in the system. Instead, when a new higher priority
interrupt is raised, the ISP broadcasts a 64-bit mask indicating
which priority levels in the interrupt table have pending inter-
rupts with an MMI/O message to the address of the interrupt table.

All cores monitoring that interrupt table capture the broadcast,
and each core decides to negotiate for an (not that) interrupt
by requesting the highest priority interrupt from the table.

When the request returns, and it is still at a higher priority
than the core is running, core performs interrupt control transfer.
If the interrupt is below the core's priority it is returned to
ISP as if NAKed.

Prior to interrupt control transfer, core remains running what-
ever it was running--and all the interrupt stuff is done by state
machines at the edge of the core and the L3/DRAM controller.

When the special uOp reaches Retire, it sends a signal to Fetch which
then sends an INT_ACCEPT signal to ICU to complete the handoff.
If a branch mispredict occurs that causes interrupts to be disabled,
then Fetch sends an INT_REJECT to ICU, and unstalls its fetching.
(Yes that is not optimal - make it work first, make it work well
second.)

This also raises a question about what the ICU is doing during this
long latency handoff. One wouldn't want ICU to sit idle so it might
have to manage the handoff of multiple interrupts to multiple cores
at the same time, each as its own little state machine.

One must assume that ISP is capable of taking a new interrupt
from a device every 5-ish cycles and interrupt handoff is in the
range of 50 cycles, and that each interrupt could be to a different
interrupt table.

My 66000 ISP treats successive requests to any one table as strongly
ordered, and requests to different tables as completely unordered.

One should see that this decision on how the core handles the
handoff has a large impact on the design complexity of the ICU.

I did not "see" that in My 66000's interrupt architecture. The ISP
complexity is fixed, and the core's interrupt negotiator is a small
state machine (~10-states).

ISP essentially performs 4-5 64-bit memory accesses, and possibly
1 MMI/O 64-bit broadcast on arrival of MSI-X interrupt. Then if
a core negotiates, it performs 3 more memory accesses per negotiator.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Tue, 18 Mar 2025 18:51:57 +0000, EricP wrote:

Robert Finch wrote:

On 2025-03-17 2:33 p.m., EricP wrote:

----------------

This also raises a question about what the ICU is doing during this
long latency handoff. One wouldn't want ICU to sit idle so it might
have to manage the handoff of multiple interrupts to multiple cores
at the same time, each as its own little state machine.

One should see that this decision on how the core handles the
handoff has a large impact on the design complexity of the ICU.

Personally, I would use method 1 first to get something working
then if this is OoO think about getting fancy with method 2.

Would it not be rare for this to occur? If so, I think the pipeline
could just be flushed from the int disabling instruction on. Then the
interrupted address recorded as the int disabling instruction. <- this
requires identification of an int disabling instruction though. It might
just be a store to a specific I/O address, therefore a special store
opcode to make it easy to detect?

It likely is rare but the possibility that the existing instructions,

Which is rare:
executing 200 instructions without an exception ?
OR
executing 200 instructions without a mispredict ?

The former is fairly rare, the later is not so rare.

a branch mispredict or an exception throw, could retroactively change
the state of the interrupt enable flag to disabled creates this
Window of Uncertainty (WoU) that is the length of the pipeline.

All the more reasons that the very vast majority of interrupts and
exceptions do not have to disable more of their kind or their
opposite.

In My 66000 interrupt architecture, the very first instruction in the
interrupt dispatcher can take a higher priority interrupt-----the
page fault handler in Guest OS can take a page fault in HyperVisor
MMU tables, without any special precautions or code sequences.

Unless one can find a way to make WoU go away the ICU needs to deal
with the possibility that there could be hundreds of clocks between
when ICU asks a core if it can accept an interrupt and when the core
does.

The window will always exist--so, the best one can do is eliminate
the core's sensitivity to the WoU.

I had a few ideas walking in the park yesterday. I had been assuming
that
when an exception is delivered that it would also automatically disable interrupts. That may not be a good idea as it means that any instruction
that can throw an exception could cause this retroactive disabling.

My 66000 simply defines that this cannot happen::
Exceptions do not alter the behavior of interrupts;
Interrupts do not alter the behavior of exceptions.

If I remove that exception side effect then the only things that can manipulate the core's master Interrupt Enable flag are the enable INTEN
and disable INTDI instructions, and the actual delivery of an interrupt.

Let's postulate we have a core running at low priority and its
instruction
stream raises an exception. That exception delivers control at that same
low priority to the exception handler.

Do you want any of this to slow down a high priority interrupt ??
even by 20-50 cycles ??

I submit the answer is:: NO !

And those three things can be tracked with a counter in Decode as they
move down the pipeline to Retire. If the counter >0 then there is a
flag change in flight and we don't accept a new interrupt. When count ==
0
and Interrupt Enable flag == 1 then core accepts interrupts, which are injected at Decode and cause a light weight purge of the Fetch buffer.

Once you start adding mechanisms to track this and that and to deal
with different this and that--you should receive an indication that
you are not on the correct path.

{{Hint: make the problem go away for all time}}

Another pipeline issue is Privileged Control Register (PCR) reads and
writes.
PCR's don't behave like general registers in that they are not renamed,
and in general operations cannot be replayed or performed out of order.

While I have a way to read and write control registers with varying
privilege, a thread at privilege[k] can only read and write his own
CRs and those of the core on which it is currently running.

If you want to read/write control register data for lower privilege
threads, you can access the pointer in core.CR and then access
thread-state directly in memory. By the time control returns to the
low privilege level, all CRs will have been made resident in core.

That is the per thread Program-Status-Line is treated like a write
back cache.

They behave more like atomic stores that must be performed at Retire
and must not be bypassed by any memory and other PCR ops. (This is why
many of the x86/x64 MSR ops are serialized with a pipeline drain.)

By converting them to real memory accesses, the problem solves itself.

This affects what it can do with PCR inside the WoU if it causes a state change that cannot be undone, for example, reading the interrupt data
FIFO.

Since the device is accessed through MMI/O space, and since My 66000
demands sequential consistency for MMI/O accesses, the LD of the
interrupt data FIFO cannot leave the confines of the core until
all pending memory references from the interrupted thread have
"been performed".

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Tue, 18 Mar 2025 21:59:51 +0000, Robert Finch wrote:

On 2025-03-18 2:51 p.m., EricP wrote:

----------------

Would it not be rare for this to occur? If so, I think the pipeline
could just be flushed from the int disabling instruction on. Then the
interrupted address recorded as the int disabling instruction. <- this
requires identification of an int disabling instruction though. It
might just be a store to a specific I/O address, therefore a special
store opcode to make it easy to detect?

It likely is rare but the possibility that the existing instructions,
a branch mispredict or an exception throw, could retroactively change
the state of the interrupt enable flag to disabled creates this
Window of Uncertainty (WoU) that is the length of the pipeline.

Unless one can find a way to make WoU go away the ICU needs to deal
with the possibility that there could be hundreds of clocks between
when ICU asks a core if it can accept an interrupt and when the core
does.

I had a few ideas walking in the park yesterday. I had been assuming
that
when an exception is delivered that it would also automatically disable
interrupts. That may not be a good idea as it means that any instruction
that can throw an exception could cause this retroactive disabling.

If I remove that exception side effect then the only things that can
manipulate the core's master Interrupt Enable flag are the enable INTEN
and disable INTDI instructions, and the actual delivery of an interrupt.
And those three things can be tracked with a counter in Decode as they
move down the pipeline to Retire. If the counter >0 then there is a
flag change in flight and we don't accept a new interrupt. When count ==
0
and Interrupt Enable flag == 1 then core accepts interrupts, which are
injected at Decode and cause a light weight purge of the Fetch buffer.

Seems like it could work. There are difficulties using counters with the
Q+ ISA as multiple interrupt enable bits could be manipulated at the
same time. One interrupt may be enabled and another one disabled by the
same instruction.

I want to address the elephant in the room::

Why disable interrupts AT ALL !!

When running at any privilege, do you not want to accept an interrupt
at higher priority with as little delay as possible ??

Does Interrupt Disable help in this goal ??

Is there a SANE way to avoid disabling of interrupts ??

So, what does it take to take (sic) interrupts without disabling
interrupts ?? It takes the interrupt control transfer sequence
to leave the core in an interruptible state ! {{Same for exceptions}}

My 66000 interrupt negotiator will not negotiate for interrupts
at the same or lower priority the core is currently running.
This is done by using the 6-bit priority as a less-than mask
generator across the current-raised 64-bit control register.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Wed, 19 Mar 2025 0:39:04 +0000, Robert Finch wrote:

On 2025-03-18 6:49 p.m., MitchAlsup1 wrote:
<snip>

I am not following this. I think there needs to be some way to disable interrupts that should not be occurring. I think a diagram would help. +-------+--------+-----+--------+
| fetch | decode | ... | retire |
+-------+--------+-----+--------+
| IRQ^ | .... | ... | INTDI |
+-------+--------+-----+--------+

These two are happening at the same time.
The INTDI (interrupt disable) should effectively
cause the IRQ to be ignored.
Instructions that are fetched after the IRQ
are relying on interrupts disabled.

a) there is a list of at least 7 places where interrupts can be disabled ..between the device[j] a core[k]
b) what I am addressing is disablement at the core.
c) any yes, I do have a way of disabling interrupts, but is generally ..reserved for nasty things like a system panic.
d) the typical "I'm done with req[k]" needs no interrupt disable.
e) certain architectures can choose to disable interrupts for a short
while
f) others can architect a system that does not need disablement.

Now, back to your ASCII-art::

If there is a interrupt disable instruction (or side effect) in the
pipeline, as seen at DECODE, the disable has already happened, and
the pipeline is just waiting for the event to become manifest. This
is that window of uncertainty.

Suppose there is an interrupt disable instruction in the pipeline that
has not been performed yet

As seen at DECODE it has already happened;
as seen at RETIRE it remains pending.

Different ends of the pipeline are allowed/required to know things
differently.

(they are not done until the retire stage in
Q+). So, interrupts are enabled when detected at an earlier pipeline
stage (fetch). It turns out that the interrupt should not have been
fetched from the interrupt queue as interrupts are about to be disabled
by an earlier instruction.

This is that tangled web some weave.

I think this matters because of the purpose
of disabling the interrupts. There could be other instructions after the
int disable including yet to be fetched instructions relying on the fact
that interrupts are disabled.

If one bothers to disable core from seeing interrupts in My 66000,
The disable happens in program order, and is made to appear as if in
program order.

Likewise, if one enables core interrupts, the instruction following the
enable can take an interrupt (before it executes).

But you seem to be missing the point--it is possible (and I would argue beneficial) to architect your interrupts such that interrupt disable is
not necessary >98& of the time. You do it when required, you don't when
you can get away with out it.

Completion interrupts ("I'm done with blah[k]") should not need to DIs.

If the interrupt did not affect other aspects of the instruction being interrupted (it maybe just sets an interrupt bit in the pipeline
register), I think it might be possible to handle this by having an
interrupt enable flag in the pipeline registers.

If you head in that direction, you need to transfer control to the ISR
at the front of the pipeline, so that a mispredicted branch backs-up
to the 1st instruction in ISR, and then throw the window away with the
normal logic, leaving IP pointing at the branch or branch target.

That way when the
interrupt is disabled, all the interrupt enable flags in the pipeline registers could be cleared. When the disabled interrupt reaches retire,
it would have to be logged (queued) so that it can be executed when interrupts are re-enabled.

It is for all these reason, I counsel you to device a system where the
typical interrupt needs to disable nothing.

It gets worse with branches involved.

Which is why you want greater orthogonality wrt interrupts and IE-bit.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <vrt2sb$27c13$2@dont-email.me>,
Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:

On 3/24/2025 1:14 PM, Dan Cross wrote:

In article <vrsaro$1faj3$9@dont-email.me>,
Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:

On 3/24/2025 11:49 AM, Dan Cross wrote:

[snip]
I'm sure one could do a lockless pop using a cmp exchange, but I
wanted to a scenario where one would want to hold onto both
locks throughout the critical section for some reason.
I just don't see how this works in the proposed scenario.

You want to hold lock A while lock B us being used? That can be tricky.

Really? This happens all the time. Of course it can be tricky,
as concurrent programming always is, but it's incredibly normal.

Locking order comes into play here. Uggg... I have seen nightmare code
that was using recursion as well... It deadlocked at a certain depth,
only under the right conditions. The locking order was not properly >respected...

Well, of course it does. But it's still something that people
do all the time.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <vrt323$27c13$3@dont-email.me>,
Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:

On 3/24/2025 7:02 PM, Chris M. Thomasson wrote:

On 3/24/2025 1:14 PM, Dan Cross wrote:

In article <vrsaro$1faj3$9@dont-email.me>,
Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:

On 3/24/2025 11:49 AM, Dan Cross wrote:

[snip]
I'm sure one could do a lockless pop using a cmp exchange, but I
wanted to a scenario where one would want to hold onto both
locks throughout the critical section for some reason.
I just don't see how this works in the proposed scenario.

You want to hold lock A while lock B us being used? That can be tricky. >>>

Really?  This happens all the time.  Of course it can be tricky,
as concurrent programming always is, but it's incredibly normal.

Locking order comes into play here. Uggg... I have seen nightmare code
that was using recursion as well... It deadlocked at a certain depth,
only under the right conditions. The locking order was not properly
respected...

A thread would take mtxA, then mtxB, while another would take mtxB, then >mtxA. Deadlock city is going to be visited rather soon...

Yeah, so don't do that. :-)

I can whack myself in the head with a ballpeen hammer, too. It
is better if I do not.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <vrt37r$27c13$4@dont-email.me>,
Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:

On 3/24/2025 1:28 PM, Dan Cross wrote:

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

On Mon, 24 Mar 2025 18:02:25 +0000, Stefan Monnier wrote:

MitchAlsup1 [2025-03-24 17:36:28] wrote:

On Mon, 24 Mar 2025 12:37:13 +0000, Dan Cross wrote:

Consider something as simple as popping an item off of the front
of a queue and inserting it into an ordered singly-linked list:

[...]

I have almost that in the documentation for my ATOMIC stuff::
The following code moves a doubly linked element from one place
in a concurrent data structure to another without any interested
3rd party being able to see that the element is now within the
CDS at any time::

Would your "ATOMIC stuff" really handle Dan's example, tho?
A key element in Dan's example if the "ordered singly-linked list",
i.e. you need to walk the list an unbounded number of steps until you
can find the insertion point, so I don't think you can do the whole
thing inside your ATOMIC stuff.

Technically, yes, you can put a search loop in an ATOOMIC event.
Whether you want to or not is a different story. My example
illustrated the ATOMIC manipulation of the event without a search.

In addition, if the search it long, code developer should either
to the search before the event, or grab a Mutex to prevent
interference during the search and rest of the critical region.

The problem, as specified, excluded this idea that the list was
long.

The point was simply to show a scenario where your atomic
operation proposal breaks down, and where you might want to
disable interrupt delivery. The point wasn't to ask whether
the specific problem could be recast in a different way; it
probably can. The question was to ask whether your proposal
could support that specific problem. I don't see how it can.

IOW, you'd have to somehow move the list-walk outside of the atomic
section.

Yes,

E.g. if you know elements are only ever removed from the tail of the
list, you can presumably walk the list outside of the ATOMIC stuff and >>>> then do the "remove from the queue and insert into the list" atomically >>>> since it's a small&finite number of steps (with a test to loop back to >>>> the list-walk if someone else inserted or removed anything at that point >>>> in the mean time).

Or maintain a tail pointer.

There's no guarantee that the tail is the correct place to
insert the element, vis the order of the elements.

https://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html

If you go back and review the thread, you'd see that the problem
is to remove an element from a queue, and insert it into an
ordered list. This part of the discussion is concerning the
latter operation.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

On Mon, 24 Mar 2025 23:45:49 +0000, Dan Cross wrote:

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

[snip]
My 66000 ATOMIC stuff is designed such that if control has to leave
the ATOMIC event, all HW knowledge of being in that event disappears
and IP is modified (prior to control transfer) such that upon return
SW knows the event failed (or never started), and that no update of >>>participating data in the event ever becomes visible.

HW can do this with address-based events, but not with data-based
events. LDL-STC are address-based events used to manipulate data-
based events. Mine just allow more LDs and STs in the event than 1.

So, if you want the property whereby the lock disappears on any
control transfer out of the event {exception, interrupt, SVC, SVR, ...}; >>>then you want to use my ATOMIC stuff; otherwise, you can use the
normal ATOMIC primitives everyone and his brother provide.

I definitely do Not want that property. Having a lock
"disappear" on delivery of an interrupt seems like it would be a
great way to introduce silent corruption.

It means that if a thread owning a lock is interrupted, that
thread gives the lock back--so there is no priority inversion
and no lock-starvation. Associated with the give back, and the
IP of the interrupted thread no longer points inside the
critical section.

Nothing gets lost.

Perhaps we're not clear on what a "lock" is. Here, I'm
referring to a mutual exclusion primitive that I use to protect
entry into a critical section. You seem to be talking about
something else.

{{Perhaps disappear was a poorly chosen word.}}

If your atomic primitives are not sufficient to cover an entire
critical section, as I believe we have established, and are
mostly intended to be used for building concurrency primitives
like locks, then I expect that software would take the lock, see
that it succeeded, and enter the critical section.

If at that
point the lock were silently discarded on receipt of an
interrupt,

At this point your thread in not IN the critical section !!

Why not? I successfully acquired a lock, no? What else do you
propose I must do to enter the critical section?

The closest you can be is at the first instruction beginning
an ATOMIC event (the never happened case) or you can also
be at the point where you KNOW that some other interfered
with your actions, and that they saw a completely consistent
state--now it is your turn (again) observing a completely
consistent but new state.

Here's a bit of my earlier message that didn't get quoted in
your reply:

|If, on the other hand, the atomic primitives are just meant for
|the spin loop, then I don't really see how that's all that
|useful compared to LL/SC. And you still need some way to ensure
|that the critical section is not interrupted.

It seems like you're saying that the "ATOMIC event" is just for
the spin loop.

then potentially some other thread could subsequently
take the lock,

Since you are not in the critical section, you don't care.
No critical data has been modified, there is no inconsistent
state to be observed; and YOUR Instruction Pointer is not
pointing into instructions within the ATOMIC event !!

This seems to be predicated on something that you understand
about this mechanism that you've proposed, but haven't quite
explained (or perhaps that I haven't understood).

So again, I ask my question, how do I get into the critical
section? Given the text quoted above from my last reply, what
is the utility of these atomic events vis that goal?

It sounds like you're saying that I can use them to implement a
traditional spin lock. But then how are they better than a
"normal" atomic CAS? You mention respecting priority and in
particular avoiding inversion, but I don't think that's actually
true: consider some critical section, where I cannot yield the
CPU to another thread, even one running at higher priority,
since I'm manipulating some data structure and it is important
that that data structure not be in an intermediate state when
I get switched away from; this strongly implies that I use these
atomic primitives to build the sort of lock where I set some
_other_ datum, not the "lock" manipulated in the atomic event,
to indicate that I'm in the critical section: but if that's the
case, then what prevents some other, higher priority thread,
from attempting to enter the critical section _when I'm in it_,
but not when I'm racing on the lock?

E.g., this sequence of events:

Thread A (lo pri) Thread B (hi pri)
-------- --------
Atomic lock
Observe success
Acquire mutex
Unlock

Atomic Lock
Observe success
Observe that mutex is already set
Unlock
Now what?

enter the critical section, and observe a data
structure in an inconsistent state (leading to a crash in the
best case).

There is no inconsistent state--in rather the same way a core backs
up a branch mispredict, the core backs up the ATOMIC event to appear
as if it never even started !!

We've already established that this cannot cover all use cases.
See my example of popping off of a queue and inserting into an
ordered list.

This is precisely the sort of thing we build mutual
exclusion primitives to wrap around critical sections to avoid.

And also why those primitives give rise to priority inversion
and lock-starvation.

But this mechanism is insufficient to actually address those
problems in anything but the most limited ways. See the example
above.

Moreover, those are problems that are well understood and are
successfully mitigated in real world systems. I do not see any
evidence that they are sufficiently problematic supporting the
introduction of a brand new mechanism with poorly understood
behavior and what seems like very complex semantics.

If, on the other hand, the atomic primitives are just meant for
the spin loop, then I don't really see how that's all that
useful compared to LL/SC.

Any number of respected people have ask for a pipelined LL-SC;
where one can LL multiple datums and later SC multiple datums.
This is what ESM can provide.

Who are these folks and have any of them chimed in on this
proposal? It seems like you've gone far beyond "pipelined
LL-SC" and introduced notions of threads and priorities that
interact with that in complex and, frankly, undesirable ways.

And you still need some way to ensure
that the critical section is not interrupted.

Just a way to detect if it happened; and if it happens;
means to back upto a point where it does not matter if
interference happened "right there"--that is: outside of
a critical section.

This is based on the fallacious assumption that that is possible
in the general case. I think I have shown that it is not.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

cross@spitfire.i.gajendra.net (Dan Cross) writes:

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

My ATOMIC stuff allows for the construction, in SW, of pretty
much any ATOMIC primitive anyone would like. It is, in general,
not suited to guard critical regions, but to grab the lock which
does.

Ok, that's good to understand.

Most uses of My ATOMIC stuff is to grab/change/update data
that then guards various critical regions. More like a multi-
valued version of LDL-STC.

I don't see how constructing the primitive that way is terribly
useful compared to just issuing multiple load-locked/store-cond
instructions; in particular, it doesn't seem like the sort of
thing that composes well: every sequence that uses it must be
coded to use it, explicitly, instead of just nesting calls to
"lock".

LL/SC has been shown to be less efficient for contended
locks than atomic operations when the core count exceeds
single digits.

It's difficult to argue against the standard set of atomic
primitives (the PCIe set: compare and swap, load and add,
swap) for scalability; ARM has extended the list to
include exclusive or, set-bit, clear-bit, min, max, et al.

Analysis comparing with LL/SC:

https://cpufun.substack.com/p/atomics-in-aarch64

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

mitchalsup@aol.com (MitchAlsup1) writes:

On Mon, 24 Mar 2025 23:45:49 +0000, Dan Cross wrote:

So, if you want the property whereby the lock disappears on any
control transfer out of the event {exception, interrupt, SVC, SVR, ...}; >>>then you want to use my ATOMIC stuff; otherwise, you can use the
normal ATOMIC primitives everyone and his brother provide.

I definitely do Not want that property. Having a lock
"disappear" on delivery of an interrupt seems like it would be a
great way to introduce silent corruption.

It means that if a thread owning a lock is interrupted, that
thread gives the lock back--so there is no priority inversion
and no lock-starvation. Associated with the give back, and the
IP of the interrupted thread no longer points inside the
critical section.

Nothing gets lost.

This isn't a hardware transaction. If the thread has updated data
and you take away the lock, the system is now inconsistent
and nasal daemons will ensue.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Tue, 25 Mar 2025 13:45:39 +0000, Scott Lurndal wrote:

mitchalsup@aol.com (MitchAlsup1) writes:

Nothing gets lost.

This isn't a hardware transaction. If the thread has updated data
and you take away the lock, the system is now inconsistent
and nasal daemons will ensue.

In HW there is a little thing known as branch misprediction repair,
where all the work done is made to appear as if those instructions
were never executed to begin with. The size of the branch mispredict
window is on the order of 300 instructions now.

With Spectré and Meltdown even cache updates must be delayed until
after the causing instruction retires.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <8qyEP.1257951$FVcd.630606@fx10.iad>,
Scott Lurndal <slp53@pacbell.net> wrote:

cross@spitfire.i.gajendra.net (Dan Cross) writes:

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

My ATOMIC stuff allows for the construction, in SW, of pretty
much any ATOMIC primitive anyone would like. It is, in general,
not suited to guard critical regions, but to grab the lock which
does.

Ok, that's good to understand.

Most uses of My ATOMIC stuff is to grab/change/update data
that then guards various critical regions. More like a multi-
valued version of LDL-STC.

I don't see how constructing the primitive that way is terribly
useful compared to just issuing multiple load-locked/store-cond >>instructions; in particular, it doesn't seem like the sort of
thing that composes well: every sequence that uses it must be
coded to use it, explicitly, instead of just nesting calls to
"lock".

LL/SC has been shown to be less efficient for contended
locks than atomic operations when the core count exceeds
single digits.

It's difficult to argue against the standard set of atomic
primitives (the PCIe set: compare and swap, load and add,
swap) for scalability; ARM has extended the list to
include exclusive or, set-bit, clear-bit, min, max, et al.

Analysis comparing with LL/SC:

https://cpufun.substack.com/p/atomics-in-aarch64

That analysis is interesting; thanks for pointing it out. I'm
not sure that it is directly applicable to locks, though, since
it's primarily concerned with atomic increment. Semaphores,
perhaps; something like `ldaddal` would work well in the
implementation of `xadd`, as in this paper by Mullender and Cox: https://swtch.com/semaphore.pdf

Highly contended spin locks based on CAS loops tend not to scale
well as core counts increase, hence more elaborate lock types
like MCS locks, CLH locks, and so on. Boyd-Wickizer et al go
into this in detail in https://people.csail.mit.edu/nickolai/papers/boyd-wickizer-locks.pdf
I rather doubt that single-instruction atomics versus LL-SC are
a going to make a big difference here. But I also wonder at the
internal implementation of these instructions in e.g. that
Fujitsu chip that allows throughput to stay more or less
constant as the number of cores increases; I'd think that cache
coherency traffic as threads contend for a single cache line
would create a bottleneck leading to (at least) a linear
slow down. This suggests to me that perhaps the performance
characteristcs are less in the specific instructions used (one
versus LL-SC), but rather how those instructions are
implemented with respect to the coherency protocol.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

On Tue, 25 Mar 2025 13:45:39 +0000, Scott Lurndal wrote:

mitchalsup@aol.com (MitchAlsup1) writes:

Nothing gets lost.

This isn't a hardware transaction. If the thread has updated data
and you take away the lock, the system is now inconsistent
and nasal daemons will ensue.

In HW there is a little thing known as branch misprediction repair,
where all the work done is made to appear as if those instructions
were never executed to begin with. The size of the branch mispredict
window is on the order of 300 instructions now.

With Spectré and Meltdown even cache updates must be delayed until
after the causing instruction retires.

But again, that's irrelevant. The "critical sections" in
question here are software abstractions created by system
software. What you're describing is at the microarchitectural
level; two totally different worlds. I think the fundamental
mismatch here is that you're trying to apply this solution you
have created for something at the uarch level to a problem at
the systems software level. It's jut not a good fit.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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.

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.
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.

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.

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.

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.

|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.

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.

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.
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.

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.

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.

If something you want to do requires a certain hat and you are not
wearing that hat then you have to get one.

Inside an HW interrupt service routine and want to run a thread?
ISR (interrupt hat) posts a Dpc to software interrupt level (SWI hat) Dispatcher, which eventually runs calls a routine that accesses scheduler tables guarded by a spinlock (that requires the SWI hat), that selects your thread so when OS returns (thread hat) your application code executes.

- Dan C.

References:

[Her08] Maurice Herlihy and Nir Shavit. 2008. _The Art of
Multiprocessor Programming_. Morgan Kaufmann, Burlington, MA.

[Vah96] Uresh Vahalia. 1996. _Unix Internals: The New
Frontiers_. Prentice Hall, Upper Saddle River, NJ.

[Vaj11] Andras Vajda. 2011. _Programming Many-Core Chips_.
Springer, New York, NY.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

a going to make a big difference here. But I also wonder at the
internal implementation of these instructions in e.g. that
Fujitsu chip that allows throughput to stay more or less
constant as the number of cores increases; I'd think that cache
coherency traffic as threads contend for a single cache line
would create a bottleneck leading to (at least) a linear
slow down.

IIUC the idea is that the atomic-add is sent to the memory and performed
there, instead of moving the data to the cache. So there's no
contention for the cache line because the data is not in a cache at all.


Stefan

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Tue, 25 Mar 2025 15:10:19 +0000, Dan Cross wrote:

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

On Tue, 25 Mar 2025 13:45:39 +0000, Scott Lurndal wrote:

mitchalsup@aol.com (MitchAlsup1) writes:

Nothing gets lost.

This isn't a hardware transaction. If the thread has updated data
and you take away the lock, the system is now inconsistent
and nasal daemons will ensue.

In HW there is a little thing known as branch misprediction repair,
where all the work done is made to appear as if those instructions
were never executed to begin with. The size of the branch mispredict
window is on the order of 300 instructions now.

With Spectré and Meltdown even cache updates must be delayed until
after the causing instruction retires.

But again, that's irrelevant. The "critical sections" in
question here are software abstractions created by system
software.

Say you have a critical section (of your description) that was
preceded by an if-statement that was predicted to enter CS, but
1,000 cycles later the branch is resolved to not enter the CS.
{{Branch was dependent on an MMI/O location down the PCIe tree
which is why it took so long to resolve.}}

HW Backs the core up so that the RF and all memory locations
contain their original values at the point of the mispredicted
branch.

Can thread running on core even tell if you entered CS or not !

No, your thread cannot.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Stefan Monnier <monnier@iro.umontreal.ca> writes:

a going to make a big difference here. But I also wonder at the
internal implementation of these instructions in e.g. that
Fujitsu chip that allows throughput to stay more or less
constant as the number of cores increases; I'd think that cache
coherency traffic as threads contend for a single cache line
would create a bottleneck leading to (at least) a linear
slow down.

IIUC the idea is that the atomic-add is sent to the memory and performed >there, instead of moving the data to the cache. So there's no
contention for the cache line because the data is not in a cache at all.

Exactly. The LLC may also support the atomics directly.

Additionally, with PCIe, the atomic can be executed at
the endpoint function.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

EricP <ThatWouldBeTelling@thevillage.com> writes:

Dan Cross wrote:

I didn't.
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.

https://en.wikipedia.org/wiki/Incompatible_Timesharing_System

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

IIUC the idea is that the atomic-add is sent to the memory and performed >>there, instead of moving the data to the cache. So there's no
contention for the cache line because the data is not in a cache at all.

Exactly. The LLC may also support the atomics directly.

Additionally, with PCIe, the atomic can be executed at
the endpoint function.

It should even be possible (no idea if anyone tried to implement it) to
combine the operations as they bubble up the memory, so your
N increments on your N cores can turn into N/64 additions of 64 leaving
each group of 64 cores, making it possible to scale with the number
of cores.


Stefan

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <jwviknxp0zj.fsf-monnier+comp.arch@gnu.org>,
Stefan Monnier <monnier@iro.umontreal.ca> wrote:

a going to make a big difference here. But I also wonder at the
internal implementation of these instructions in e.g. that
Fujitsu chip that allows throughput to stay more or less
constant as the number of cores increases; I'd think that cache
coherency traffic as threads contend for a single cache line
would create a bottleneck leading to (at least) a linear
slow down.

IIUC the idea is that the atomic-add is sent to the memory and performed >there, instead of moving the data to the cache. So there's no
contention for the cache line because the data is not in a cache at all.

Interesting; that's very clever.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Scott Lurndal wrote:

Stefan Monnier <monnier@iro.umontreal.ca> writes:

a going to make a big difference here. But I also wonder at the
internal implementation of these instructions in e.g. that
Fujitsu chip that allows throughput to stay more or less
constant as the number of cores increases; I'd think that cache
coherency traffic as threads contend for a single cache line
would create a bottleneck leading to (at least) a linear
slow down.

IIUC the idea is that the atomic-add is sent to the memory and performed
there, instead of moving the data to the cache. So there's no
contention for the cache line because the data is not in a cache at all.

Exactly. The LLC may also support the atomics directly.

Additionally, with PCIe, the atomic can be executed at
the endpoint function.

Those features are possible but there is no indication that is
what that web page is measuring.

I agree with Dan that looks more like a test of the cache efficiency or
the cache line pinning mechanism than a test of LL/SC vs AtomicXxxx.

First, it doesn't say what systems these are on.
It says the cores is Cavium Thunder X2 and Fujitsu A64FX
but does not describe the systems.

For each platform it needed to establish a base line performance for
moving lines between caches, the same ++ loops but without atomics.

Also Arm is weak ordered. At least one version of those test loops should
have fences otherwise this doesn't tell you anything about how it might
behave in real use.

And as a general guideline, I tend to distrust concurrency benchmarks
which sit in a tight loop hammering a single memory location because
they greatly favor whichever core is currently holding the cache line.
By artificially inflating the contention they really tell you little
about how it will behave in real world use where there are time gaps
between core accesses allowing lines to move.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

On Tue, 25 Mar 2025 15:10:19 +0000, Dan Cross wrote:

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

On Tue, 25 Mar 2025 13:45:39 +0000, Scott Lurndal wrote:

mitchalsup@aol.com (MitchAlsup1) writes:

Nothing gets lost.

This isn't a hardware transaction. If the thread has updated data
and you take away the lock, the system is now inconsistent
and nasal daemons will ensue.

In HW there is a little thing known as branch misprediction repair,
where all the work done is made to appear as if those instructions
were never executed to begin with. The size of the branch mispredict >>>window is on the order of 300 instructions now.

With Spectré and Meltdown even cache updates must be delayed until
after the causing instruction retires.

But again, that's irrelevant. The "critical sections" in
question here are software abstractions created by system
software.

Say you have a critical section (of your description) that was
preceded by an if-statement that was predicted to enter CS, but
1,000 cycles later the branch is resolved to not enter the CS.
{{Branch was dependent on an MMI/O location down the PCIe tree
which is why it took so long to resolve.}}

HW Backs the core up so that the RF and all memory locations
contain their original values at the point of the mispredicted
branch.

Can thread running on core even tell if you entered CS or not !

No, your thread cannot.

Again, how is that relevant? The branch predictor can only
handle speculative execution of so-many instructions. Attempts
to perform more instructions than that will stall the pipeline.

A critical section as defined by software may contain more than
that number of instructions. A critical section, as defined by
software, may touch more cache lines than your atomic event
proposal can handle. Thus, for your architecture to be useful,
you must provide some mechanism for handling those
eventualities.

Your stuff sounds fine for getting into the critsec; but it
doesn't help you once you're in it, and it seems like it may
hurt you if some higher-priority thing comes along and yanks
your lock out from under you.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

EricP <ThatWouldBeTelling@thevillage.com> writes:

Scott Lurndal wrote:

Stefan Monnier <monnier@iro.umontreal.ca> writes:

a going to make a big difference here. But I also wonder at the
internal implementation of these instructions in e.g. that
Fujitsu chip that allows throughput to stay more or less
constant as the number of cores increases; I'd think that cache
coherency traffic as threads contend for a single cache line
would create a bottleneck leading to (at least) a linear
slow down.

IIUC the idea is that the atomic-add is sent to the memory and performed >>> there, instead of moving the data to the cache. So there's no
contention for the cache line because the data is not in a cache at all.

Exactly. The LLC may also support the atomics directly.

Additionally, with PCIe, the atomic can be executed at
the endpoint function.

Those features are possible but there is no indication that is
what that web page is measuring.

I agree with Dan that looks more like a test of the cache efficiency or
the cache line pinning mechanism than a test of LL/SC vs AtomicXxxx.

First, it doesn't say what systems these are on.
It says the cores is Cavium Thunder X2 and Fujitsu A64FX
but does not describe the systems.

There were actually two Thunder X2 chips - the original was
the Cavium in-house design, the second was based on the Vulcan
design that Cavium bought from Broadcom. The Cavium Thunderx2
chip was rebranded OcteonTx and aimed at the networking market,
while the Vulcan was named ThunderX2 and sold into the server space.

For each platform it needed to establish a base line performance for
moving lines between caches, the same ++ loops but without atomics.

Also Arm is weak ordered. At least one version of those test loops should >have fences otherwise this doesn't tell you anything about how it might >behave in real use.

The memory model is formally defined in the ARM Architecture manual.
There are a number of methods available to deal with ordering and
consistency, including a memory barrier instruction (DMB) which
can be applied globally or within sharability domains.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Tue, 25 Mar 2025 17:54:42 +0000, Dan Cross wrote:

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

--------------------------

Say you have a critical section (of your description) that was
preceded by an if-statement that was predicted to enter CS, but
1,000 cycles later the branch is resolved to not enter the CS.
{{Branch was dependent on an MMI/O location down the PCIe tree
which is why it took so long to resolve.}}

HW Backs the core up so that the RF and all memory locations
contain their original values at the point of the mispredicted
branch.

Can thread running on core even tell if you entered CS or not !

No, your thread cannot.

Again, how is that relevant? The branch predictor can only
handle speculative execution of so-many instructions.

Around 300 at present.
Know of any critical sections that long?

Attempts
to perform more instructions than that will stall the pipeline.

Obviously.

A critical section as defined by software may contain more than
that number of instructions.

Sure, its possible.

But if DECODE cannot push the entire critical section into the
execution window, then BY DEFINITION, it MUST be able to make
the entire critical section appear as if you never started on
it !!!

IP gets backed up as if you never entered CS
RF gets backed up as if you never entered CS
LOCK variable never got written to SNOOPable cache where others can see
it
Cache memory gets put back in the "you never got here" states too.

Thus, it is like it never happened:: both to the core and to all
interested 3rd parties.

Nobody saw the Lock variable change value.
And
Nobody saw any STs from the CS change anything in memory.

Thus, it is as if CS never happened, it was all speculative, and
got put-right when CS was not allowed to finish.

BUT-----------------------------
Code running in CS does believe the the LOCK variable was updated
AND that STs from CS have been performed by the exit of CS ------------------------------------------------------------

You see SW sees the nonNeumann model. 1 instruction is Fetched
and executed in its entirely before proceeding to the next inst-
ruction. You see individual instructions--as if single stepping.

HW, on the other hand sees at least 3 points in time
a) instructions has not arrived to be execcuted
b) instruction is executing
c) instruction has completed executing

And the time span from 1) to c) can be hundreds of cycles
while there are 300 (or more) instruction contending for
execution resources.

In additions, certain instructions may have more than 1 b) units
of timing--for example a LD-OP-ST has a LD execution, an OP
execution, and a ST execution.

But look at the execution of a ST in the shadow of a branch.
We want ST to be "performed" as soon as possible, so that a
subsequent LD can obtain the ST-data even before we are allowed
to write ST-data into the cache. So, your notion of what can be
backed up (or not) appears not to be able to see all the funny
business HW goes through to make the core smell fast.

After the LD receives ST-data, the branch may resolve as a
bad prediction, and the ST is not allowed to modify cache,
also the LD was not allowed to see data that was never to be
written. And HW clean up making it all SMELL like it never
happened.

-----------------------------------------------------------

Interested 3rd parties are another problem to be solved.

In the midst of a CS a SNOOP comes along and touches a memory
location you are using in CS.

a) You can make the CS appear never to have happened
b) you can delay the SNOOP response
c) You can wait for the branch to resolve to choose
...between a) and b)
d) same as c) but coherence protocol has a NaK in it.

(c) is only an option for more advance cache coherence protocols.

(d) allows a CS in the manifestation part (Sts) to have priority
(sic.) over interfering SNOOP requests--a soft guarantee of for-
ward progress.

A critical section, as defined by
software, may touch more cache lines than your atomic event
proposal can handle.

Sure, but then you would only be using my ATOMICs for locking/
unlocking not for the work going on.

Thus, for your architecture to be useful,
you must provide some mechanism for handling those
eventualities.

As stated about 15 responses ago, just use them as ATOMIC primitive
generators.

Your stuff sounds fine for getting into the critsec; but it
doesn't help you once you're in it, and it seems like it may
hurt you if some higher-priority thing comes along and yanks
your lock out from under you.

I conceded that point at least 2 days ago.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <vrv483$3ekk$2@dont-email.me>,
Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:

On 3/25/2025 4:20 AM, Dan Cross wrote:

In article <vrt37r$27c13$4@dont-email.me>,
Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:

On 3/24/2025 1:28 PM, Dan Cross wrote:

There's no guarantee that the tail is the correct place to
insert the element, vis the order of the elements.

https://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html

If you go back and review the thread, you'd see that the problem
is to remove an element from a queue, and insert it into an
ordered list. This part of the discussion is concerning the
latter operation.

There are lock-free ways to insert into an ordered list, indeed.

How is that relevant?

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Dan Cross [2025-03-25 22:19:07] wrote:

From what I gather, you've said to just eschew the atomic event
stuff and build a traditional lock using those primitives. But
you have also said that a traditional lock can be silently
unlocked if the thread holding it (which, apparently, is an
abstraction known to hardware) is preempted. It will be like
the lock had never been acquired.

Here's the misunderstanding: the lock that can be silently taken away
is the lock implemented in the CPU to run an ATOMIC sequence, not the
lock implemented as a data-structure on top of it: once you've run
(atomically) your `lock_acquire`, of course that lock is yours. The CPU doesn't even know that this data-structure is a lock and has no
way to steal it.


Stefan

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

On Tue, 25 Mar 2025 17:54:42 +0000, Dan Cross wrote:

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

--------------------------

Say you have a critical section (of your description) that was
preceded by an if-statement that was predicted to enter CS, but
1,000 cycles later the branch is resolved to not enter the CS.
{{Branch was dependent on an MMI/O location down the PCIe tree
which is why it took so long to resolve.}}

HW Backs the core up so that the RF and all memory locations
contain their original values at the point of the mispredicted
branch.

Can thread running on core even tell if you entered CS or not !

No, your thread cannot.

Again, how is that relevant? The branch predictor can only
handle speculative execution of so-many instructions.

Around 300 at present.
Know of any critical sections that long?

Oh, absolutely.

But that's besides the point. The point is that software _can_
exceed that limit, even if it's a bad idea to do so; it may not
even be immediately obvious to the programmer, who is most
likely working in a high-level langauge, not assembler.

How will your design accommodate that eventuality?

Attempts
to perform more instructions than that will stall the pipeline.

Obviously.

A critical section as defined by software may contain more than
that number of instructions.

Sure, its possible.

But if DECODE cannot push the entire critical section into the
execution window, then BY DEFINITION, it MUST be able to make
the entire critical section appear as if you never started on
it !!!

So ... what, you just don't execute it? Always skip over it?
Software needs to ensure serial access to some resource. That's
what critical sections are for. Your architecture needs to
support that.

From what I gather, you've said to just eschew the atomic event
stuff and build a traditional lock using those primitives. But
you have also said that a traditional lock can be silently
unlocked if the thread holding it (which, apparently, is an
abstraction known to hardware) is preempted. It will be like
the lock had never been acquired.

But here's the impedence mismatch: it appears that that happens
_after_ software has already made a decision based on something
that is rolled back later. If that's mistaken, then say so, but
if not, then the scheme is fatally flawed: there is literally no
way you can use it reliably to build anything that doesn't fit
into your atomic window.

IP gets backed up as if you never entered CS
RF gets backed up as if you never entered CS
LOCK variable never got written to SNOOPable cache where others can see
it
Cache memory gets put back in the "you never got here" states too.

[...a lot of the same stuff, repeated over and over snipped]

A critical section, as defined by
software, may touch more cache lines than your atomic event
proposal can handle.

Sure, but then you would only be using my ATOMICs for locking/
unlocking not for the work going on.

Indeed; that's what I've been saying.

But you also seem to imply that if a higher priority interrupt
comes along and preempts the code that's in the critical section
it will silently unlock the lock that is used to serialize entry
into the critical section. Is that correct? If so, do you see
how that makes the whole facility useless for building robust
mutual exclusion primitives? A lock that is silently released
because something else comes along and wants a turn instead is
no lock at all.

Thus, for your architecture to be useful,
you must provide some mechanism for handling those
eventualities.

As stated about 15 responses ago, just use them as ATOMIC primitive >generators.

Yes. Was that the same response where you said the lock would
be silently released if a higher-priority interrupt came along?

Your stuff sounds fine for getting into the critsec; but it
doesn't help you once you're in it, and it seems like it may
hurt you if some higher-priority thing comes along and yanks
your lock out from under you.

I conceded that point at least 2 days ago.

Ok, now we're back to the question then: what purpose does it
serve? It doesn't seem like it can be usefully applied to
anything other than building traditional mutexes based on spin
locks, and even then I'm not sure if that's correct (see above).

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <vrvdth$d24n$1@dont-email.me>,
Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:

On 3/25/2025 3:21 PM, Dan Cross wrote:

In article <vrv483$3ekk$2@dont-email.me>,
Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:

On 3/25/2025 4:20 AM, Dan Cross wrote:

In article <vrt37r$27c13$4@dont-email.me>,
Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:

On 3/24/2025 1:28 PM, Dan Cross wrote:

There's no guarantee that the tail is the correct place to
insert the element, vis the order of the elements.

https://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html

If you go back and review the thread, you'd see that the problem
is to remove an element from a queue, and insert it into an
ordered list. This part of the discussion is concerning the
latter operation.

There are lock-free ways to insert into an ordered list, indeed.

How is that relevant?

inserting into an ordered list is not relevant?

The fact that you can use a lock-free algorithm to do so seems
utterly beside the point.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <jwvjz8coho7.fsf-monnier+comp.arch@gnu.org>,
Stefan Monnier <monnier@iro.umontreal.ca> wrote:

Dan Cross [2025-03-25 22:19:07] wrote:

From what I gather, you've said to just eschew the atomic event
stuff and build a traditional lock using those primitives. But
you have also said that a traditional lock can be silently
unlocked if the thread holding it (which, apparently, is an
abstraction known to hardware) is preempted. It will be like
the lock had never been acquired.

Here's the misunderstanding: the lock that can be silently taken away
is the lock implemented in the CPU to run an ATOMIC sequence, not the
lock implemented as a data-structure on top of it: once you've run >(atomically) your `lock_acquire`, of course that lock is yours. The CPU >doesn't even know that this data-structure is a lock and has no
way to steal it.

I hope you are right, and I'd like Mitch to confirm.

Even so, I don't see the point of the proposed atomic framework.
It seems to have no significant advantage over a more
traditional scheme; CAS, LL-SC, whatever seem more general and
less intertwined with primitives that the hardware has no real
business injecting itself into (like threads).

- Dan C.


--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Tue, 25 Mar 2025 22:49:29 +0000, Stefan Monnier wrote:

Dan Cross [2025-03-25 22:19:07] wrote:

From what I gather, you've said to just eschew the atomic event
stuff and build a traditional lock using those primitives. But
you have also said that a traditional lock can be silently
unlocked if the thread holding it (which, apparently, is an
abstraction known to hardware) is preempted. It will be like
the lock had never been acquired.

Here's the misunderstanding: the lock that can be silently taken away
is the lock implemented in the CPU to run an ATOMIC sequence, not the
lock implemented as a data-structure on top of it: once you've run (atomically) your `lock_acquire`, of course that lock is yours. The CPU doesn't even know that this data-structure is a lock and has no
way to steal it.

You are getting at the "why". In Compare-Swap atomic sequences with
your typical ISA, the HW does not see the initial LD (of the memory participating in the compare-swap instruction) as locked. In the LL-
SC version, HW does have that tidbit of information.

With that information, the event is secured both by data and by
address, preventing the ABA problem {At least in ESM}.

Stefan

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Tue, 25 Mar 2025 22:19:07 +0000, Dan Cross wrote:

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

Your stuff sounds fine for getting into the critsec; but it
doesn't help you once you're in it, and it seems like it may
hurt you if some higher-priority thing comes along and yanks
your lock out from under you.

I conceded that point at least 2 days ago.

Ok, now we're back to the question then: what purpose does it
serve?

You (well Chris) can write critical sections where a low priority
holder can give way to the higher priority requestor such that
the low priority holder reverts back to before it entered CS,
and does not see the lock being stolen.

For the sizes of CSs this covers--it prevent priority inversion.

It doesn't seem like it can be usefully applied to
anything other than building traditional mutexes based on spin
locks, and even then I'm not sure if that's correct (see above).

And here I thought you had an imagination .....

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Even so, I don't see the point of the proposed atomic framework.
It seems to have no significant advantage over a more
traditional scheme; CAS, LL-SC, whatever seem more general and
less intertwined with primitives that the hardware has no real
business injecting itself into (like threads).

AFAICT it's somewhat similar to ARM's LL/SC (which can also cover some
number of cache lines) except that it takes care of looping for you: if
the final store fails because of interference My 66000 will "simply" abort
the whole operation (reusing the speculation hardware) and start over,
instead of having to write an explicit loop.

Without actual hardware and software to try it's hard to assess how well
it's going to work, but the design sounds good: it should lead to more
compact code than LL/SC, be more general/friendly to lock-free coding
than T&S/C&S, and also compared to LL/SC it should behave better under
high contention because it is careful to guarantee overall forward
progress (in case of conflict between two cores, at least one of them
can finish successfully).

IIRC there's also some kind of mechanism to retry more cleverly, i.e. so
that when N cores are in conflicts, not only one of them succeeds, but
the N-1 remaining cores have a fighting chance of avoiding bumping into
each other next time around. I don't know the details, tho, and IIUC
this is not automatic: some relevant info is provided but it's up to the
code to do something useful with it.


Stefan

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

On Tue, 25 Mar 2025 22:19:07 +0000, Dan Cross wrote:

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

Your stuff sounds fine for getting into the critsec; but it
doesn't help you once you're in it, and it seems like it may
hurt you if some higher-priority thing comes along and yanks
your lock out from under you.

I conceded that point at least 2 days ago.

Ok, now we're back to the question then: what purpose does it
serve?

You (well Chris) can write critical sections where a low priority
holder can give way to the higher priority requestor such that
the low priority holder reverts back to before it entered CS,
and does not see the lock being stolen.

You still have not defined what you mean by, "the lock being
stolen."

Tell you what. Earlier, you posted some code for a critical
section that inserts a node into a linked list. That code is
written in terms of some primitives (presumably intrinsics,
though you call them macros); `esmLOCKload`, `esmLOCKprefetch`, `esmINTERFERENCE` and `esmLOCKstore`. Here's that code, slightly
reformatted:

// Removes the element `from` from a doubly linked list, and
// inserts it into a (possibly different) doubly linked list,
// after the element pointed to be `to`.
// Assumes <stdbool.h>
bool
MoveElement(Element *from, Element *to)
{
assert(from != NULL);
assert(to != NULL);

Element *from_next = esmLOCKload(from->next);
Element *from_prev = esmLOCKload(from->prev);
Element *to_next = esmLOCKload(to->next);
esmLOCKprefetch(from_next);
esmLOCKprefetch(from_prev);
esmLOCKprefetch(to_next);
if (!esmINTERFERENCE()) {
// Unlink the "from" node from its list.
from_prev->next = from_next; // XXX: `from_prev` may be nil?
from_next->prev = from_prev; // XXX: `from_next` may be nil?
// Insert the node after "to".
to->next = from;
to_next->prev = from; // XXX: `to_net` may be nil?
from->prev = to;
esmLOCKstore(from->next, to_next);
return true;
}
return false;
}

Leaving aside the unchecked boundary conditions I highlighted
above, there are other questions that this raises. You
mentioned that the ESM stuff can use up to 8 cache lines in a
single atomic "event"; let's count how many this code may
encounter:

1. `from` may point to a cache line
2. `to` may point to a different cache line.
3. Does your architecture use a stack? What sort of alignment
criteria do you impose? At first blush, it seems to me that
the pointers `from_next`, `from_prev`, and `to_next` could be
on the stack and if so, will be on at least one cache line,
and possibly 2, if the call frame for `MoveElement` spans
more than one. Of course, it's impossible to say when this
is compiled, but maybe you require that the stack is always
aligned to a cache line boundary or something. Or maybe
these are all in registers and it's fine.
4. Depending on the size and alignment criteria of the the
`Element` structure and the placement of the `next` and
`prev` elements in the struct (unknowable from this example),
`to->next` may be on another cache line.
5. Similarly, `from->next`
6. And `from->prev`
7. And `from_prev->next`
8. And `from_next->prev`
9. And `to_next->prev`.

So potentially this code _could_ touch 9 or 10 cache lines, more
than you said are supported for a single atomic event. What
happens in that case? Does the code just always return false?
The programmer best make sure the optimizer is keeping those
temporary pointers off the stack; good luck with a debug build.

Anyway, let's assume that's not the case, and we don't hit the
pathological case with cache lines, and we're not dealing with
edge cases at the front or end of the lists (so various next or
prev pointers are not NULL). Why don't I try to explain what I
think this code is doing, and you tell me whether I'm right or
wrong.

If I understand this correctly, the `esmLOCKload`s are simply
loads, but they make sure that the compiler emits instructions
that tie into your atomic support framework. Earlier you wrote, "esmINTERFERENCE is a query on the state of th event and whether
a 2nd party has performed a memory action that kills the event."
Ok, I take this to mean _at the time of the store_, which
appears later in the program. If it were simply a query at the
time it was written in the code, then it seems like it opens a
TOCTOU bug (what if something interfers after the check, but
before the the locked store at the end?). Or perhaps it signals
to the architecture that this is the point to which the
processor should rollback, if anything subsequently fails; sort
of a `setjmp` kind of thing that conceptually returns twice.

Assuming nothing has poisoned the event, the various pointer
stores inside the conditional are conditionally performed; the
`esmLOCKstore` to `from->next` commits the event, at which
point all side effects are exposed and durable.

Is that correct? Let's suppose that it is.

But later you wrote,

So, if you want the property whereby the lock disappears on any
control transfer out of the event {exception, interrupt, SVC, SVR, ...};
then you want to use my ATOMIC stuff; otherwise, you can use the
normal ATOMIC primitives everyone and his brother provide.

Well, what precisely do you mean here when you say, "if you want
the property whereby the lock disappears on any control transfer
out of the event"?

What I _hope_ you mean is that if you transfer "out of the
event" before the `esmLOCKstore` then anything that's been done
since the "event" started is rolled back, but NOT if control
transfer happens _after_ the `esmLOCKstore`. If THAT were the
case, then this entire mechanism is useless.

Perhaps you would clarify?

But for the time being, let's assume that `esmLOCKstore` is
conceptually a commit that ends the atomic event, and the store
is durable and observable after that. Let's see if we can
construct a simple spinlock from these primitives.

typedef struct Spinlock Spinlock;
struct Spinlock {
uint32_t lock;
};

uint32_t
xcas(volatile Spinlock *lk, uint32_t expected, uint32_t val)
{
uint32_t v = esmLOCKload(&lk->lock);
if (v == expected && !esmINTERFERENCE()) {
esmLOCKstore(&lk->lock, val)
}
return v;
}

void
spin_acquire(volatile Spinlock *lk)
{
splhi();
while (xcas(lk, 0, 1) != 0)
relax(); // Spin loop intrinsic.
}

void
spin_release(volatile Spinlock *lk)
{
xcas(lk, 1, 0);
// Maybe we should `spllo` here, maybe not. Either choice
// reflects lots of assumptions about whether or not we might
// take and hold multiple locks concurrently, etc.
spllo();
}

Does this seem correct? It is not immediately clear to me
whether `esmINTERFERENCE` is actually needed here, but
avoiding the store seemed fine. One could imagine shorting
`xcas` to simply:

uint32_t
xcas(volatile Spinlock *lk, uint32_t expected, uint32_t val)
{
uint32_t v = esmLOCKload(&lk->lock);
if (v == expected) esmLOCKstore(&lk->lock, val);
return v;
}

or perhaps:

uint32_t
xswap(volatile Spinlock *lk, uint32_t val)
{
uint32_t v = esmLOCKload(&lk->lock);
esmLOCKstore(&lk->lock, val);
return v;
}

But that all depends on the specifics of the atomics.

For the sizes of CSs this covers--it prevent priority inversion.

Except you've admitted that this is not a general solution, as
it cannot "cover" arbitrary software-defined critical sections:
the window isn't big enough and we've seen how even a fairly
small problem may exceed the number of cache lines supported by
one of these events.

So I have to implement solutions to priority inversion problems
outside of your scheme anyway. Clearly, whatever mechanism is
chosen to do so is, by definition, also general enough to cover
the use cases for which your atomic scheme is best suited.

Plus, as you stated, this whole thing is wrapped up in notions
of threads and priorities that appear to try and subsume some
functionality from the OS, whether it's a good fit for a
particular OS's expectations or not; as a simple example, the
priorities of threads can change over time, etc, and it's not
clear how to keep that state in sync between the OS and
hardware, and so on.

So now I, as a systems software person, have to ask design
question around how I want to use these architectural features,
if at all, weighing various pros and cons. This is where I'm
struggling with your proposal: given that I'm going to have to
implement more general support for the things that the
architecture gives me anyway, what do I gain by also supporting
the specialized mechanisms? Particularly if, in order to use
them, I'm also forced into a "shape" for my system that's
dictated by the hardware, but that may not be the best for my
software? Is whatever the hardware gives me worth the tradeoff?

Right now, I'm not seeing it that it is. "It solves priority
inversion for the size of problems that it's applicable to" is
not enough to justify the additional cost of adoption. I have
to solve that problem anyway, whether I use this or not.

It doesn't seem like it can be usefully applied to
anything other than building traditional mutexes based on spin
locks, and even then I'm not sure if that's correct (see above).

And here I thought you had an imagination .....

You admitted you're not an OS person and asked other people to
poke holes in your proposal. I'm sorry if you find the holes
I'm poking upsetting.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <jwv34f0o75h.fsf-monnier+comp.arch@gnu.org>,
Stefan Monnier <monnier@iro.umontreal.ca> wrote:

Even so, I don't see the point of the proposed atomic framework.
It seems to have no significant advantage over a more
traditional scheme; CAS, LL-SC, whatever seem more general and
less intertwined with primitives that the hardware has no real
business injecting itself into (like threads).

AFAICT it's somewhat similar to ARM's LL/SC (which can also cover some
number of cache lines) except that it takes care of looping for you: if
the final store fails because of interference My 66000 will "simply" abort >the whole operation (reusing the speculation hardware) and start over, >instead of having to write an explicit loop.

Without actual hardware and software to try it's hard to assess how well
it's going to work, but the design sounds good: it should lead to more >compact code than LL/SC, be more general/friendly to lock-free coding
than T&S/C&S, and also compared to LL/SC it should behave better under
high contention because it is careful to guarantee overall forward
progress (in case of conflict between two cores, at least one of them
can finish successfully).

Ah, thanks, Stefan. That makes more sense.

Perhaps some day there will be hardware and systems software and
we can see how it actually works out in practice. I remain
skeptical given the example code that was posted, and it appears
that the claims are still just that: claims.

Regardless, if anyone has the sort of track record to
demonstrate that they can pull it off on the hardware side,
Alsup certainly does, so maybe my skepticism is overly
pessimistic and unwarranted.

- Dan C.

IIRC there's also some kind of mechanism to retry more cleverly, i.e. so
that when N cores are in conflicts, not only one of them succeeds, but
the N-1 remaining cores have a fighting chance of avoiding bumping into
each other next time around. I don't know the details, tho, and IIUC
this is not automatic: some relevant info is provided but it's up to the
code to do something useful with it.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

mitchalsup@aol.com (MitchAlsup1) writes:

On Tue, 18 Mar 2025 18:51:57 +0000, EricP wrote:

This affects what it can do with PCR inside the WoU if it causes a state
change that cannot be undone, for example, reading the interrupt data
FIFO.

Since the device is accessed through MMI/O space, and since My 66000
demands sequential consistency for MMI/O accesses, the LD of the
interrupt data FIFO cannot leave the confines of the core until
all pending memory references from the interrupted thread have
"been performed".

Be careful when relying on the ordering of outbound MMI/O accesses. They're not
ordered with respect to DMA accesses initiated from the device.

With PCI Express, software can also enable RO (Relaxed Ordering) which
changes the normal fairly strict ordering rules, particulary with respect
to non-posted transactions vis a vis posted transactions.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

mitchalsup@aol.com (MitchAlsup1) writes:

On Tue, 18 Mar 2025 21:59:51 +0000, Robert Finch wrote:

On 2025-03-18 2:51 p.m., EricP wrote:

----------------

Seems like it could work. There are difficulties using counters with the
Q+ ISA as multiple interrupt enable bits could be manipulated at the
same time. One interrupt may be enabled and another one disabled by the
same instruction.

I want to address the elephant in the room::

Why disable interrupts AT ALL !!

Because sometimes you need to. For example, when making a configuration
change to the device, you'll want to disable interrupts that may be
generated as a result of the configuration change (e.g. when flushing
a FIFO on the device, you may not want the 'FIFO Empty' interrupt
to be asserted).

Granted, there might be an enable gate on the device itself
that can be used for that, but generally speaking there are other cases
where it will make sense to disable delivery at the interrupt controller
or core (the later, particularly, during certain critical sections).

When running at any privilege, do you not want to accept an interrupt
at higher priority with as little delay as possible ??

Not while the core is executing an OS/hypervisor/device driver critical
section sensitive to interrupts.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

I want to address the elephant in the room::

Why disable interrupts AT ALL !!

So that you can have some mechanism for building critical
sections that span multiple instructions, where just having
access to atomics and spin locks isn't enough.

When running at any privilege, do you not want to accept an interrupt
at higher priority with as little delay as possible ??

Usually the assumption is that the critical section is short; a
handful of instructions, perhaps, so that the cost of blocking a
high priority interrupt is low.

Does Interrupt Disable help in this goal ??

This is predicated on an incomplete view of the situation and
the intersection between hardware and software. Serving high
priority interrupts quickly is not the only consideration.

Is there a SANE way to avoid disabling of interrupts ??

It depends on your definition of "sane" in this context. One
may imagine redesigning all of a system's locking primitives,
perhaps, to avoid the need to block interrupts in most cases.
But that pushes a lot of complexity onto software for dubious
benefit, and even then, it's not clear to me that they can be
blocked in _all_ cases.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

MitchAlsup1 [2025-03-17 21:49:18] wrote:

On Mon, 17 Mar 2025 18:33:09 +0000, EricP wrote:

Method 1 is simplest, it injects the interrupt request at Retire
as that's where the state of everything is synchronized.

[...]

Lowest interrupt Latency
Highest waste of power (i.e., work)

Method 2 pipelines the switch by injecting the interrupt request at
Fetch.

[...]

Interrupt latency is dependent on executing instructions,
Lowest waste of power

What do existing CPUs do?
Method 2 looks insanely messy, so I'd assume method 1 is the standard
approach, right?


Stefan

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Wed, 19 Mar 2025 13:49:54 +0000, Scott Lurndal wrote:

mitchalsup@aol.com (MitchAlsup1) writes:

On Tue, 18 Mar 2025 21:59:51 +0000, Robert Finch wrote:

On 2025-03-18 2:51 p.m., EricP wrote:

----------------

Seems like it could work. There are difficulties using counters with the >>> Q+ ISA as multiple interrupt enable bits could be manipulated at the
same time. One interrupt may be enabled and another one disabled by the
same instruction.

I want to address the elephant in the room::

Why disable interrupts AT ALL !!

Because sometimes you need to. For example, when making a configuration change to the device, you'll want to disable interrupts that may be
generated as a result of the configuration change (e.g. when flushing
a FIFO on the device, you may not want the 'FIFO Empty' interrupt
to be asserted).

The above is more quickly performed by raising the priority level above
those of interrupts a device may send.

{{This is part of my whole point--one can use priority as if it were enable/disable, and once you get priority setup as you perform inter-
rupt control transfer, you no longer need DI or EI.}}

Granted, there might be an enable gate on the device itself

As illustrated before, there are at least 7 gates between device and
a core.

that can be used for that, but generally speaking there are other cases
where it will make sense to disable delivery at the interrupt controller
or core (the later, particularly, during certain critical sections).

When running at any privilege, do you not want to accept an interrupt
at higher priority with as little delay as possible ??

Not while the core is executing an OS/hypervisor/device driver critical section sensitive to interrupts.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Wed, 19 Mar 2025 13:54:01 +0000, Scott Lurndal wrote:

mitchalsup@aol.com (MitchAlsup1) writes:

On Tue, 18 Mar 2025 18:51:57 +0000, EricP wrote:

This affects what it can do with PCR inside the WoU if it causes a state >>> change that cannot be undone, for example, reading the interrupt data
FIFO.

Since the device is accessed through MMI/O space, and since My 66000 >>demands sequential consistency for MMI/O accesses, the LD of the
interrupt data FIFO cannot leave the confines of the core until
all pending memory references from the interrupted thread have
"been performed".

Be careful when relying on the ordering of outbound MMI/O accesses.
They're not
ordered with respect to DMA accesses initiated from the device.

When device DMA gets translated into MMI/O space my HostBridge will
treat it as sequentially consistent.

When device DMA gets translated into DRAM space my HostBridge will
treat it as casually ordered.

With PCI Express, software can also enable RO (Relaxed Ordering) which changes the normal fairly strict ordering rules, particulary with
respect
to non-posted transactions vis a vis posted transactions.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Wed, 19 Mar 2025 14:03:56 +0000, Dan Cross wrote:

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

I want to address the elephant in the room::

Why disable interrupts AT ALL !!

So that you can have some mechanism for building critical
sections that span multiple instructions, where just having
access to atomics and spin locks isn't enough.

You can do this with priority, too.

When running at any privilege, do you not want to accept an interrupt
at higher priority with as little delay as possible ??

Usually the assumption is that the critical section is short; a
handful of instructions, perhaps, so that the cost of blocking a
high priority interrupt is low.

Does Interrupt Disable help in this goal ??

This is predicated on an incomplete view of the situation and
the intersection between hardware and software. Serving high
priority interrupts quickly is not the only consideration.

Is there a SANE way to avoid disabling of interrupts ??

It depends on your definition of "sane" in this context. One
may imagine redesigning all of a system's locking primitives,
perhaps, to avoid the need to block interrupts in most cases.
But that pushes a lot of complexity onto software for dubious
benefit, and even then, it's not clear to me that they can be
blocked in _all_ cases.

- Dan C.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

mitchalsup@aol.com (MitchAlsup1) writes:

On Wed, 19 Mar 2025 13:49:54 +0000, Scott Lurndal wrote:

mitchalsup@aol.com (MitchAlsup1) writes:

On Tue, 18 Mar 2025 21:59:51 +0000, Robert Finch wrote:

On 2025-03-18 2:51 p.m., EricP wrote:

----------------

Seems like it could work. There are difficulties using counters with the >>>> Q+ ISA as multiple interrupt enable bits could be manipulated at the
same time. One interrupt may be enabled and another one disabled by the >>>> same instruction.

I want to address the elephant in the room::

Why disable interrupts AT ALL !!

Because sometimes you need to. For example, when making a configuration
change to the device, you'll want to disable interrupts that may be
generated as a result of the configuration change (e.g. when flushing
a FIFO on the device, you may not want the 'FIFO Empty' interrupt
to be asserted).

The above is more quickly performed by raising the priority level above
those of interrupts a device may send.

Most device interrupts have the same priority. So your solution blocks
all interrupts effectively, even though only the interrupt for the particular device owned by the device driver needs to be blocked. Enabling really needs to be done on a per-device-instance basis.

There aren't enough priorities to have a separate priority for each
device instance (e.g. 1000 virtual functions owned by a single PF,
each with 10 individual interrupts).

If every device was required to have different priorities, you have
a nightmare scenario just trying to figure out which device interrupt
should be where in the priority hierarchy to avoid potential deadlocks.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Wed, 19 Mar 2025 15:20:20 +0000, Stefan Monnier wrote:

MitchAlsup1 [2025-03-17 21:49:18] wrote:

On Mon, 17 Mar 2025 18:33:09 +0000, EricP wrote:

Method 1 is simplest, it injects the interrupt request at Retire
as that's where the state of everything is synchronized.

[...]

Lowest interrupt Latency
Highest waste of power (i.e., work)

Method 2 pipelines the switch by injecting the interrupt request at
Fetch.

[...]

Interrupt latency is dependent on executing instructions,
Lowest waste of power

What do existing CPUs do?

Lean in the direction of method 2 will fallback position of method 1
if anything goes wrong.

Method 2 looks insanely messy, so I'd assume method 1 is the standard approach, right?

It is "not that bad" on the large scale of things.

Stefan

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Robert Finch wrote:

I am going for a simple approach. Since the CSR instruction is used to manipulate the interrupt enable bits in the status register, if there is
any CSR instruction in the pipeline, then interrupts will be masked off
until the CSR clears. One issue with this type of approach is evil
software could issue a lot of CSRs preventing interrupt servicing from happening. I Could fine tune the decode to sort out CSRs just affecting
the interrupt flags. It always seems to be more logic.

KISS is usually best - just single step the major actions.

I added single step to my uArch with a NotifyDecode flag in the uOp.
To single step Decode emits a special nop uOp with a NotifyDecode bit
and sets a Stop flip-flop that stalls Decode. The Fetch buffer fills up
and Fetch stalls itself. When the special nop reaches Retire we know all
older instructions are done. Retire sees the NotifyDecode bit and pulses
a wire that clears the Decode Stop FF.

Decode then emits the single step instruction uOp again with the
NotifyDecode bit and sets its Stop FF. When that uOp reaches Retire
it pulses the wire and clears the Decode Stop flag, which reads the
Fetch buffer and restarts the front end.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Wed, 19 Mar 2025 16:14:45 +0000, Scott Lurndal wrote:

mitchalsup@aol.com (MitchAlsup1) writes:

On Wed, 19 Mar 2025 13:49:54 +0000, Scott Lurndal wrote:

mitchalsup@aol.com (MitchAlsup1) writes:

On Tue, 18 Mar 2025 21:59:51 +0000, Robert Finch wrote:

On 2025-03-18 2:51 p.m., EricP wrote:

----------------

Seems like it could work. There are difficulties using counters with the >>>>> Q+ ISA as multiple interrupt enable bits could be manipulated at the >>>>> same time. One interrupt may be enabled and another one disabled by the >>>>> same instruction.

I want to address the elephant in the room::

Why disable interrupts AT ALL !!

Because sometimes you need to. For example, when making a configuration >>> change to the device, you'll want to disable interrupts that may be
generated as a result of the configuration change (e.g. when flushing
a FIFO on the device, you may not want the 'FIFO Empty' interrupt
to be asserted).

The above is more quickly performed by raising the priority level above >>those of interrupts a device may send.

Most device interrupts have the same priority. So your solution blocks
all interrupts effectively,

Only to the core that took the interrupt, other cores remain to take
those other exceptions--and only for the duration of the interrupt
processing. So if you have 100 cores, and one is processing SATA[k]
on core[j], there are 99 other cores that can take any pending
interrupt from that or other interrupt tables.

even though only the interrupt for the particular device owned by the device driver needs to be blocked.* Enabling really needs to be done on a per-device-instance basis.

Are you now arguing that interrupt en/disable should be processed at the device-instance ?? that is far from the core !!

Certainly if the device-instance has not been assigned to a core/VM
then it should not be sending interrupts (to anyone). This can be done
at any of the first 4 layers of interrupt enablement. Heck--it is
unlikely
to have an interrupt table assigned, and would get terminated by the
I/O MMU (if not before).

But during the assignment to a core/VM the device has the routing
(I/O MMU) to send interrupts that can be taken by a core running
that GuestOS/VM.

There aren't enough priorities to have a separate priority for each
device instance (e.g. 1000 virtual functions owned by a single PF,
each with 10 individual interrupts).

Priority only does the second order of the sort, allowing certain
interrupts to bypass in front of other interrupts. Interrupt table selection/assignment does a first level of sort. Then who is looking
at which table performs the third layer of the sort/routing.

If every device was required to have different priorities, you have
a nightmare scenario just trying to figure out which device interrupt
should be where in the priority hierarchy to avoid potential deadlocks.

Multiple device-instances will use different interrupt tables as each GuestOS/VM has at least its own interrupt table. In which case, the
priority in one table is orthogonal to the priority in another table.

(*) comming back to::

even though only the interrupt for the particular device owned by the device driver needs to be blocked.*

The interrupts are queued and until the priority of the core drops below
that of the pending interrupts, the driver is not stimulated into
activity
again (recursively or reentrantly).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Wed, 19 Mar 2025 17:27:46 +0000, Robert Finch wrote:

On 2025-03-19 12:00 p.m., MitchAlsup1 wrote:

On Wed, 19 Mar 2025 15:20:20 +0000, Stefan Monnier wrote:

MitchAlsup1 [2025-03-17 21:49:18] wrote:

On Mon, 17 Mar 2025 18:33:09 +0000, EricP wrote:

Method 1 is simplest, it injects the interrupt request at Retire
as that's where the state of everything is synchronized.

[...]

Lowest interrupt Latency
Highest waste of power (i.e., work)

Method 2 pipelines the switch by injecting the interrupt request at
Fetch.

[...]

Interrupt latency is dependent on executing instructions,
Lowest waste of power

What do existing CPUs do?

Lean in the direction of method 2 will fallback position of method 1
if anything goes wrong.

Method 2 looks insanely messy, so I'd assume method 1 is the standard
approach, right?

It is "not that bad" on the large scale of things.

Undaunted he tries to implement the method 2 approach using an IRQ
victim queue for IRQs that should not be processed at retire. It is not
too bad to code, but I dunno if it works yet. Just a switch at fetch
time to select from the victim queue first, otherwise pop the normal IRQ queue. The queue is small, assuming that IRQs are not disabled for great lengths of time.

Interrupt table MSI-X message undergoes negotiation.

One possible result of interrupt negotiation is that core can reject
said
interrupt, and message is returned to the interrupt table.

During this time, core is not doing anything but running its previously assigned thread. The negotiation takes place in state machines more
optimally positioned for throughput and latency than the function units
within cores. So, core has not done anything speculative wrt IROing
except that which has a well developed protocol.

Now, once core claims the interrupt, it performs as if it were the
typical von Neumann "perform 1 instructions then move on" Mantra
enforced by boatloads of reservations stations and predictors and
prediction repair mechanisms. Accessing memory with side effects
is not one of those mechanisms and must be ordered properly wrt
{interrupts, exceptions, mispredictions, and program order}.

But on the scale of a FDIV unit that sends out a 0.51 ULP result
on cycle 12 and can send out the 0.500 ULP result on cycle 17,
and fixing the intermediate damage--handing off to an interrupt
handler is "not that bad".

        Stefan

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)