Re: MSI interrupts

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.