https://comsec.ethz.ch/research/microarch/retbleed/ (A foaf actually
wrote the exploit code for this). It seems there is no end to
this. Intel and AMD are affected, and mitigation is expensive,
14% and 39% overhead measured. Bah.

@Mitch: How expensive would not allowing speculative execution to
update microarchitectural state be?

I am thinking about stores; I assume that most stores on OoO
architectures are speculative, so a sizable buffer (a second L1
cache, if you will) would have to be set aside. Do you have
an estimate how big and expensive that would have to be?

On Saturday, July 16, 2022 at 1:06:58 PM UTC-5, Thomas Koenig wrote:
> https://comsec.ethz.ch/research/microarch/retbleed/ (A foaf actually
> wrote the exploit code for this). It seems there is no end to
> this. Intel and AMD are affected, and mitigation is expensive,
> 14% and 39% overhead measured. Bah.
>
> @Mitch: How expensive would not allowing speculative execution to
> update microarchitectural state be?
<
I have read the associated paper and spent a couple hours thinking about
the problem space::
<
a) My 66130 is not sensitive to this kind of attack.
.....My 666x0 might be sensitive to this kind of attack.
.....I suspect Mill is not sensitive, either.
b) the attack strategy would vanish if GuestOS used different ASID
.....than application, and the branch prediction recorded ASID or just
.....used the ASID in its HASH. My 66000 has this abstraction built in.
c) using Safe Stack (and the Mill equivalent) eliminates the problem.
.....but also makes retpolines require excess privilege, but these are
.....unnecessary; so let us assume they were not "put in".
d) in any event, My 66000 has switches and method calls that are not
.....based on indirect control transfer (LD Rk,[address], JMP Rk) and use
.....of these has range verification applied in HW; so the main avenue
.....of attack is missing.
e) since indirect control transfer (LD Rk,[address], JMP Rk) will be so
.....rare, it requires no prediction, eliminating this attack strategy.
>
> I am thinking about stores; I assume that most stores on OoO
> architectures are speculative, so a sizable buffer (a second L1
> cache, if you will) would have to be set aside. Do you have
> an estimate how big and expensive that would have to be?
<
In Mc88120 we allowed the conditional cache (i.e., memory reservation
station) to be ½ of the size of dynamic execution window (96 instructions).
We chose ½ instead of ⅓ because administration was simpler, and because
memory references tend to come in clumps, and breaking a clump harmed
the packet cache density.
<
In general, STs represent 10% of dynamic instructions, LDs 20%. So, you need
a ST buffer big enough not to stall issue when you have a clump or run through
a section of code with little arithmetic. It has to be long enough to absorb the
delay until you get to the point STs can migrate data to the cache hierarchy. In
heavy FP codes this will be at least (12-cycles + completion-latency) × issue-width.
12-cycles embraces the LD latency feeding the FP calculations and the FP calcu-
lations themselves. Completion latency is the number of cycles after ST becomes
consistent (and is allowed to modify visible architectural state) until all such state
has been so modified and the store is then ready to have its microarchitectural
state recycled to a new memory reference (or ST).

> e) since indirect control transfer (LD Rk,[address], JMP Rk) will be so
> ....rare, it requires no prediction, eliminating this attack strategy.

While some languages and/or compilation strategies may be able to
replace most indirect calls other forms of control transfers, it doesn't
sound reasonable to assume that they will necessarily be rare.

Method calls and calls to closures by default rely crucially on
indirect function calls. Various optimization techniques have been
developed to replace those with direct calls or switch tables, but they
only cover *some* cases.

Stefan

Thomas Koenig <tkoenig@netcologne.de> writes:
> https://comsec.ethz.ch/research/microarch/retbleed/ (A foaf actually
> wrote the exploit code for this). It seems there is no end to
> this. Intel and AMD are affected, and mitigation is expensive,
> 14% and 39% overhead measured. Bah.

Never mind the cost of losses to Yet Another Exploit.

What if you grid, say, RK3399's onto a board, with some flavor
of switched ethernet serving all the nodes? Storage is off-board
SAN. You share a CPU IFF the apps are all in the same security
domain.

I would cheerfully switch to this, even at a 25% bump in hosting
cost.

Andy Valencia
Home page: https://www.vsta.org/andy/
To contact me: https://www.vsta.org/contact/andy.html

On Saturday, July 16, 2022 at 9:20:56 PM UTC-5, Stefan Monnier wrote:
> > e) since indirect control transfer (LD Rk,[address], JMP Rk) will be so
> > ....rare, it requires no prediction, eliminating this attack strategy.
> While some languages and/or compilation strategies may be able to
> replace most indirect calls other forms of control transfers, it doesn't
> sound reasonable to assume that they will necessarily be rare.
>
> Method calls and calls to closures by default rely crucially on
> indirect function calls. Various optimization techniques have been
> developed to replace those with direct calls or switch tables, but they
> only cover *some* cases.
<
Tabularized calls are supported and do not need indirect calling/jumping.
Tabularized calls support Method Calling.
>
>
> Stefan

> Tabularized calls are supported and do not need indirect calling/jumping.
> Tabularized calls support Method Calling.

Many method calls look like:

(x->vtable[CST]) (x, ..args...)

while calls to closures will look like

(x->code) (x, ...args...)

both of those seem to fall squarely in the category of indirect calls.

IIUC you're saying that you think you'll be able to avoid using
prediction for those? That seems difficult without paying a fairly
heavy cost (`x` is not necessarily known yet at the time you fetch those
instructions).

Stefan

Andy Valencia wrote:
> Thomas Koenig <tkoenig@netcologne.de> writes:
>> https://comsec.ethz.ch/research/microarch/retbleed/ (A foaf actually
>> wrote the exploit code for this). It seems there is no end to
>> this. Intel and AMD are affected, and mitigation is expensive,
>> 14% and 39% overhead measured. Bah.
>
> Never mind the cost of losses to Yet Another Exploit.
>
> What if you grid, say, RK3399's onto a board, with some flavor
> of switched ethernet serving all the nodes? Storage is off-board
> SAN. You share a CPU IFF the apps are all in the same security
> domain.
>
> I would cheerfully switch to this, even at a 25% bump in hosting
> cost.
>
> Andy Valencia
> Home page: https://www.vsta.org/andy/
> To contact me: https://www.vsta.org/contact/andy.html

Beaten with a blunt object is also a viable engineering solution.

On Sunday, July 17, 2022 at 10:12:36 AM UTC-5, Stefan Monnier wrote:
> > Tabularized calls are supported and do not need indirect calling/jumping.
> > Tabularized calls support Method Calling.
> Many method calls look like:
>
> (x->vtable[CST]) (x, ..args...)
<
Why do they not look like::
<
globaltable[x->method](x, ..args... )
<
After all, the compiler+linker can account for all methods prior to the start
of execution:: can they not ??
>
> while calls to closures will look like
>
> (x->code) (x, ...args...)
<
Which languages expose closures to applications ??
>
> both of those seem to fall squarely in the category of indirect calls.
>
> IIUC you're saying that you think you'll be able to avoid using
> prediction for those? That seems difficult without paying a fairly
> heavy cost (`x` is not necessarily known yet at the time you fetch those
> instructions).
<
Prediction is based on the performance goals. A 1-wide in-order machine
is unlikely to use prediction--indeed, the ISA of My 66000 was designed
so that prediction was unnecessary on such lowly implementations. VVM,
then, enabled these lowly implementations to achieve performance results
within spitting distance of current GBOoO machines (that is 2.0 IPC long
term average).
<
However, GBOoO My 66000's will indeed have (and need) prediction.
I envision 3 kinds of predictors:: conditional branch predictor, call-return
stack predictor, and an indirect predictor. Exactly how these would be
configured is dependent on how the FETCH-DECODE part of the execution
pipeline is designed.
<
Indirect prediction in the past has not have very good accuracy. In fact,
my My 66000 simulator uses tabularized subroutine calls:: PARSE uses
instruction<31:26> to index a format table. The format subroutine, then,
extracts more bits from the instruction (dependent on which format is
active) and then calls an indirect function to deal with operands (in
DECODE) and then call the calculation indirect function (In EXECUTE).
<
static
REGISTER op2table( REGISTER S1, REGISTER S2, SIGN s )[] = {
illegalOpCode, // 0
SR, // 1
SL, // 2
BMM, // 3
ADD, // 4
MUL, // 5
DIV, // 6
CMP, // 7
MAX, // 8
MIN, // 9
OR, // 10
XOR, // 11
AND, // 12
illegalOpcode, // 13
illegalOpcode, // 14
illegalOpcode, // 15
EADD, // 16
FADD, // 17
FMUL, // 18
FDIV, // 19
FCMP, // 20
FMAX, // 21
FMIN, // 22
POW, // 23
ATAN2, // 24
illegalOpCode, // 25
illegalOpCode, // 26
illegalOpCode, // 27
illegalOpCode, // 28
illegalOpCode, // 29
illegalOpCode, // 30
illegalOpCode, // 31
};
<
Since each instruction is independent of the predecessor and successor
prediction is not going to be good with any kind of predictor !!
<
In Mc88120 we had an indirect predictor and we gave it 1 SRAM of storage;
1024 entries; replace on mispredict. We were getting 50% indirect prediction
accuracy in SPEC89. On the other hand, the design of the front end allotted
us only 4 gates of delay from arrival of a packet to the choice of next_fetch_
_address. So we had no room for any exotic prediction algorithms.
>
>
> Stefan

MitchAlsup [2022-07-17 10:55:56] wrote:
> On Sunday, July 17, 2022 at 10:12:36 AM UTC-5, Stefan Monnier wrote:
>> > Tabularized calls are supported and do not need indirect calling/jumping.
>> > Tabularized calls support Method Calling.
>> Many method calls look like:
>> (x->vtable[CST]) (x, ..args...)
> Why do they not look like::
> <
> globaltable[x->method](x, ..args... )
> <
> After all, the compiler+linker can account for all methods prior to the start
> of execution:: can they not ??

For most applications nowadays you never get to see "the whole world",
e.g. because of plugins, or dynamically linked libraries, or jit, or ...

>> while calls to closures will look like
>> (x->code) (x, ...args...)
> Which languages expose closures to applications ??

AFAIK nowadays basically all languages expose some kind of closure
construct (except for C and maybe a handful of other holdovers).

> Prediction is based on the performance goals. A 1-wide in-order machine
> is unlikely to use prediction--indeed, the ISA of My 66000 was designed
> so that prediction was unnecessary on such lowly implementations.

For the typical `(x->vtable[CST]) (x, ..args...)` method calls I suspect
that the performance will suck if you don't have a BTB-style (or
better) predictor [ Tho admittedly it depends on how much your machine
is strictly "in-order", but there's about 10 cycles of latency with
a naive execution and the BTB can remove that dependency completely,
especially since practice most of those method calls always jump to the
same destination so even a simple BTB tends to work very well. ]

> Since each instruction is independent of the predecessor and successor
> prediction is not going to be good with any kind of predictor !!

Actually the kinds of predictors used on modern amd4 processors can make
use of the branch history to provide surprisingly good predictions in
these kinds of situations (basically running an interpreter). They end
up being able to take advantage of patterns in the interpreted code
(where you do get usual control flow behaviors like loops etc...).

Stefan

MitchAlsup [2022-07-17 10:55:56] wrote:
> On Sunday, July 17, 2022 at 10:12:36 AM UTC-5, Stefan Monnier wrote:
>> > Tabularized calls are supported and do not need indirect calling/jumping.
>> > Tabularized calls support Method Calling.
>> Many method calls look like:
>> (x->vtable[CST]) (x, ..args...)
> Why do they not look like::
> <
> globaltable[x->method](x, ..args... )
> <
> After all, the compiler+linker can account for all methods prior to the start
> of execution:: can they not ??

For most applications nowadays you never get to see "the whole world",
e.g. because of plugins, or dynamically linked libraries, or jit, or ...

>> while calls to closures will look like
>> (x->code) (x, ...args...)
> Which languages expose closures to applications ??

AFAIK nowadays basically all languages expose some kind of closure
construct (except for C and maybe a handful of other holdovers).

> Prediction is based on the performance goals. A 1-wide in-order machine
> is unlikely to use prediction--indeed, the ISA of My 66000 was designed
> so that prediction was unnecessary on such lowly implementations.

For the typical `(x->vtable[CST]) (x, ..args...)` method calls I suspect
that the performance will suck if you don't have a BTB-style (or
better) predictor [ Tho admittedly it depends on how much your machine
is strictly "in-order", but there's about 10 cycles of latency with
a naive execution and the BTB can remove that dependency completely,
especially since practice most of those method calls always jump to the
same destination so even a simple BTB tends to work very well. ]

> Since each instruction is independent of the predecessor and successor
> prediction is not going to be good with any kind of predictor !!

Actually the kinds of predictors used on modern amd4 processors can make
use of the branch history to provide surprisingly good predictions in
these kinds of situations (basically running an interpreter). They end
up being able to take advantage of patterns in the interpreted code
(where you do get usual control flow behaviors like loops etc...).

Stefan

On Sunday, July 17, 2022 at 1:15:56 PM UTC-5, Stefan Monnier wrote:
> MitchAlsup [2022-07-17 10:55:56] wrote:
> > On Sunday, July 17, 2022 at 10:12:36 AM UTC-5, Stefan Monnier wrote:
> >> > Tabularized calls are supported and do not need indirect calling/jumping.
> >> > Tabularized calls support Method Calling.
> >> Many method calls look like:
> >> (x->vtable[CST]) (x, ..args...)
> > Why do they not look like::
> > <
> > globaltable[x->method](x, ..args... )
> > <
> > After all, the compiler+linker can account for all methods prior to the start
> > of execution:: can they not ??
> For most applications nowadays you never get to see "the whole world",
> e.g. because of plugins, or dynamically linked libraries, or jit, or ...
> >> while calls to closures will look like
> >> (x->code) (x, ...args...)
> > Which languages expose closures to applications ??
> AFAIK nowadays basically all languages expose some kind of closure
> construct (except for C and maybe a handful of other holdovers).
> > Prediction is based on the performance goals. A 1-wide in-order machine
> > is unlikely to use prediction--indeed, the ISA of My 66000 was designed
> > so that prediction was unnecessary on such lowly implementations.
> For the typical `(x->vtable[CST]) (x, ..args...)` method calls I suspect
> that the performance will suck if you don't have a BTB-style (or
> better) predictor [ Tho admittedly it depends on how much your machine
> is strictly "in-order", but there's about 10 cycles of latency with
> a naive execution and the BTB can remove that dependency completely,
> especially since practice most of those method calls always jump to the
> same destination so even a simple BTB tends to work very well. ]
<
I agree that GBOoO machine will use prediction on these.
<
> > Since each instruction is independent of the predecessor and successor
> > prediction is not going to be good with any kind of predictor !!
> Actually the kinds of predictors used on modern amd4 processors can make
> use of the branch history to provide surprisingly good predictions in
> these kinds of situations (basically running an interpreter). They end
> up being able to take advantage of patterns in the interpreted code
> (where you do get usual control flow behaviors like loops etc...).
>
>
> Stefan

On Sunday, July 17, 2022 at 1:15:56 PM UTC-5, Stefan Monnier wrote:
> MitchAlsup [2022-07-17 10:55:56] wrote:
> > On Sunday, July 17, 2022 at 10:12:36 AM UTC-5, Stefan Monnier wrote:
> >> > Tabularized calls are supported and do not need indirect calling/jumping.
> >> > Tabularized calls support Method Calling.
> >> Many method calls look like:
> >> (x->vtable[CST]) (x, ..args...)
> > Why do they not look like::
> > <
> > globaltable[x->method](x, ..args... )
> > <
> > After all, the compiler+linker can account for all methods prior to the start
> > of execution:: can they not ??
> For most applications nowadays you never get to see "the whole world",
> e.g. because of plugins, or dynamically linked libraries, or jit, or ...
> >> while calls to closures will look like
> >> (x->code) (x, ...args...)
> > Which languages expose closures to applications ??
> AFAIK nowadays basically all languages expose some kind of closure
> construct (except for C and maybe a handful of other holdovers).
> > Prediction is based on the performance goals. A 1-wide in-order machine
> > is unlikely to use prediction--indeed, the ISA of My 66000 was designed
> > so that prediction was unnecessary on such lowly implementations.
> For the typical `(x->vtable[CST]) (x, ..args...)` method calls I suspect
> that the performance will suck if you don't have a BTB-style (or
> better) predictor [ Tho admittedly it depends on how much your machine
> is strictly "in-order", but there's about 10 cycles of latency with
> a naive execution and the BTB can remove that dependency completely,
> especially since practice most of those method calls always jump to the
> same destination so even a simple BTB tends to work very well. ]
> > Since each instruction is independent of the predecessor and successor
> > prediction is not going to be good with any kind of predictor !!
> Actually the kinds of predictors used on modern amd4 processors can make
> use of the branch history to provide surprisingly good predictions in
> these kinds of situations (basically running an interpreter). They end
> up being able to take advantage of patterns in the interpreted code
> (where you do get usual control flow behaviors like loops etc...).
<
Does anyone have a pointer to a paper where they look at <typical>
branch prediction accuracies when ½ of the branches have been
converted into predication ?
>
>
> Stefan

On 7/17/2022 10:55 AM, MitchAlsup wrote:
> On Sunday, July 17, 2022 at 10:12:36 AM UTC-5, Stefan Monnier wrote:
>>> Tabularized calls are supported and do not need indirect calling/jumping.
>>> Tabularized calls support Method Calling.
>> Many method calls look like:
>>
>> (x->vtable[CST]) (x, ..args...)
> <
> Why do they not look like::
> <
> globaltable[x->method](x, ..args... )
> <
> After all, the compiler+linker can account for all methods prior to the start
> of execution:: can they not ??

No: ld.so at runtime.

>>
>> while calls to closures will look like
>>
>> (x->code) (x, ...args...)
> <
> Which languages expose closures to applications ??

Many, although they might not call them closures. Start with C++.

>>
>> both of those seem to fall squarely in the category of indirect calls.
>>
>> IIUC you're saying that you think you'll be able to avoid using
>> prediction for those? That seems difficult without paying a fairly
>> heavy cost (`x` is not necessarily known yet at the time you fetch those
>> instructions).
> <
> Prediction is based on the performance goals. A 1-wide in-order machine
> is unlikely to use prediction--indeed, the ISA of My 66000 was designed
> so that prediction was unnecessary on such lowly implementations. VVM,
> then, enabled these lowly implementations to achieve performance results
> within spitting distance of current GBOoO machines (that is 2.0 IPC long
> term average).
> <
> However, GBOoO My 66000's will indeed have (and need) prediction.
> I envision 3 kinds of predictors:: conditional branch predictor, call-return
> stack predictor, and an indirect predictor. Exactly how these would be
> configured is dependent on how the FETCH-DECODE part of the execution
> pipeline is designed.
> <
> Indirect prediction in the past has not have very good accuracy. In fact,
> my My 66000 simulator uses tabularized subroutine calls:: PARSE uses
> instruction<31:26> to index a format table. The format subroutine, then,
> extracts more bits from the instruction (dependent on which format is
> active) and then calls an indirect function to deal with operands (in
> DECODE) and then call the calculation indirect function (In EXECUTE).
> <
> static
> REGISTER op2table( REGISTER S1, REGISTER S2, SIGN s )[] = {
> illegalOpCode, // 0
> SR, // 1
> SL, // 2
> BMM, // 3
> ADD, // 4
> MUL, // 5
> DIV, // 6
> CMP, // 7
> MAX, // 8
> MIN, // 9
> OR, // 10
> XOR, // 11
> AND, // 12
> illegalOpcode, // 13
> illegalOpcode, // 14
> illegalOpcode, // 15
> EADD, // 16
> FADD, // 17
> FMUL, // 18
> FDIV, // 19
> FCMP, // 20
> FMAX, // 21
> FMIN, // 22
> POW, // 23
> ATAN2, // 24
> illegalOpCode, // 25
> illegalOpCode, // 26
> illegalOpCode, // 27
> illegalOpCode, // 28
> illegalOpCode, // 29
> illegalOpCode, // 30
> illegalOpCode, // 31
> };
> <
> Since each instruction is independent of the predecessor and successor
> prediction is not going to be good with any kind of predictor !!
> <
> In Mc88120 we had an indirect predictor and we gave it 1 SRAM of storage;
> 1024 entries; replace on mispredict. We were getting 50% indirect prediction
> accuracy in SPEC89. On the other hand, the design of the front end allotted
> us only 4 gates of delay from arrival of a packet to the choice of next_fetch_
> _address. So we had no room for any exotic prediction algorithms.

That's why Mill uses run-ahead prediction, that and because it permits
arbitrary fetch-ahead without needing the branch in memory.

My66 is tuned for code with small working sets, so most code will be hat
in the I$1 so a limited lookahead is enough to keep the predictor up
with the fetcher, so you only need branch prediction; indirect
prediction is a matter of tidying up.

Mill is tuned for code with working sets somewhat or much larger than
I$1 and frequently than I$2; that's why we use exit prediction. By
chaining through exits we can prefetch all the way to RAM. The drawback
is that the added state limits the number of entries for a give budget.
That prevents us from doing much history matching; there isn't much room
for multiple histories for each ebb. There's more, but it's NYF.

>>
>>
>> Stefan

On 7/17/2022 2:13 PM, MitchAlsup wrote:
> On Sunday, July 17, 2022 at 1:15:56 PM UTC-5, Stefan Monnier wrote:
>> MitchAlsup [2022-07-17 10:55:56] wrote:
>>> On Sunday, July 17, 2022 at 10:12:36 AM UTC-5, Stefan Monnier wrote:
>>>>> Tabularized calls are supported and do not need indirect calling/jumping.
>>>>> Tabularized calls support Method Calling.
>>>> Many method calls look like:
>>>> (x->vtable[CST]) (x, ..args...)
>>> Why do they not look like::
>>> <
>>> globaltable[x->method](x, ..args... )
>>> <
>>> After all, the compiler+linker can account for all methods prior to the start
>>> of execution:: can they not ??
>> For most applications nowadays you never get to see "the whole world",
>> e.g. because of plugins, or dynamically linked libraries, or jit, or ...
>>>> while calls to closures will look like
>>>> (x->code) (x, ...args...)
>>> Which languages expose closures to applications ??
>> AFAIK nowadays basically all languages expose some kind of closure
>> construct (except for C and maybe a handful of other holdovers).
>>> Prediction is based on the performance goals. A 1-wide in-order machine
>>> is unlikely to use prediction--indeed, the ISA of My 66000 was designed
>>> so that prediction was unnecessary on such lowly implementations.
>> For the typical `(x->vtable[CST]) (x, ..args...)` method calls I suspect
>> that the performance will suck if you don't have a BTB-style (or
>> better) predictor [ Tho admittedly it depends on how much your machine
>> is strictly "in-order", but there's about 10 cycles of latency with
>> a naive execution and the BTB can remove that dependency completely,
>> especially since practice most of those method calls always jump to the
>> same destination so even a simple BTB tends to work very well. ]
>>> Since each instruction is independent of the predecessor and successor
>>> prediction is not going to be good with any kind of predictor !!
>> Actually the kinds of predictors used on modern amd4 processors can make
>> use of the branch history to provide surprisingly good predictions in
>> these kinds of situations (basically running an interpreter). They end
>> up being able to take advantage of patterns in the interpreted code
>> (where you do get usual control flow behaviors like loops etc...).
> <
> Does anyone have a pointer to a paper where they look at <typical>
> branch prediction accuracies when ½ of the branches have been
> converted into predication ?

No paper, but some experience: predication doesn't seem to impact
accuracy much if the predictor is bigger than the code's working set.
That is, far branches (too far to use predication) seem to be about as
predictable as close ones. However, predication reduces the number of
branch instructions to be executed, i.e. it reduces the working set of
the code. That can drop the working set into the size of the predictor,
and the predictor performance dramatically improves as the code stops
thrashing in the predictor.

That's only for the middle range of working sets of course; small sets
fit in the predictor with or without predication, and large sets don't
fit either way, and thrash.

MitchAlsup wrote:
> <
> Does anyone have a pointer to a paper where they look at <typical>
> branch prediction accuracies when ½ of the branches have been
> converted into predication ?

I'm not sure about 1/2 but there are a bunch of papers from 1994 to
2007 on interactions between branch prediction and predication.
I found these by taking the title I have for the first one on
Guarded Execution, plopping it into Google Scholar,
and following the citations.
They have titles and/or abstracts that look relevant but
I haven't read them and have no idea if they actually are relevant.

Guarded execution and branch prediction in dynamic ILP processors, 1994
https://research.cs.wisc.edu/techreports/1993/TR1193.pdf

Characterizing the impact of predicated execution on
branch prediction, 1994
https://web.eecs.umich.edu/~mahlke/papers/1994/mahlke_micro94.pdf

The Effects of Predicated Execution on Branch Prediction, 1994
http://www.princeton.edu/~rblee/ELE572Papers/the-effects-of-predicated.pdf

Evaluating the Effects of Predicated Execution on Branch Prediction, 2006
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.75.6629&rep=rep1&type=pdf

The impact of if-conversion and branch prediction on program execution
on the intel itanium processor, 2001
http://courses.cs.washington.edu/courses/cse590g/02wi/choi_y.pdf

Predicate Prediction for Efficient Out-of-order Execution, 2003
https://cseweb.ucsd.edu/~calder/papers/ICS-03-PP.pdf

Improving Branch Prediction and Predicated Execution
in Out-of-Order Processors, 2007
http://people.site.ac.upc.edu/~equinone/docs/2006-08/hpca_2007.pdf

On 7/17/2022 7:33 PM, EricP wrote:
> MitchAlsup wrote:
>> <
>> Does anyone have a pointer to a paper where they look at <typical>
>> branch prediction accuracies when ½ of the branches have been
>> converted into predication ?
>
> I'm not sure about 1/2 but there are a bunch of papers from 1994 to
> 2007 on interactions between branch prediction and predication.
> I found these by taking the title I have for the first one on
> Guarded Execution, plopping it into Google Scholar,
> and following the citations.
> They have titles and/or abstracts that look relevant but
> I haven't read them and have no idea if they actually are relevant.
>
> Guarded execution and branch prediction in dynamic ILP processors, 1994
> https://research.cs.wisc.edu/techreports/1993/TR1193.pdf

This presents the same guarding instruction approach that Mitch uses. So
much for that patent :-(

> Characterizing the impact of predicated execution on
> branch prediction, 1994
> https://web.eecs.umich.edu/~mahlke/papers/1994/mahlke_micro94.pdf
>
> The Effects of Predicated Execution on Branch Prediction, 1994
> http://www.princeton.edu/~rblee/ELE572Papers/the-effects-of-predicated.pdf
>
> Evaluating the Effects of Predicated Execution on Branch Prediction, 2006
> https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.75.6629&rep=rep1&type=pdf
>
>
> The impact of if-conversion and branch prediction on program execution
> on the intel itanium processor, 2001
> http://courses.cs.washington.edu/courses/cse590g/02wi/choi_y.pdf
>
> Predicate Prediction for Efficient Out-of-order Execution, 2003
> https://cseweb.ucsd.edu/~calder/papers/ICS-03-PP.pdf
>
> Improving Branch Prediction and Predicated Execution
> in Out-of-Order Processors, 2007
> http://people.site.ac.upc.edu/~equinone/docs/2006-08/hpca_2007.pdf
>
>
>
>
>

Thomas Koenig <tkoenig@netcologne.de> writes:
>https://comsec.ethz.ch/research/microarch/retbleed/ (A foaf actually
>wrote the exploit code for this). It seems there is no end to
>this. Intel and AMD are affected, and mitigation is expensive,
>14% and 39% overhead measured. Bah.
>
>@Mitch: How expensive would not allowing speculative execution to
>update microarchitectural state be?
>
>I am thinking about stores; I assume that most stores on OoO
>architectures are speculative, so a sizable buffer (a second L1
>cache, if you will) would have to be set aside.

Store buffers are set aside already, because a store must only become
permanent on commit.

Spectre v1 and v2 work use loads for the side channel because CPUs
with speculative execution and without Spectre fix make permanent
changes to the caches when a speculative load happens. A fix would
keep the loads in load buffers und only put them in the caches on
commit. According to Mitch Alsup, CPUs already have such load
buffers. My guess is that you may want to make them somewhat bigger;
if you want to support, say, speculative loads from 32 different cache
lines that do not reside in the D-cache already, you need 32 cache
lines (2KB with 64-byte cache lines).

There are also other microarchitectural states that have been used as
a side channel (e.g., the power state of SIMD units), but all others
need much less speculative state (or, if you delay the change until it
is no longer speculative, have a much smaller performance impact) then
loads.

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

Anton Ertl wrote:
> Thomas Koenig <tkoenig@netcologne.de> writes:
>> https://comsec.ethz.ch/research/microarch/retbleed/ (A foaf actually
>> wrote the exploit code for this). It seems there is no end to
>> this. Intel and AMD are affected, and mitigation is expensive,
>> 14% and 39% overhead measured. Bah.
>>
>> @Mitch: How expensive would not allowing speculative execution to
>> update microarchitectural state be?
>>
>> I am thinking about stores; I assume that most stores on OoO
>> architectures are speculative, so a sizable buffer (a second L1
>> cache, if you will) would have to be set aside.
>
> Store buffers are set aside already, because a store must only become
> permanent on commit.
>
> Spectre v1 and v2 work use loads for the side channel because CPUs
> with speculative execution and without Spectre fix make permanent
> changes to the caches when a speculative load happens. A fix would
> keep the loads in load buffers und only put them in the caches on
> commit. According to Mitch Alsup, CPUs already have such load
> buffers. My guess is that you may want to make them somewhat bigger;
> if you want to support, say, speculative loads from 32 different cache
> lines that do not reside in the D-cache already, you need 32 cache
> lines (2KB with 64-byte cache lines).

As we have discussed here previously, that might be vulnerable too.
Reading a line shared for a speculated LD cache miss could cause
a remote node to downgrade it from an exclusive or modified state,
and that line state change would be detectable at the remote node.
Holding the line in a local miss buffer wouldn't help because the
remote node's cache has already changed state.

Changing this coherence behaviour would require adding a NAK to the
protocol to read the line shared if no node has it exclusive or modified,
which no one would want to do as it adds states to the protocol.

It can do local store-load forwarding because that all gets tossed
on mispredict.

One might be able to build a dependency matrix that tracked
LD and ST vs prior branch resolutions. When all older branches
have resolved then release the loads to cause real cache misses,
and allow the stores to prefetch. But this too might be vulnerable
to using exceptions like bounds check instead of branches,
so it might have to watch pending potential exceptions too.

> There are also other microarchitectural states that have been used as
> a side channel (e.g., the power state of SIMD units), but all others
> need much less speculative state (or, if you delay the change until it
> is no longer speculative, have a much smaller performance impact) then
> loads.
>
> - anton

On Monday, July 18, 2022 at 8:32:18 AM UTC-5, EricP wrote:
> Anton Ertl wrote:
> > Thomas Koenig <tko...@netcologne.de> writes:
> >> https://comsec.ethz.ch/research/microarch/retbleed/ (A foaf actually
> >> wrote the exploit code for this). It seems there is no end to
> >> this. Intel and AMD are affected, and mitigation is expensive,
> >> 14% and 39% overhead measured. Bah.
> >>
> >> @Mitch: How expensive would not allowing speculative execution to
> >> update microarchitectural state be?
> >>
> >> I am thinking about stores; I assume that most stores on OoO
> >> architectures are speculative, so a sizable buffer (a second L1
> >> cache, if you will) would have to be set aside.
> >
> > Store buffers are set aside already, because a store must only become
> > permanent on commit.
> >
> > Spectre v1 and v2 work use loads for the side channel because CPUs
> > with speculative execution and without Spectre fix make permanent
> > changes to the caches when a speculative load happens. A fix would
> > keep the loads in load buffers und only put them in the caches on
> > commit. According to Mitch Alsup, CPUs already have such load
> > buffers. My guess is that you may want to make them somewhat bigger;
> > if you want to support, say, speculative loads from 32 different cache
> > lines that do not reside in the D-cache already, you need 32 cache
> > lines (2KB with 64-byte cache lines).
<
> As we have discussed here previously, that might be vulnerable too.
> Reading a line shared for a speculated LD cache miss could cause
> a remote node to downgrade it from an exclusive or modified state,
> and that line state change would be detectable at the remote node.
> Holding the line in a local miss buffer wouldn't help because the
> remote node's cache has already changed state.
<
yes, setting 3rd party Spectré attack strategies.
>
> Changing this coherence behaviour would require adding a NAK to the
> protocol to read the line shared if no node has it exclusive or modified,
> which no one would want to do as it adds states to the protocol.
<
My 66000 already has NaK in the protocol; currently only being used
for ATOMIC stuff.
<
The alternative is to have the ability to send the line back to its previous
owner if the line cannot be installed in Cache due to non-comit of
memory reference.
>
> It can do local store-load forwarding because that all gets tossed
> on mispredict.
>
> One might be able to build a dependency matrix that tracked
> LD and ST vs prior branch resolutions. When all older branches
> have resolved then release the loads to cause real cache misses,
<
Tidies up branches, does nothing for exceptions.
<
> and allow the stores to prefetch. But this too might be vulnerable
> to using exceptions like bounds check instead of branches,
> so it might have to watch pending potential exceptions too.
<
I don't see that you have gained anything (due to exceptions remaining
present.)
<
> > There are also other microarchitectural states that have been used as
> > a side channel (e.g., the power state of SIMD units), but all others
> > need much less speculative state (or, if you delay the change until it
> > is no longer speculative, have a much smaller performance impact) then
> > loads.
> >
> > - anton

Ivan Godard <ivan@millcomputing.com> schrieb:
> On 7/17/2022 7:33 PM, EricP wrote:

>> Guarded execution and branch prediction in dynamic ILP processors, 1994
>> https://research.cs.wisc.edu/techreports/1993/TR1193.pdf
>
> This presents the same guarding instruction approach that Mitch uses. So
> much for that patent :-(

Is that indeed a patent?

Mitch's name is rare enough that it is rather easy to search for
in the patent databases (unlike mine, which is relatively common),
and the only one I found post-Samsung was US20180357043, the
Transcendental calculation unit apparatus and method.

On Monday, July 18, 2022 at 1:02:11 PM UTC-5, Thomas Koenig wrote:
> Ivan Godard <iv...@millcomputing.com> schrieb:
> > On 7/17/2022 7:33 PM, EricP wrote:
>
> >> Guarded execution and branch prediction in dynamic ILP processors, 1994
> >> https://research.cs.wisc.edu/techreports/1993/TR1193.pdf
> >
> > This presents the same guarding instruction approach that Mitch uses. So
> > much for that patent :-(
> Is that indeed a patent?
>
> Mitch's name is rare enough that it is rather easy to search for
> in the patent databases (unlike mine, which is relatively common),
> and the only one I found post-Samsung was US20180357043, the
> Transcendental calculation unit apparatus and method.
<
You will find my name on 52 patents at USPTO.

MitchAlsup <MitchAlsup@aol.com> schrieb:
> On Monday, July 18, 2022 at 1:02:11 PM UTC-5, Thomas Koenig wrote:
>> Ivan Godard <iv...@millcomputing.com> schrieb:
>> > On 7/17/2022 7:33 PM, EricP wrote:
>>
>> >> Guarded execution and branch prediction in dynamic ILP processors, 1994
>> >> https://research.cs.wisc.edu/techreports/1993/TR1193.pdf
>> >
>> > This presents the same guarding instruction approach that Mitch uses. So
>> > much for that patent :-(
>> Is that indeed a patent?
>>
>> Mitch's name is rare enough that it is rather easy to search for
>> in the patent databases (unlike mine, which is relatively common),
>> and the only one I found post-Samsung was US20180357043, the
>> Transcendental calculation unit apparatus and method.
><
> You will find my name on 52 patents at USPTO.

That's quite a number (but apparently I didn't find them all,
I only used Google patents, which is somewhat iffy). I didn't
use the patent database I use at work, for obvious reasons.

MitchAlsup wrote:
> On Monday, July 18, 2022 at 8:32:18 AM UTC-5, EricP wrote:
>> Anton Ertl wrote:
>>> Thomas Koenig <tko...@netcologne.de> writes:
>>>> https://comsec.ethz.ch/research/microarch/retbleed/ (A foaf actually
>>>> wrote the exploit code for this). It seems there is no end to
>>>> this. Intel and AMD are affected, and mitigation is expensive,
>>>> 14% and 39% overhead measured. Bah.
>>>>
>>>> @Mitch: How expensive would not allowing speculative execution to
>>>> update microarchitectural state be?
>>>>
>>>> I am thinking about stores; I assume that most stores on OoO
>>>> architectures are speculative, so a sizable buffer (a second L1
>>>> cache, if you will) would have to be set aside.
>>> Store buffers are set aside already, because a store must only become
>>> permanent on commit.
>>>
>>> Spectre v1 and v2 work use loads for the side channel because CPUs
>>> with speculative execution and without Spectre fix make permanent
>>> changes to the caches when a speculative load happens. A fix would
>>> keep the loads in load buffers und only put them in the caches on
>>> commit. According to Mitch Alsup, CPUs already have such load
>>> buffers. My guess is that you may want to make them somewhat bigger;
>>> if you want to support, say, speculative loads from 32 different cache
>>> lines that do not reside in the D-cache already, you need 32 cache
>>> lines (2KB with 64-byte cache lines).
> <
>> As we have discussed here previously, that might be vulnerable too.
>> Reading a line shared for a speculated LD cache miss could cause
>> a remote node to downgrade it from an exclusive or modified state,
>> and that line state change would be detectable at the remote node.
>> Holding the line in a local miss buffer wouldn't help because the
>> remote node's cache has already changed state.
> <
> yes, setting 3rd party Spectré attack strategies.
>> Changing this coherence behaviour would require adding a NAK to the
>> protocol to read the line shared if no node has it exclusive or modified,
>> which no one would want to do as it adds states to the protocol.
> <
> My 66000 already has NaK in the protocol; currently only being used
> for ATOMIC stuff.
> <
> The alternative is to have the ability to send the line back to its previous
> owner if the line cannot be installed in Cache due to non-comit of
> memory reference.

Hmmm... a cache line 'Rebound'?
My guess is that would probably go over even less popular than NAK.

AIUI the problem with NAK is not just the extra protocol states
which causes possible interactions to grow exponentially.
It was also that resources would be allocated for a miss,
cache victims chosen and evicted, possibly move store data from
LSQ into the pending cache miss buffer to free the LSQ entry.
Then the cache gets back a NAK and... does what?

So it can't move the store data to the miss buffer early,
and it either lives with the empty slot or puts back the victim,
then wakes up the waiting LSQ entries which immediately
trigger the miss sequence again.

A rebound would be like a NAK but with longer latency,
and with the possibility of other interviening cache changes,
that all have to be backed out of. Yeech.

>> It can do local store-load forwarding because that all gets tossed
>> on mispredict.
>>
>> One might be able to build a dependency matrix that tracked
>> LD and ST vs prior branch resolutions. When all older branches
>> have resolved then release the loads to cause real cache misses,
> <
> Tidies up branches, does nothing for exceptions.
> <
>> and allow the stores to prefetch. But this too might be vulnerable
>> to using exceptions like bounds check instead of branches,
>> so it might have to watch pending potential exceptions too.
> <
> I don't see that you have gained anything (due to exceptions remaining
> present.)

Just spitballing...
I'll call the state of a uOp after execution Finished.
When branch instructions are finished they have resolved and,
if a mispredict, already purged mispredicted younger uOps.

All instructions except LD and ST are unaffected by the finished
status of older uOps so they do not need to take them into account
for their scheduling.

LD and ST can translate addresses in the TLB in any order as soon
as the address is ready. However because a table walk would cause
cache state and TLB changes we must synchronize how these proceed.
LD and ST table walks must wait until all older uOps are finished
and exception free before proceeding one at a time.

Note however this serializes all TLB miss table walks as we don't
know if the current walk will ultimately page fault so we can't
begin the next as it might change cache too early. So there is only
one table walker (but that was probably going to happen anyway).

After translate LD can proceed if it can receive a store-load forward,
or if it cache hits. Otherwise LD must wait until older uOps are finished
and exception free (if LD got a TLB hit it would have skipped this check
earlier so must do it now).
Note that memory disambiguation will group LD's to the same cache line
together and process the groups concurrently, So LD's to different lines
can hit the cache while others stall.

ST must wait to reach the Commit/Retire stage but can issue cache
prefetches as soon as older uOps are finished and exception free.

So it looks like there is still some concurrency and prefetching
opportunities to be had even while respecting Spectre cache rules.

On Monday, July 18, 2022 at 4:33:10 PM UTC-5, EricP wrote:
> MitchAlsup wrote:
<snip>
> > yes, setting 3rd party Spectré attack strategies.
> >> Changing this coherence behaviour would require adding a NAK to the
> >> protocol to read the line shared if no node has it exclusive or modified,
> >> which no one would want to do as it adds states to the protocol.
> > <
> > My 66000 already has NaK in the protocol; currently only being used
> > for ATOMIC stuff.
> > <
> > The alternative is to have the ability to send the line back to its previous
> > owner if the line cannot be installed in Cache due to non-comit of
> > memory reference.
<
> Hmmm... a cache line 'Rebound'?
> My guess is that would probably go over even less popular than NAK.
>
> AIUI the problem with NAK is not just the extra protocol states
> which causes possible interactions to grow exponentially.
> It was also that resources would be allocated for a miss,
> cache victims chosen and evicted, possibly move store data from
> LSQ into the pending cache miss buffer to free the LSQ entry.
> Then the cache gets back a NAK and... does what?
<
NAK in the protocol pushes the architect in the direction of exclusive
caches. Thus, you do not select and evict on miss, you select and
evict on data arrival. Remember, Spectrè is going to prevent you
from modifying your cache until the instruction performing the
modification can retire. So, you already LOST the ability to select
and evict up front, you just have not seen a Spectrè attack using
that. It is gone, none-the-less.
<
When the protocol is well sorted, a NAK arriving back at original
requestor cause the request to be restarted {unless the request
was participating in an ATOMIC event in which case, the ATOMIC
event fails instead}.
<
At the point of replay, that cache is in the same sate as it was when
the request went out the first time.
>
> So it can't move the store data to the miss buffer early,
> and it either lives with the empty slot or puts back the victim,
> then wakes up the waiting LSQ entries which immediately
> trigger the miss sequence again.
>
> A rebound would be like a NAK but with longer latency,
> and with the possibility of other interviening cache changes,
> that all have to be backed out of. Yeech.
<
Rebound is not data-present is is a command message only. The
downgraded line remains
<
> >> It can do local store-load forwarding because that all gets tossed
> >> on mispredict.
> >>
> >> One might be able to build a dependency matrix that tracked
> >> LD and ST vs prior branch resolutions. When all older branches
> >> have resolved then release the loads to cause real cache misses,
> > <
> > Tidies up branches, does nothing for exceptions.
> > <
> >> and allow the stores to prefetch. But this too might be vulnerable
> >> to using exceptions like bounds check instead of branches,
> >> so it might have to watch pending potential exceptions too.
> > <
> > I don't see that you have gained anything (due to exceptions remaining
> > present.)
> Just spitballing...
> I'll call the state of a uOp after execution Finished.
We used Complete.
> When branch instructions are finished they have resolved and,
> if a mispredict, already purged mispredicted younger uOps.
You also have to do similarly when an exception is recognized.
>
> All instructions except LD and ST are unaffected by the finished
> status of older uOps so they do not need to take them into account
> for their scheduling.
<
Memory references are dependent on their operand ordering and on
their memory ordering. {Not sure if there is any disagreement here,
just clarifying. We are also assuming result ordering was renamed
away.}
>
> LD and ST can translate addresses in the TLB in any order as soon
> as the address is ready. However because a table walk would cause
> cache state and TLB changes we must synchronize how these proceed.
> LD and ST table walks must wait until all older uOps are finished
> and exception free before proceeding one at a time.
<
We never found a need to do this. Mc 88120 started table walks as
TLB misses occurred. What Spectrè brings in is that you cannot
update TLB until the TLB-missing instruction becomes consistent.
{Consistent is when all older instructions are complete and exception
free.} An expendable buffer associated with TLB allows for these
walked translations to service other memory references without
being "in" the TLB. They migrate to TLB after the cause becomes
consistent.
>
> Note however this serializes all TLB miss table walks as we don't
> know if the current walk will ultimately page fault so we can't
> begin the next as it might change cache too early. So there is only
> one table walker (but that was probably going to happen anyway).
<
Mc 88120 measured this and did not find it to be a troublesome
problem in practice. We built and measured a table walker that
could service several TLB misses simultaneously (about 4) and
found no particular advantage compared to 1. But machines are
extracting more ILP now, so it would be best to rerun this experiment.
>
> After translate LD can proceed if it can receive a store-load forward,
> or if it cache hits. Otherwise LD must wait until older uOps are finished
> and exception free (if LD got a TLB hit it would have skipped this check
> earlier so must do it now).
<
You have this all lined up as if there was no buffering that relaxes the
problem enough to warrant their inclusion. I am not applying these
restrictions ...
<
> Note that memory disambiguation will group LD's to the same cache line
> together and process the groups concurrently, So LD's to different lines
> can hit the cache while others stall.
<
As I taught Luke a couple of years ago, disambiguation is more about
filtering out the "can't be the same as" lines from the "absolutely is
the same as". The former can be done with lower order untranslated
address bits, while the later requires physical address bits. In practice
the former is a lot easier to implement and looses virtually nothing.
>
> ST must wait to reach the Commit/Retire stage but can issue cache
> prefetches as soon as older uOps are finished and exception free.
<
Earlier with buffering.
>
> So it looks like there is still some concurrency and prefetching
> opportunities to be had even while respecting Spectre cache rules.
<
I agree with that sentiment.

EricP <ThatWouldBeTelling@thevillage.com> writes:
>Anton Ertl wrote:
>> Thomas Koenig <tkoenig@netcologne.de> writes:
>>> https://comsec.ethz.ch/research/microarch/retbleed/ (A foaf actually
>>> wrote the exploit code for this). It seems there is no end to
>>> this. Intel and AMD are affected, and mitigation is expensive,
>>> 14% and 39% overhead measured. Bah.
>>>
>>> @Mitch: How expensive would not allowing speculative execution to
>>> update microarchitectural state be?
>>>
>>> I am thinking about stores; I assume that most stores on OoO
>>> architectures are speculative, so a sizable buffer (a second L1
>>> cache, if you will) would have to be set aside.
>>
>> Store buffers are set aside already, because a store must only become
>> permanent on commit.
>>
>> Spectre v1 and v2 work use loads for the side channel because CPUs
>> with speculative execution and without Spectre fix make permanent
>> changes to the caches when a speculative load happens. A fix would
>> keep the loads in load buffers und only put them in the caches on
>> commit. According to Mitch Alsup, CPUs already have such load
>> buffers. My guess is that you may want to make them somewhat bigger;
>> if you want to support, say, speculative loads from 32 different cache
>> lines that do not reside in the D-cache already, you need 32 cache
>> lines (2KB with 64-byte cache lines).
>
>As we have discussed here previously, that might be vulnerable too.
>Reading a line shared for a speculated LD cache miss could cause
>a remote node to downgrade it from an exclusive or modified state,
>and that line state change would be detectable at the remote node.

You cannot do that, as you discussed with Mitch Alsup. There are also
other issues, like the bandwidth side channel. But the question was
about the needed buffer size, and these other issues have little to
do with that.

>Holding the line in a local miss buffer wouldn't help because the
>remote node's cache has already changed state.

You don't do that with speculative accesses. If the speculative
access can be handled without change to permanent microarchitectural
state, it can go ahead, otherwise it has to wait until it is no longer
speculative. Given that most accesses don't require such a change,
and that accesses to remote caches usually take more cycles than
waiting for the commit, I expect that the slowdown from this waiting
will be small.

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