On Tuesday, December 28, 2021 at 10:46:51 PM UTC-6, Stefan Monnier wrote:
> > With coherent TLBs, there are no IPI-shootdowns. In fact, no IPIs
> > at all in modifying MMU tables. You just write the MMU tables and
> > it is up to all the HW resources to "do the right thing".
> >
> > That SW prevents this is no reason HW guys should not be worried
> > about anomalous behavior.
> I still don't see what kind of anomalous behavior you're thinking of
> that's solved by special handling of (non-atomic) RMW.
<
Imagine the above scenario where SW did NOT perform the interlocking:
<
What semantic do you prescribe where a non-interrupted stream of instructions
forms 2 addresses from the same pattern, with none of the pattern registers
changing value, and touching different memory locations because some other
piece of SW altered the MMU tables "at just the right time".
>
>
> Stefan

MitchAlsup wrote:
> On Tuesday, December 28, 2021 at 6:43:24 PM UTC-6, EricP wrote:
>> Yes, its not the RMW sequence that is a problem, although the shootdown-IPI
>> does prevent that because the RMW is all before or all after the interrupt.
>> But a LD OP ST sequence could be paged out after the LD and page in
>> for the ST at a different physical address and it would not be harmed.
>>
>> The purpose of the shootdown-IPI handshake is to ensure that
>> all cores agree that there is just one translation for that address.
> <
> But consider the case where the TLBs are coherent. Anyone with TLB
> permission to anyone-else's MMU tables, can write to and instantly
> modify the other-guy's TLB entries. With multi-core operations, this
> could happen....

Yes but the problem is the *instantly* part - it takes time to
notify all SMP cores and that leaves a hole where one core uses
the old mapping and a different core uses the new mapping.
Waiting for the ACK's closes that hole.

Note also below the ACK must not be sent too quickly.

> <
> With coherent TLBs, there are no IPI-shootdowns. In fact, no IPIs
> at all in modifying MMU tables. You just write the MMU tables and
> it is up to all the HW resources to "do the right thing".

I was thinking this applied just to RMW instructions but I just
realized it actually applies to *ALL* load or store instructions.

Any LSQ entry that looks up a translation and is holding the physical
address before it is used is *also effectively a cached TLB entry*.
If a RMW instruction LSQ entry holds its translation while the
OP executes then it is just a longer duration cached copy.

When a remote TLB receives a shootdown coherence msg, it removes its
own matching entries but it must not ACK until it knows there are
no other copies of the PTE (address, access protections) in the LSQ.
The easiest way is to wait until LSQ empties but that could
have other consequences (it could take a long time for the ACK).

Also any ITLB copies that fetch buffers might have need to be zapped.

The PTE value must not be allowed to change until all ACKs are received,
just like when switching a cache line from Shared to Exclusive state.

> That SW prevents this is no reason HW guys should not be worried
> about anomalous behavior.

Right but HW taking over TLB coherence is a new responsibly
so it presents new anomalies.

EricP wrote:
> MitchAlsup wrote:
>> On Tuesday, December 28, 2021 at 6:43:24 PM UTC-6, EricP wrote:
>>> Yes, its not the RMW sequence that is a problem, although the
>>> shootdown-IPI does prevent that because the RMW is all before or all
>>> after the interrupt. But a LD OP ST sequence could be paged out after
>>> the LD and page in for the ST at a different physical address and it
>>> would not be harmed.
>>> The purpose of the shootdown-IPI handshake is to ensure that all
>>> cores agree that there is just one translation for that address.
>> <
>> But consider the case where the TLBs are coherent. Anyone with TLB
>> permission to anyone-else's MMU tables, can write to and instantly
>> modify the other-guy's TLB entries. With multi-core operations, this
>> could happen....
>
> Yes but the problem is the *instantly* part - it takes time to
> notify all SMP cores and that leaves a hole where one core uses
> the old mapping and a different core uses the new mapping.
> Waiting for the ACK's closes that hole.
>
> Note also below the ACK must not be sent too quickly.
>
>> <
>> With coherent TLBs, there are no IPI-shootdowns. In fact, no IPIs
>> at all in modifying MMU tables. You just write the MMU tables and
>> it is up to all the HW resources to "do the right thing".
>
> I was thinking this applied just to RMW instructions but I just
> realized it actually applies to *ALL* load or store instructions.
>
> Any LSQ entry that looks up a translation and is holding the physical
> address before it is used is *also effectively a cached TLB entry*.
> If a RMW instruction LSQ entry holds its translation while the
> OP executes then it is just a longer duration cached copy.
>
> When a remote TLB receives a shootdown coherence msg, it removes its
> own matching entries but it must not ACK until it knows there are
> no other copies of the PTE (address, access protections) in the LSQ.
> The easiest way is to wait until LSQ empties but that could
> have other consequences (it could take a long time for the ACK).

Actually it is more than this since in OoO a LD instruction can
bypass other LD's or ST's, access a physical address, complete,
and be removed from the LSQ.
But the value loaded in implicitly tied to the translation used
even if there is no trace of that physical address in the LSQ.

If the translation was allowed to change out of order
it could allow a younger LD to use an older translation,
and an older LD to use a younger translation.
Which would create an illegal coherence scenario.

So the TLB shootdown has to trigger a replay trap for all non-retired
instructions and wait for committed ST's to flush to cache
before sending the ACK.

> Also any ITLB copies that fetch buffers might have need to be zapped.
>
> The PTE value must not be allowed to change until all ACKs are received,
> just like when switching a cache line from Shared to Exclusive state.

The PTE writer can use Exclusive ownership of the PTE cache line to prevent
remote TLB's from reloading the PTE too quickly after a shootdown.

The PTE writer acquires Exclusive ownership and invalidates all
remote cached copies of the PTE cache line. Only after does it
purge the TLB entries, trigger a replay, and send its ACK.
The replay will try to retranslate the VA and the TLB will
try to reread the PTE cache line in a Shared state,
but will stall until the PTE writer finishes its change
which only occurs after it receives ACKs from all nodes.

On Wednesday, December 29, 2021 at 3:23:32 PM UTC-6, EricP wrote:
> EricP wrote:
> > MitchAlsup wrote:
> >> On Tuesday, December 28, 2021 at 6:43:24 PM UTC-6, EricP wrote:
> >>> Yes, its not the RMW sequence that is a problem, although the
> >>> shootdown-IPI does prevent that because the RMW is all before or all
> >>> after the interrupt. But a LD OP ST sequence could be paged out after
> >>> the LD and page in for the ST at a different physical address and it
> >>> would not be harmed.
> >>> The purpose of the shootdown-IPI handshake is to ensure that all
> >>> cores agree that there is just one translation for that address.
> >> <
> >> But consider the case where the TLBs are coherent. Anyone with TLB
> >> permission to anyone-else's MMU tables, can write to and instantly
> >> modify the other-guy's TLB entries. With multi-core operations, this
> >> could happen....
> >
> > Yes but the problem is the *instantly* part - it takes time to
> > notify all SMP cores and that leaves a hole where one core uses
> > the old mapping and a different core uses the new mapping.
> > Waiting for the ACK's closes that hole.
> >
> > Note also below the ACK must not be sent too quickly.
> >
> >> <
> >> With coherent TLBs, there are no IPI-shootdowns. In fact, no IPIs
> >> at all in modifying MMU tables. You just write the MMU tables and
> >> it is up to all the HW resources to "do the right thing".
> >
> > I was thinking this applied just to RMW instructions but I just
> > realized it actually applies to *ALL* load or store instructions.
> >
> > Any LSQ entry that looks up a translation and is holding the physical
> > address before it is used is *also effectively a cached TLB entry*.
> > If a RMW instruction LSQ entry holds its translation while the
> > OP executes then it is just a longer duration cached copy.
> >
> > When a remote TLB receives a shootdown coherence msg, it removes its
> > own matching entries but it must not ACK until it knows there are
> > no other copies of the PTE (address, access protections) in the LSQ.
> > The easiest way is to wait until LSQ empties but that could
> > have other consequences (it could take a long time for the ACK).
<
> Actually it is more than this since in OoO a LD instruction can
> bypass other LD's or ST's, access a physical address, complete,
> and be removed from the LSQ.
<
> But the value loaded in implicitly tied to the translation used
> even if there is no trace of that physical address in the LSQ.
<
Now you are at least catching on as to why there is a scenario to be
concerned about.
>
> If the translation was allowed to change out of order
> it could allow a younger LD to use an older translation,
> and an older LD to use a younger translation.
> Which would create an illegal coherence scenario.
>
> So the TLB shootdown has to trigger a replay trap for all non-retired
> instructions and wait for committed ST's to flush to cache
> before sending the ACK.
> > Also any ITLB copies that fetch buffers might have need to be zapped.
> >
> > The PTE value must not be allowed to change until all ACKs are received,
> > just like when switching a cache line from Shared to Exclusive state.
<
> The PTE writer can use Exclusive ownership of the PTE cache line to prevent
> remote TLB's from reloading the PTE too quickly after a shootdown.
<
I have been giving some thought to using a different state in the Dcache
for PTEs--which would convert an access response into "not right now"
to let the slings and arrows of doing these quiess before granting access.
>
> The PTE writer acquires Exclusive ownership and invalidates all
> remote cached copies of the PTE cache line. Only after does it
> purge the TLB entries, trigger a replay, and send its ACK.
<
Almost starts to smell ATOMIC..........
<
> The replay will try to retranslate the VA and the TLB will
> try to reread the PTE cache line in a Shared state,
> but will stall until the PTE writer finishes its change
> which only occurs after it receives ACKs from all nodes.

EricP wrote:
> EricP wrote:
>> MitchAlsup wrote:
>>> On Tuesday, December 28, 2021 at 6:43:24 PM UTC-6, EricP wrote:
>>>> Yes, its not the RMW sequence that is a problem, although the
>>>> shootdown-IPI does prevent that because the RMW is all before or all
>>>> after the interrupt. But a LD OP ST sequence could be paged out
>>>> after the LD and page in for the ST at a different physical address
>>>> and it would not be harmed.
>>>> The purpose of the shootdown-IPI handshake is to ensure that all
>>>> cores agree that there is just one translation for that address.
>>> <
>>> But consider the case where the TLBs are coherent. Anyone with TLB
>>> permission to anyone-else's MMU tables, can write to and instantly
>>> modify the other-guy's TLB entries. With multi-core operations, this
>>> could happen....
>>
>> Yes but the problem is the *instantly* part - it takes time to
>> notify all SMP cores and that leaves a hole where one core uses
>> the old mapping and a different core uses the new mapping.
>> Waiting for the ACK's closes that hole.
>>
>> Note also below the ACK must not be sent too quickly.
>>
>>> <
>>> With coherent TLBs, there are no IPI-shootdowns. In fact, no IPIs
>>> at all in modifying MMU tables. You just write the MMU tables and
>>> it is up to all the HW resources to "do the right thing".
>>
>> I was thinking this applied just to RMW instructions but I just
>> realized it actually applies to *ALL* load or store instructions.
>>
>> Any LSQ entry that looks up a translation and is holding the physical
>> address before it is used is *also effectively a cached TLB entry*.
>> If a RMW instruction LSQ entry holds its translation while the
>> OP executes then it is just a longer duration cached copy.
>>
>> When a remote TLB receives a shootdown coherence msg, it removes its
>> own matching entries but it must not ACK until it knows there are
>> no other copies of the PTE (address, access protections) in the LSQ.
>> The easiest way is to wait until LSQ empties but that could
>> have other consequences (it could take a long time for the ACK).
>
> Actually it is more than this since in OoO a LD instruction can
> bypass other LD's or ST's, access a physical address, complete,
> and be removed from the LSQ.
> But the value loaded in implicitly tied to the translation used
> even if there is no trace of that physical address in the LSQ.
>
> If the translation was allowed to change out of order
> it could allow a younger LD to use an older translation,
> and an older LD to use a younger translation.
> Which would create an illegal coherence scenario.
>
> So the TLB shootdown has to trigger a replay trap for all non-retired
> instructions and wait for committed ST's to flush to cache
> before sending the ACK.

Hmmm... this could deadlock.
If it had to flush committed ST's to cache before sending the ACK then
this could deadlock with the PTE writer holding the cache line Exclusive
awaiting those ACKs if the store was to the same PTE cache line.

The reason I'm concerned is if there are committed stores queued
to write to a physical page and the translation changes,
the PTE writer might think that the old page won't be written
any more but if fact there could many pending writes scattered
about the system in various hit-under-miss MSHR buffers.
That physical page might be reallocated for some other use
only to be stomped on by all those late writes.

>> Also any ITLB copies that fetch buffers might have need to be zapped.
>>
>> The PTE value must not be allowed to change until all ACKs are received,
>> just like when switching a cache line from Shared to Exclusive state.
>
> The PTE writer can use Exclusive ownership of the PTE cache line to prevent
> remote TLB's from reloading the PTE too quickly after a shootdown.
>
> The PTE writer acquires Exclusive ownership and invalidates all
> remote cached copies of the PTE cache line. Only after does it
> purge the TLB entries, trigger a replay, and send its ACK.
> The replay will try to retranslate the VA and the TLB will
> try to reread the PTE cache line in a Shared state,
> but will stall until the PTE writer finishes its change
> which only occurs after it receives ACKs from all nodes.

>> I still don't see what kind of anomalous behavior you're thinking of
>> that's solved by special handling of (non-atomic) RMW.
> <
> Imagine the above scenario where SW did NOT perform the interlocking:
> <
> What semantic do you prescribe where a non-interrupted stream of instructions
> forms 2 addresses from the same pattern, with none of the pattern registers
> changing value, and touching different memory locations because some other
> piece of SW altered the MMU tables "at just the right time".

Trying to address this for RMW seems pointless because the same problem
affects all the cases where the same logical address is used several times
from different instructions.

Stefan

On Wednesday, December 29, 2021 at 4:03:44 PM UTC-6, EricP wrote:
> EricP wrote:
> > EricP wrote:
> >> MitchAlsup wrote:
> >>> On Tuesday, December 28, 2021 at 6:43:24 PM UTC-6, EricP wrote:
> >>>> Yes, its not the RMW sequence that is a problem, although the
> >>>> shootdown-IPI does prevent that because the RMW is all before or all
> >>>> after the interrupt. But a LD OP ST sequence could be paged out
> >>>> after the LD and page in for the ST at a different physical address
> >>>> and it would not be harmed.
> >>>> The purpose of the shootdown-IPI handshake is to ensure that all
> >>>> cores agree that there is just one translation for that address.
> >>> <
> >>> But consider the case where the TLBs are coherent. Anyone with TLB
> >>> permission to anyone-else's MMU tables, can write to and instantly
> >>> modify the other-guy's TLB entries. With multi-core operations, this
> >>> could happen....
> >>
> >> Yes but the problem is the *instantly* part - it takes time to
> >> notify all SMP cores and that leaves a hole where one core uses
> >> the old mapping and a different core uses the new mapping.
> >> Waiting for the ACK's closes that hole.
> >>
> >> Note also below the ACK must not be sent too quickly.
> >>
> >>> <
> >>> With coherent TLBs, there are no IPI-shootdowns. In fact, no IPIs
> >>> at all in modifying MMU tables. You just write the MMU tables and
> >>> it is up to all the HW resources to "do the right thing".
> >>
> >> I was thinking this applied just to RMW instructions but I just
> >> realized it actually applies to *ALL* load or store instructions.
> >>
> >> Any LSQ entry that looks up a translation and is holding the physical
> >> address before it is used is *also effectively a cached TLB entry*.
> >> If a RMW instruction LSQ entry holds its translation while the
> >> OP executes then it is just a longer duration cached copy.
> >>
> >> When a remote TLB receives a shootdown coherence msg, it removes its
> >> own matching entries but it must not ACK until it knows there are
> >> no other copies of the PTE (address, access protections) in the LSQ.
<
If the ST already has a valid Phsical Address why is not allowed to complete.
<
> >> The easiest way is to wait until LSQ empties but that could
> >> have other consequences (it could take a long time for the ACK).
> >
> > Actually it is more than this since in OoO a LD instruction can
> > bypass other LD's or ST's, access a physical address, complete,
> > and be removed from the LSQ.
<
The LD should not be able to be removed from the queue until all stores
in the queue have known-physical-addresses. Yes, it can run early, but
it cannot run (bypass forward) over a store which will interfere with the
data the LD wants.
<
> > But the value loaded in implicitly tied to the translation used
> > even if there is no trace of that physical address in the LSQ.
<
The value loaded is tied to any older store in any queue {pre AGEN in
reservation station, and post AGEN in the miss queues.}
> >
> > If the translation was allowed to change out of order
> > it could allow a younger LD to use an older translation,
> > and an older LD to use a younger translation.
> > Which would create an illegal coherence scenario.
<
This gets you into the game of asking out-of-order with respect to whom ?
<
OoO wrt itself (same core)
OoO wrt any core in the system
> >
> > So the TLB shootdown has to trigger a replay trap for all non-retired
> > instructions and wait for committed ST's to flush to cache
> > before sending the ACK.
> Hmmm... this could deadlock.
> If it had to flush committed ST's to cache before sending the ACK then
> this could deadlock with the PTE writer holding the cache line Exclusive
> awaiting those ACKs if the store was to the same PTE cache line.
<
I think what we have here is a scenario where SW is not allowed to
modify MMU table entries while any thread using those tables are
in a runnable state. Threads need to be waiting for it to be legal to
alter their tables.
>
> The reason I'm concerned is if there are committed stores queued
> to write to a physical page and the translation changes,
> the PTE writer might think that the old page won't be written
> any more but if fact there could many pending writes scattered
> about the system in various hit-under-miss MSHR buffers.
<
Under the rule above: the ST cannot enter execution because the MMU
tables are being executed and the thread(s) is(are) in WAIT states.
<
> That physical page might be reallocated for some other use
> only to be stomped on by all those late writes.
> >> Also any ITLB copies that fetch buffers might have need to be zapped.
> >>
> >> The PTE value must not be allowed to change until all ACKs are received,
> >> just like when switching a cache line from Shared to Exclusive state.
> >
> > The PTE writer can use Exclusive ownership of the PTE cache line to prevent
> > remote TLB's from reloading the PTE too quickly after a shootdown.
> >
> > The PTE writer acquires Exclusive ownership and invalidates all
> > remote cached copies of the PTE cache line. Only after does it
> > purge the TLB entries, trigger a replay, and send its ACK.
> > The replay will try to retranslate the VA and the TLB will
> > try to reread the PTE cache line in a Shared state,
> > but will stall until the PTE writer finishes its change
> > which only occurs after it receives ACKs from all nodes.

MitchAlsup wrote:
> On Wednesday, December 29, 2021 at 4:03:44 PM UTC-6, EricP wrote:
>> EricP wrote:
>>>>
>>>> Any LSQ entry that looks up a translation and is holding the physical
>>>> address before it is used is *also effectively a cached TLB entry*.
>>>> If a RMW instruction LSQ entry holds its translation while the
>>>> OP executes then it is just a longer duration cached copy.
>>>>
>>>> When a remote TLB receives a shootdown coherence msg, it removes its
>>>> own matching entries but it must not ACK until it knows there are
>>>> no other copies of the PTE (address, access protections) in the LSQ.
> <
> If the ST already has a valid Phsical Address why is not allowed to complete.

I was looking for a way to make the delay to sending an ACK predictable.

A ST may have its physical address but it can't retire and commit
until all prior instructions have retired.

>>>> The easiest way is to wait until LSQ empties but that could
>>>> have other consequences (it could take a long time for the ACK).
>>> Actually it is more than this since in OoO a LD instruction can
>>> bypass other LD's or ST's, access a physical address, complete,
>>> and be removed from the LSQ.
> <
> The LD should not be able to be removed from the queue until all stores
> in the queue have known-physical-addresses. Yes, it can run early, but
> it cannot run (bypass forward) over a store which will interfere with the
> data the LD wants.

Oops right. There are a lot of causality balls to juggle.
Virtual addresses can resolve in any order and translate in any order.
Also its not just unknown stores that loads should not bypass.
Loads should not bypass any unknown addresses.

>>> But the value loaded in implicitly tied to the translation used
>>> even if there is no trace of that physical address in the LSQ.
> <
> The value loaded is tied to any older store in any queue {pre AGEN in
> reservation station, and post AGEN in the miss queues.}

This would be easier if we triggered a replay and tossed all the
in-flight values and any existing translations.

Then we'd only have to deal with the values in miss queues
as those are committed values from retired stores.
We don't know which, if any, of them is a store to the old page
that is retiring so we have to assume that all of them are.

We have to ensure all pending stores are complete and have
reached their coherence points and updated local cache.
Only when there are no references to the old page is
it available for reuse.

>>> If the translation was allowed to change out of order
>>> it could allow a younger LD to use an older translation,
>>> and an older LD to use a younger translation.
>>> Which would create an illegal coherence scenario.
> <
> This gets you into the game of asking out-of-order with respect to whom ?
> <
> OoO wrt itself (same core)
> OoO wrt any core in the system

Good question. I'm wondering if thinking about this as
versioning in a database is helpful.

>>> So the TLB shootdown has to trigger a replay trap for all non-retired
>>> instructions and wait for committed ST's to flush to cache
>>> before sending the ACK.
>> Hmmm... this could deadlock.
>> If it had to flush committed ST's to cache before sending the ACK then
>> this could deadlock with the PTE writer holding the cache line Exclusive
>> awaiting those ACKs if the store was to the same PTE cache line.
> <
> I think what we have here is a scenario where SW is not allowed to
> modify MMU table entries while any thread using those tables are
> in a runnable state. Threads need to be waiting for it to be legal to
> alter their tables.
>> The reason I'm concerned is if there are committed stores queued
>> to write to a physical page and the translation changes,
>> the PTE writer might think that the old page won't be written
>> any more but if fact there could many pending writes scattered
>> about the system in various hit-under-miss MSHR buffers.
> <
> Under the rule above: the ST cannot enter execution because the MMU
> tables are being executed and the thread(s) is(are) in WAIT states.

I want to reset and start again from scratch.
I'm going to assume that a replay trap is triggered and
tosses all in-flight instructions, values and translations.
Then we can add more complex scenarios back in later.

There is a lot of similarity in this to an OS managing files.
The PTE is acting like an OS file handle,
the copies of the physical address are like referenced counting
to OS kernel resources, the memory values are file contents.

Updating the PTE is like closing an old file handle and opening a new
handle to the same file without loosing any file updates made using
the old handle.

On Friday, December 31, 2021 at 11:38:55 AM UTC-6, EricP wrote:
> MitchAlsup wrote:
> > On Wednesday, December 29, 2021 at 4:03:44 PM UTC-6, EricP wrote:
> >> EricP wrote:
> >>>>
> >>>> Any LSQ entry that looks up a translation and is holding the physical
> >>>> address before it is used is *also effectively a cached TLB entry*.
> >>>> If a RMW instruction LSQ entry holds its translation while the
> >>>> OP executes then it is just a longer duration cached copy.
> >>>>
> >>>> When a remote TLB receives a shootdown coherence msg, it removes its
> >>>> own matching entries but it must not ACK until it knows there are
> >>>> no other copies of the PTE (address, access protections) in the LSQ.
> > <
> > If the ST already has a valid Phsical Address why is not allowed to complete.
> I was looking for a way to make the delay to sending an ACK predictable.
>
> A ST may have its physical address but it can't retire and commit
> until all prior instructions have retired.
<
Yes, It cannot retire, but it has everything it needs to retire.
<
> >>>> The easiest way is to wait until LSQ empties but that could
> >>>> have other consequences (it could take a long time for the ACK).
> >>> Actually it is more than this since in OoO a LD instruction can
> >>> bypass other LD's or ST's, access a physical address, complete,
> >>> and be removed from the LSQ.
> > <
> > The LD should not be able to be removed from the queue until all stores
> > in the queue have known-physical-addresses. Yes, it can run early, but
> > it cannot run (bypass forward) over a store which will interfere with the
> > data the LD wants.
<
> Oops right. There are a lot of causality balls to juggle.
> Virtual addresses can resolve in any order and translate in any order.
> Also its not just unknown stores that loads should not bypass.
> Loads should not bypass any unknown addresses.
<
In Mc 88120 we allowed LDs to bypass older LDs with unknown address,
But this become dangerous if the bypassed LD (or the LD at hand) are
to MMI/O address space (Or configuration address space).
<
> >>> But the value loaded in implicitly tied to the translation used
> >>> even if there is no trace of that physical address in the LSQ.
> > <
> > The value loaded is tied to any older store in any queue {pre AGEN in
> > reservation station, and post AGEN in the miss queues.}
<
> This would be easier if we triggered a replay and tossed all the
> in-flight values and any existing translations.
>
> Then we'd only have to deal with the values in miss queues
> as those are committed values from retired stores.
> We don't know which, if any, of them is a store to the old page
> that is retiring so we have to assume that all of them are.
>
> We have to ensure all pending stores are complete and have
> reached their coherence points and updated local cache.
> Only when there are no references to the old page is
> it available for reuse.
<
> >>> If the translation was allowed to change out of order
> >>> it could allow a younger LD to use an older translation,
> >>> and an older LD to use a younger translation.
> >>> Which would create an illegal coherence scenario.
> > <
> > This gets you into the game of asking out-of-order with respect to whom ?
> > <
> > OoO wrt itself (same core)
> > OoO wrt any core in the system
<
> Good question. I'm wondering if thinking about this as
> versioning in a database is helpful.
<
> >>> So the TLB shootdown has to trigger a replay trap for all non-retired
> >>> instructions and wait for committed ST's to flush to cache
> >>> before sending the ACK.
> >> Hmmm... this could deadlock.
> >> If it had to flush committed ST's to cache before sending the ACK then
> >> this could deadlock with the PTE writer holding the cache line Exclusive
> >> awaiting those ACKs if the store was to the same PTE cache line.
> > <
> > I think what we have here is a scenario where SW is not allowed to
> > modify MMU table entries while any thread using those tables are
> > in a runnable state. Threads need to be waiting for it to be legal to
> > alter their tables.
> >> The reason I'm concerned is if there are committed stores queued
> >> to write to a physical page and the translation changes,
> >> the PTE writer might think that the old page won't be written
> >> any more but if fact there could many pending writes scattered
> >> about the system in various hit-under-miss MSHR buffers.
> > <
> > Under the rule above: the ST cannot enter execution because the MMU
> > tables are being executed and the thread(s) is(are) in WAIT states.
<
> I want to reset and start again from scratch.
> I'm going to assume that a replay trap is triggered and
> tosses all in-flight instructions, values and translations.
> Then we can add more complex scenarios back in later.
<
Brutal, but often effective--especially if the scenario occurs seldomly.
>
> There is a lot of similarity in this to an OS managing files.
> The PTE is acting like an OS file handle,
> the copies of the physical address are like referenced counting
> to OS kernel resources, the memory values are file contents.
>
> Updating the PTE is like closing an old file handle and opening a new
> handle to the same file without loosing any file updates made using
> the old handle.
<
And the question at hand is, what does the "system" do with all the writes
to the file between the closing of one handle and the opening of another ??
And it is not allowed to lose the order of the writes, either.

>> A ST may have its physical address but it can't retire and commit
>> until all prior instructions have retired.
><
>Yes, It cannot retire, but it has everything it needs to retire.

?What is meant by retire or commit? In my cores I allow the ST operation
to be completed if there is no possibility of flow control change in prior
instructions. Memory may be updated even if prior instructions have not
completed yet.

robf...@gmail.com wrote:
>>> A ST may have its physical address but it can't retire and commit
>>> until all prior instructions have retired.
>> <
>> Yes, It cannot retire, but it has everything it needs to retire.
>
>
> ?What is meant by retire or commit? In my cores I allow the ST operation
> to be completed if there is no possibility of flow control change in prior
> instructions. Memory may be updated even if prior instructions have not
> completed yet.

Similar. The difference sounds like how and when exceptions are detected.

I think of Retire as the point where the oldest instruction is removed
from the queue, and if it had no exceptions updates the program state.
For a ST instruction it initiates the sequence that ultimately
writes a value to an address.

My method only looks at the oldest instruction to see if
it has an exception, and tosses any changes if it does.

Your method requires knowing that no future partially complete
instructions can trigger an exception or trigger a replay,
which allows it to initiate a non-reversible state change ASAP.

On Friday, December 31, 2021 at 7:21:32 PM UTC-6, robf...@gmail.com wrote:
> >> A ST may have its physical address but it can't retire and commit
> >> until all prior instructions have retired.
> ><
> >Yes, It cannot retire, but it has everything it needs to retire.
<
> ?What is meant by retire or commit? In my cores I allow the ST operation
> to be completed if there is no possibility of flow control change in prior
> instructions. Memory may be updated even if prior instructions have not
> completed yet.
<
Comit is the point where there are no older instructions that could cause
the ST not to be performed due to raising of an exception.
<
Retire is the point where the ST can be performed to unbackupable memory.

On Saturday, January 1, 2022 at 2:12:29 PM UTC-5, MitchAlsup wrote:
> On Friday, December 31, 2021 at 7:21:32 PM UTC-6, robf...@gmail.com wrote:
> > >> A ST may have its physical address but it can't retire and commit
> > >> until all prior instructions have retired.
> > ><
> > >Yes, It cannot retire, but it has everything it needs to retire.
> <
> > ?What is meant by retire or commit? In my cores I allow the ST operation
> > to be completed if there is no possibility of flow control change in prior
> > instructions. Memory may be updated even if prior instructions have not
> > completed yet.
> <
> Comit is the point where there are no older instructions that could cause
> the ST not to be performed due to raising of an exception.
> <
> Retire is the point where the ST can be performed to unbackupable memory.

Thanks, I have some difficulty understanding the difference between commit
and retire, but I think I have got it now. Commit means the machine is dedicated
to performing the instruction. The instruction might be executed but registers
are not written yet. Retire means the machine state is updated, registers
updated. Normally stores do not update memory until they retire. I called the
retire stage in my core commit, oh well. Now I am confusing commit and issue.

There are many instructions that fall under the category of not causing
exceptions or changes of flow control. For my machine, there is a signal
coming out of the decoder (canex) that indicates such. Instructions such as
unsigned multiply and divide, add, and, shifts, etc. qualify. However, if debug
mode is on then potentially any instruction can cause an exception – single
stepping, so then stores do not update memory until they are ready to retire.

On Saturday, January 1, 2022 at 5:07:35 PM UTC-6, robf...@gmail.com wrote:
> On Saturday, January 1, 2022 at 2:12:29 PM UTC-5, MitchAlsup wrote:
> > On Friday, December 31, 2021 at 7:21:32 PM UTC-6, robf...@gmail.com wrote:
> > > >> A ST may have its physical address but it can't retire and commit
> > > >> until all prior instructions have retired.
> > > ><
> > > >Yes, It cannot retire, but it has everything it needs to retire.
> > <
> > > ?What is meant by retire or commit? In my cores I allow the ST operation
> > > to be completed if there is no possibility of flow control change in prior
> > > instructions. Memory may be updated even if prior instructions have not
> > > completed yet.
> > <
> > Comit is the point where there are no older instructions that could cause
> > the ST not to be performed due to raising of an exception.
> > <
> > Retire is the point where the ST can be performed to unbackupable memory.
<
> Thanks, I have some difficulty understanding the difference between commit
> and retire, but I think I have got it now. Commit means the machine is dedicated
> to performing the instruction. The instruction might be executed but registers
> are not written yet. Retire means the machine state is updated, registers
> updated. Normally stores do not update memory until they retire. I called the
> retire stage in my core commit, oh well. Now I am confusing commit and issue.
<
In the Mc 88120, stores could be written into the conditional cache where younger
loads could access them, but this was a place where stores could still be "thrown
away" due to exceptions or even branch mispredictions. These were executed even
prior to commit.
<
Between comit and retire, stores from the conditional cache would be migrated to
the <real> cache or to main memory depending on set-overload.
<
At retire, all the resources being used to track the instruction in progress is made
available to a new instruction (so it can enter the execution window).
<
This is how we (Mike Shebanow and I) defined the nomenclature in 1991. While doing
the Mc 88120 we did not understand the subtle difference until over a year into the
design.
>
> There are many instructions that fall under the category of not causing
> exceptions or changes of flow control. For my machine, there is a signal
> coming out of the decoder (canex) that indicates such. Instructions such as
> unsigned multiply and divide, add, and, shifts, etc. qualify. However, if debug
> mode is on then potentially any instruction can cause an exception – single
> stepping, so then stores do not update memory until they are ready to retire.
<
You are using the word "retire" to mean it is safe to comit state (visible outside
the execution of this thread).
This is what I use the word "comit" to indicate--it is safe to comit the store
to memory that cannot be undone (visible outside of this thread)
I (we) then use the word retire to denote the point where execution resources are
delivered back so new instruction can use them.
<
This may not be the nomenclature used by UCB or Stanford.

robf...@gmail.com wrote:
> On Saturday, January 1, 2022 at 2:12:29 PM UTC-5, MitchAlsup wrote:
>> On Friday, December 31, 2021 at 7:21:32 PM UTC-6, robf...@gmail.com wrote:
>>>>> A ST may have its physical address but it can't retire and commit
>>>>> until all prior instructions have retired.
>>>> <
>>>> Yes, It cannot retire, but it has everything it needs to retire.
>> <
>>> ?What is meant by retire or commit? In my cores I allow the ST operation
>>> to be completed if there is no possibility of flow control change in prior
>>> instructions. Memory may be updated even if prior instructions have not
>>> completed yet.
>> <
>> Comit is the point where there are no older instructions that could cause
>> the ST not to be performed due to raising of an exception.
>> <
>> Retire is the point where the ST can be performed to unbackupable memory.
>
> Thanks, I have some difficulty understanding the difference between commit
> and retire, but I think I have got it now. Commit means the machine is dedicated
> to performing the instruction. The instruction might be executed but registers
> are not written yet. Retire means the machine state is updated, registers
> updated. Normally stores do not update memory until they retire. I called the
> retire stage in my core commit, oh well. Now I am confusing commit and issue.
>
> There are many instructions that fall under the category of not causing
> exceptions or changes of flow control. For my machine, there is a signal
> coming out of the decoder (canex) that indicates such. Instructions such as
> unsigned multiply and divide, add, and, shifts, etc. qualify. However, if debug
> mode is on then potentially any instruction can cause an exception – single
> stepping, so then stores do not update memory until they are ready to retire.

The terms Commit and Retire are often used interchangeably.

While Retire is thought of as a single step where the new state is
made permanent and resources allocated to an instruction are recovered,
depending on the uArch and instruction it can require multiple steps.

A ST instruction in particular can linger in the Load-Store Queue
after its Instruction Queue entry has been retired and deleted,
waiting to be passed to the memory subsystem. And there could
be multiple committed ST operations waiting ahead it it.
After it is transferred to memory subsystem the LSQ entry is recovered.

Looking at a diagram of the IBM z15 pipeline I see 10 stages
for "Completion" and "Checkpointing".

https://www.servethehome.com/ibm-z15-mainframe-processor-design/hot-chips-32-ibm-z15-processor-pipeline/

Note also that there is a difference between when a ST instruction
retires and starts to transfer a new value to memory,
and when that new value becomes coherently visible to all cores
as the "One True Value" of an address.

"robf...@gmail.com" <robfi680@gmail.com> writes:
>Thanks, I have some difficulty understanding the difference between commit
>and retire

That's not surprising, because it's the same point in time, and
therefore people (including me) use these words as synonyms. Commit
is when the architectural effect of the instruction becomes permanent.
After that there is no point in keeping the instruction around, so the
instruction can retire.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On Monday, January 3, 2022 at 7:19:43 AM UTC-6, Anton Ertl wrote:
> "robf...@gmail.com" <robf...@gmail.com> writes:
> >Thanks, I have some difficulty understanding the difference between commit
> >and retire
> That's not surprising, because it's the same point in time, and
> therefore people (including me) use these words as synonyms. Commit
> is when the architectural effect of the instruction becomes permanent.
s/can/is allowed to/
> After that there is no point in keeping the instruction around, so the
> instruction can retire.
One may have a number of instructions that retire together and some other
instruction can be holding up the STs retirement.
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

On 1/3/2022 5:13 AM, Anton Ertl wrote:
> "robf...@gmail.com" <robfi680@gmail.com> writes:
>> Thanks, I have some difficulty understanding the difference between commit
>> and retire
>
> That's not surprising, because it's the same point in time, and
> therefore people (including me) use these words as synonyms. Commit
> is when the architectural effect of the instruction becomes permanent.
> After that there is no point in keeping the instruction around, so the
> instruction can retire.
>
> - anton

Commit is when it *will* happen. Retire is when it *has* happened.

MitchAlsup wrote:
> On Friday, December 31, 2021 at 11:38:55 AM UTC-6, EricP wrote:
>> Also its not just unknown stores that loads should not bypass.
>> Loads should not bypass any unknown addresses.
> <
> In Mc 88120 we allowed LDs to bypass older LDs with unknown address,
> But this become dangerous if the bypassed LD (or the LD at hand) are
> to MMI/O address space (Or configuration address space).

Its not just MMIO, its that loads to the same address must be
performed in program order in case the cache line is grabbed away.
A load-load bypass could allow a younger load to read an older value and
an older load to read a younger value, a coherence violation under TSO-86.

#1 LD r0,[r1] // r1 is not yet resolved
#2 LD r2,[r3] // r3 = 1234

R0 address pending and R3 set to address 1234.
If LD#2 is allowed to proceed, R2 reads the old value from 1234.
Then that cache line is grabbed away by another core and changed.
Later R1 resolves to 1234 and R0 loads the new value.
Result is R2 has old value for 1234 and R1 has new value.

Its not just unresolved addresses that cause this,
they just make the window of vulnerability wider.
An LSQ scheduler which chose resolved entries to service
in the wrong order might cause it too.

To prevent the coherence violation one can block the load from
bypassing all older unresolved load and store addresses,
AND LSQ scheduler enforces older to younger ordering to the same address
(just in case the line is grabbed away between entries).

Or the load bypass could put a watch point on the cache line
that triggers a replay trap if the line gets invalidated.
But the watch point must be removed somehow at the right time
and that is probably more complicated.

MitchAlsup wrote:
> On Monday, January 3, 2022 at 7:19:43 AM UTC-6, Anton Ertl wrote:
>> "robf...@gmail.com" <robf...@gmail.com> writes:
>>> Thanks, I have some difficulty understanding the difference between commit
>>> and retire
>> That's not surprising, because it's the same point in time, and
>> therefore people (including me) use these words as synonyms. Commit
>> is when the architectural effect of the instruction becomes permanent.
> s/can/is allowed to/
>> After that there is no point in keeping the instruction around, so the
>> instruction can retire.
> One may have a number of instructions that retire together and some other
> instruction can be holding up the STs retirement.

Just to muddy the water, there is also some research on
Out-of-Order Commit/Retire such as this one by Gordon Bell:

Deconstructing Commit, GB Bell, MH Lipasti, 2004
https://pharm.ece.wisc.edu/papers/ispass2004gbell.pdf

The rules for OOC concern:
- WAR hazards
- unresolved older branches
- exceptions from older instructions
- replay traps from older instructions used to enforce
the memory consistency model (like load-load bypass ordering).

One of the advantages of OOC is early resource recovery but the
problem is that simple structures like circular buffers don't work.
Their proposed solution is compacting buffers, basically FIFO
shift registers that pack down to eliminate any deleted holes.

They say a "collapsing the ROB does not add significant complexity"
but I think it is considerably more expensive than a circular buffer
especially if you want to allow multiple deletions/retires at once
(takes lots and lots of muxes to do that).

On Tuesday, January 4, 2022 at 10:46:37 AM UTC-6, EricP wrote:
> MitchAlsup wrote:
> > On Friday, December 31, 2021 at 11:38:55 AM UTC-6, EricP wrote:
> >> Also its not just unknown stores that loads should not bypass.
> >> Loads should not bypass any unknown addresses.
> > <
> > In Mc 88120 we allowed LDs to bypass older LDs with unknown address,
> > But this become dangerous if the bypassed LD (or the LD at hand) are
> > to MMI/O address space (Or configuration address space).
<
> Its not just MMIO, its that loads to the same address must be
> performed in program order in case the cache line is grabbed away.
> A load-load bypass could allow a younger load to read an older value and
> an older load to read a younger value, a coherence violation under TSO-86.
>
> #1 LD r0,[r1] // r1 is not yet resolved
> #2 LD r2,[r3] // r3 = 1234
>
> R0 address pending and R3 set to address 1234.
> If LD#2 is allowed to proceed, R2 reads the old value from 1234.
> Then that cache line is grabbed away by another core and changed.
> Later R1 resolves to 1234 and R0 loads the new value.
> Result is R2 has old value for 1234 and R1 has new value.
>
> Its not just unresolved addresses that cause this,
> they just make the window of vulnerability wider.
> An LSQ scheduler which chose resolved entries to service
> in the wrong order might cause it too.
<
What we did in the Mc 88120 was: When a LD result had been delivered,
and the LD remained unRetireable AND there was a SNOOP to the cache
line the LD consumed; the window was backed up to the beginning of the
packet containing the LD instruction. In the K9 design, we did a similar
backup, but just marked all the affected instructions are unExecuted
(rather than flushing and reInserting them into the window.)
>
> To prevent the coherence violation one can block the load from
> bypassing all older unresolved load and store addresses,
> AND LSQ scheduler enforces older to younger ordering to the same address
> (just in case the line is grabbed away between entries).
<
These cases happen so seldomly, that using the brute hand of mispredict
seems in-order. And when they do occur, doing them fast is never as good
as appearing as if the instruction stream is always in-order.
>
> Or the load bypass could put a watch point on the cache line
> that triggers a replay trap if the line gets invalidated.
> But the watch point must be removed somehow at the right time
> and that is probably more complicated.

On Tuesday, January 4, 2022 at 10:56:46 AM UTC-6, EricP wrote:
> MitchAlsup wrote:
> > On Monday, January 3, 2022 at 7:19:43 AM UTC-6, Anton Ertl wrote:
> >> "robf...@gmail.com" <robf...@gmail.com> writes:
> >>> Thanks, I have some difficulty understanding the difference between commit
> >>> and retire
> >> That's not surprising, because it's the same point in time, and
> >> therefore people (including me) use these words as synonyms. Commit
> >> is when the architectural effect of the instruction becomes permanent.
> > s/can/is allowed to/
> >> After that there is no point in keeping the instruction around, so the
> >> instruction can retire.
> > One may have a number of instructions that retire together and some other
> > instruction can be holding up the STs retirement.
> Just to muddy the water, there is also some research on
> Out-of-Order Commit/Retire such as this one by Gordon Bell:
>
> Deconstructing Commit, GB Bell, MH Lipasti, 2004
> https://pharm.ece.wisc.edu/papers/ispass2004gbell.pdf
>
> The rules for OOC concern:
> - WAR hazards
renaming registers and memory eliminates this.
> - unresolved older branches
I never tried to retire anything still covered by the shadow of a branch.
> - exceptions from older instructions
See unresolved older branches.
> - replay traps from older instructions used to enforce
I never tried to retire anything still in the shadow of a potential exception.
> the memory consistency model (like load-load bypass ordering).
>
> One of the advantages of OOC is early resource recovery but the
> problem is that simple structures like circular buffers don't work.
> Their proposed solution is compacting buffers, basically FIFO
> shift registers that pack down to eliminate any deleted holes.
<
We used the exception flags, and some memory state/memory-ref
to decide if all instructions in a packet were ready to retire, then we
retired them en massé. The circuits I used look similar to that found
in the Bell paper.
>
> They say a "collapsing the ROB does not add significant complexity"
> but I think it is considerably more expensive than a circular buffer
> especially if you want to allow multiple deletions/retires at once
> (takes lots and lots of muxes to do that).
<
A lot of this is dependent on how long it takes to backup your execution
window. Mc 88120 could perform a ranch instruction in cycle[k] and
both backup the execution window AND insert instructions from the
alternate packet in cycle[k+1]--that is zero cycles wasted on recovery.
In order to do this, one needs the source register decoders in the RF
to be CAMs......