<div dir="auto"><div><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, May 24, 2021, 18:44 Benjamin Herrenschmidt &lt;<a href="mailto:benh@kernel.crashing.org">benh@kernel.crashing.org</a>&gt; wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Mon, 2021-05-24 at 16:30 +0100, Luke Kenneth Casson Leighton wrote:<br>
&gt; refs:<br>
&gt; <br>
&gt; * <a href="https://en.wikipedia.org/wiki/Load-link/store-conditional" rel="noreferrer noreferrer" target="_blank">https://en.wikipedia.org/wiki/Load-link/store-conditional</a><br>
&gt; * v3.0B section 4.6.2 p868<br>
&gt; * <br>
&gt; <a href="https://github.com/riscv/riscv-isa-manual/blob/master/src/a.tex#L320" rel="noreferrer noreferrer" target="_blank">https://github.com/riscv/riscv-isa-manual/blob/master/src/a.tex#L320</a><br>
&gt; <br>
&gt; paul, hi,<br>
&gt; <br>
&gt; the discussion on wednesday covered a lot of ground, i didn&#39;t manage<br>
&gt; to successfully communicate my point about LR AX.  i thought it best<br>
&gt; to follow up because after reviewing lwarx etc the specification<br>
&gt; ambiguity i expected might be there looks like it is.<br>
&gt; <br>
&gt; what appears to be missing is how many instructions are permitted<br>
&gt; between a LR and an SC. without this information it imposes a<br>
&gt; significantly higher hardware implementation cost and complexity than<br>
&gt; might at first appear.<br>
<br>
There is no limit.<br></blockquote></div></div><div dir="auto"><br></div><div dir="auto">I think the issue is not how many instructions can be put between LR and SC, since both OpenPower and RISC-V have no limit, but instead: how many and which kind of instructions can be put in between a LR and SC while retaining an architectural forward-progress guarantee. Just snooping and deleting the reservation is not sufficient if you want a forward-progress guarantee, since it is totally possible for the following loop to live-lock:</div><div dir="auto"><div dir="auto">loop:</div><div dir="auto">lwarx r5,0,r3</div><div dir="auto">stwcx. r4,0,r3</div><div dir="auto">bne loop</div><div dir="auto"><br></div><div dir="auto">The following assumes lwarx is implemented by obtaining the cache block in the Exclusive or Modified states in the MESI cache coherency protocol.</div><div dir="auto">Assume two cpu threads T1 and T2 are both executing the loop:</div><div dir="auto">T1: lwarx</div><div dir="auto">cache block is moved to T1 in the Exclusive state.</div><div dir="auto">T2: lwarx</div><div dir="auto">cache block is moved to T2 in the Exclusive state, breaking T1&#39;s reservation.</div><div dir="auto" style="font-family:sans-serif"><div dir="auto">T1: stwcx. -- fails</div><div dir="auto">T1: bne loop -- branches</div><div dir="auto">T1: lwarx</div><div dir="auto">cache block is moved to T1 in the Exclusive state, breaking T2&#39;s reservation.</div><div dir="auto"><div dir="auto">T2: stwcx. -- fails</div><div dir="auto">T2: bne loop -- branches</div><div dir="auto">T2: lwarx</div><div dir="auto">cache block is moved to T2 in the Exclusive state, breaking T1&#39;s reservation.</div><div dir="auto"><div dir="auto">T1: stwcx. -- fails</div><div dir="auto">T1: bne loop -- branches</div><div dir="auto">T1: lwarx</div><div dir="auto">cache block is moved to T1 in the Exclusive state, breaking T2&#39;s reservation.</div><div dir="auto"><div dir="auto">T2: stwcx. -- fails</div><div dir="auto">T2: bne loop -- branches</div><div dir="auto">T2: lwarx</div><div dir="auto">cache block is moved to T2 in the Exclusive state, breaking T1&#39;s reservation.</div><div dir="auto"><div dir="auto">T1: stwcx. -- fails</div><div dir="auto">T1: bne loop -- branches</div><div dir="auto">T1: lwarx</div><div dir="auto">cache block is moved to T1 in the Exclusive state, breaking T2&#39;s reservation.</div><div dir="auto"><div dir="auto">T2: stwcx. -- fails</div><div dir="auto">T2: bne loop -- branches</div><div dir="auto">T2: lwarx</div><div dir="auto">cache block is moved to T2 in the Exclusive state, breaking T1&#39;s reservation.</div><div dir="auto">...</div><div dir="auto">live-lock</div><div dir="auto"><br></div><div dir="auto">RISC-V has an architectural forward-progress guarantee for the equivalent loop, suggesting that a cpu implementation prevents live-lock by blocking other cpus from taking the cache block associated with a reservation for a few cycles (enough for at least 16 simple integer instructions), giving the cpu enough time to get to the store-conditional and successfully store.</div><div dir="auto"><br></div><div dir="auto">Jacob</div></div></div></div></div></div></div></div></div>