Re: MSI interrupts

On Thu, 27 Mar 2025 17:19:21 +0000, Dan Cross wrote:

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

On Wed, 26 Mar 2025 4:08:57 +0000, Dan Cross wrote:

[snip]
1. `from` may point to a cache line
2. `to` may point to a different cache line.
3. Does your architecture use a stack?

>
No

>
You make multiple references to a stack just below.  I
understand stack references are excluded from the atomic event,
but I asked whether the architecture uses a stack.  Does it, or
doesn't it?
>

   What sort of alignment criteria do you impose?

>
On the participating data none. On the cache line--cache line.

>
I meant for data on the stack.  The point is moot, though, since
as you said stack data does not participate in the atomic event.

Stack does not NECESSARILY participate. However, if you perform
a esmLOCKload( SP[23] ) then that line on the stack is participating.

   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.

>
The illustrated code is using 6 participating cache lines.
Where local variables are kept (stack, registers) does not
count against the tally of participating cache lines.

>
Huh.

There are 6 esmLOCKxxxxx() so there are 6 participating lines--
and these are absolutely independent from where the variables
are located. The variables carry information but do not part-
ticipate they carry data between operations on the particupating
lines.

      How would this handle something like an MCS lock, where
the lock node may be on a stack, though accessible globally in
some virtual address space?

As illustrated above esmLOCKload( SP[23]) will cause a line on
the stack to participate in the event.
----------------

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

>
If you want that property--you use the tools at hand.
If you don't just use them as primitive generators.

>
I wasn't clear enough here.  I'm asking what, exactly, you mean
by this _property_,

The property that if an interrupt (or exception or SVC or SVR)
prevents executing the event to its conclusion, HW makes the
event look like it never started. So that when/if control returns
we have another chance to execute the event as-if ATOMICally.

                    not what you mean when you write that one
can use these atomic events if one wants the property.  That is,
I'm asking you to precisely define what it means for a lock to
"disappear".
>
It seems clear enough _now_ that once the event concludes
successfully the lock value is set to whatever it was set to in
during the event, but that wasn't clear to me earlier and I
wanted confirmation.

Not "the lock value" but "all participating values" are set
and become visible system-wide in a single instant. No 3rd
party sees some set and others remain unset. Everybody sees
all of then change value between this-clock and its successor.

In particular, it seems odd to me that one would bother with a
lock of some kind during an event if it didn't remain set after
the event.

Consider CompareTripleSwapFour() as an atomic primitive. How
would you program this such that nobody nowhere could ever
tell that the four updated locations changes in any order
then simultaneously ??? Without using a LOCK to guard the
event ??? And without demanding that all four updates are
to the same cache line ???
{{Nobody nowhere included ATOMIC-blind DMA requests}}

            If you do all of your critical section stuff inside
of the event, and setting the lock in the event is not visible
until the event concludes, why bother?  If on the other hand you
use the event to set the lock, why bother doing additional work
inside the event itself, but in this case I definitely don't
want something else to come along and just unset the lock on its
own, higher priority or not.

It is clear you do not understand the trouble HW takes to implement
even DCADS where between any 2 clocks, one (or more) SNOOPs can
take the lines you are DCADSing. It is this property of cache
coherence that gets in the way of multi-operation ATOMIC events.
In 2004 Fred Weber came to me and ask: "Why can't we (AMD) give
Microsoft the DCADS they want. I dug into it, and ASF was my
solution in x86 ISA, ESM is my solution in RISC-based ISA. It
removes the need to add ATOMIC primitives to ISA over generations.
It also provides the ability to do other things--which apparently
you will not use--sort of like complaining that your new car has
auto-park a feature you will never use.

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.

>
One can use a esmLOCKstore( *SP, 0 ) to abandon an event. HW
detects that *SP is not participating in the event, and uses
the lock bit in the instruction to know it is time to leave
the event in the failed manner. No ST is performed to the
non-participating cache line. {{I guess I could wrap the
abandonment into a macro ...}}

>
>
Again, not what I was asking.  I'm trying to understand what you
meant when you talked about disappearing locks.

If the event cannot be completed due to interrupt or exception or
SCVC or SVR, the HW backs up the event such that is looks like
it never started. SO when control return, the ATOMIC event runs
in its entirety ATOMICally !! So, the illusion of ATOMICITY is
preserved.

Again, I think you meant that, if an atomic event that sets a
lock variable fails,

The event has NO lock variable--it has up to 8 cache line address
monitors.

                     whether it got far enough along to set the
variable inside the event or not is not observable if the event
fails.

Non-participating cache lines can be used to leak information
out of the event (like for debug purposes). Participating data
does not leak.

        But if the event succeeds, then the variable is set and
that's that.  IF that's the case, then great!  But if not, then
disappearing locks are bad.

It is NOT a FRIGGEN LOCK--it is a set of address monitors which
are used to determine the success of the event -- the monitors
remain invisible to SW just like miss buffers remain invisible
to SW. The monitors are not preservable across privilege changes.

                             This is especially murky to me
because there seem to be bits of OS primitives, like threads and
priority, that are known directly to the hardware.

Just its instantaneous privilege level--which is congruent to
its register file, Root Pointer, ASID, and operating modes.
------------------

>
Ok, so perhaps this is a reasonable implementation of spinlock
acquire, as I wrote to Stefan yesterday:
>
void
spinlock_acquire(volatile Spinlock *lk)
{
while (esmLOCKload(&lk->lock) != 0)
cpu_spin_hint();
esmLOCKstore(&lk->lock, 1);
}
>
Yes?  If this is preempted, or another CPU wins the race on the
lock, the hardware will back this up and start over in the while
loop, right?

Yes.
------------

Remember only the lines participating in the event count. For
example, say one had sprintf() inside the event. None of the
lines touched by springt() are participating in the event,
and are not counted against the 8 cache lines available.

>
This doesn't change the point, though.  Anything that touches
more than 8 cache lines is not suitable for an atomic event.

I see what you are saying, but the event is allowed to have an
unbounded amount of touches to non-participating lies.

Insertion into a doubly linked list is already up to 6 lines,

I moved a doubly linked element from a CDS and inserted it
somewhere else doubly-linked in same CDS in 6 cache lines.
You need to refine how you count.
BOOLEAN InsertElement( Element *el, Element *to )
{
     tn = esmLOCKload( to->next );
     esmLOCKprefetch( el );
     esmLOCKprefetch( tn );
     if( !esmINTERFERENCE() )
     {
                   el->next = tn;
                   el->prev = to;
                   to->next = el;
     esmLOCKstore( tn->prev,  el );
                   return TRUE;
     }
     return FALSE;
}

recall that my original hypothetical also involved popping off a
queue, which adds another (the queue head).  If I threw up
incrementing a couple of counters I can't do it.  And this seems
like a perfectly reasonable real-world scenario; consider a work
stealing thread scheduler that takes a task from one core to
another and keeps some stats on how things move.
>
Or maybe even just swapping places between two elements in a
linked list.  For example:

The example has 3 structures each requiring 3 participating lines.
{themself, the struct their next pointer points at and the struct
their prev pointer points at}
3×3 = 9 and there is no getting around it.
-------------------------

>
But there isn't a lot of publicly available documentation for
any of this, at least none that I could find, and from the way
it's been described thus far it seems like there are a number of
edge cases that it is not clear how one is supposed to address.
So I want to understand the boundaries of where these hardware
facilities are applicable, given architectural limitations.  I
think this thread has shown that those boundaries exist.  The
universe of interesting and useful software is big, and someone,
somewhere, is going to trip over those limitations sooner or
later.  Once we accept that, we must ask, "Then what?"  It seems
obvious that programmers are going to have to find techniques to
work around those limitations, and that the mechanisms chosen
are unknowable to hardware.

Fair enough.

But now we're back in the same boat of software having to deal
with all the thorny problems that these mechanisms were designed
to address in the first place, like priority inversion: take the
spinlock from earlier, the hardware has no semantic knowledge
that the lock is used as a mutex, and can't know; it's just some
bit in memory somewhere that was set during an atomic event.

It is not a FRIGGEN lock, it is a set of address monitors which
guard the instructions in the event. A Lock is a SW concept
which requires a value change to announce to others that "you
got it".

Maybe ESM helps in a race when trying to acquire the spinlock,
but once it's acquired, it's acquired, and because the spinlock
is not a primitive understood by the hardware, the hardware has
no way of incorporating the spinlock's semantics into its view
of priority, threading, etc.

Consider a 1024 core system and the time-quantum goes off and
every core wants to rotate the thread it is running; putting
it at the back of the execution queue and taking off the one on
the front to run. Nick McLaren timed a big SUN server (100 core)
on this and it could take up to 6 seconds !! for something that
should take a few milliseconds. This is because of the BigO( n^3 )
nature of bus traffic wrt SNOOPing on that system.
One can use ESM to convert that particular case to BigO( 3 )
or in the general case of random insert and removal times:
BigO( ln( n ) ).

So while an atomic event might help me in the implementation of
a generic mutex of some kind, so that I can protect critical
sections that can't be handled with the atomic event framework
directly because of their size, that's the extent of the help it
can give me, because once the mutex is acquired the hardware has
no insight into the fact that it's a mutex.

Exactly:: once you convert address-based mutual exclusion to
data-based mutual exclusion, HW no longer sees it at all.

                                             So if some higher
priority thing subsequently comes along and preempts the thread
holding that lock and tries to take that lock itself, then the
hardware can't help me out anymore, and I'm back to a
priority-inversion deadlock that has to be dealt with by
software.

HW can only "take" address based locking, not data-based locking.

The point is, even if the hardware gives me a cool
mechanism for helping prevent priority inversion problems,
programmers are inevitably going to have to handle those
situations themselves anyway.

Never promised you a rose garden.

This is the sort of thing I'm trying to communicate, it's really
not me sitting here tossing out barbs like, "oh yeah?!  Well,
how about THIS one, smart guy?"

Look at it this way:: over the decade from 2000-2010 x86 added
a new ATOMIC instruction every iteration.
Using ASF or ESM; my architecture would never have to add one.
SW has the tools to build what it wants/needs.

>
- Dan C.