Do Simple Spin Lock raise a deadlock that be cause by exclusive memory access instruction?
I have a idea about that LDXR/STXR occur a deadlock. Is this case possible?
Two core access global variable in a few of instruction clock difference. And repeat. Both cores is running same code.
My Exclusive Simple Spin Lock Assembly(Image):
.spin_lock:
NOP
.stxr_fail:
LDXR R0, .data+0
CMP R0, #0
BNE .spin_lock
MOV R0, #1
STXR W0, R0, .data+0
CMP W0, #0
BNE .stxr_fail
BL critical_section()
MOV R0, #0
STR R0, .data+0
RET
.data:
.word lock
Do a deadlock occur on multi-core running? (Image):
Each line of the same color is atomic step. It operates sequentially in numerical step. This is occurred a deadlock by 6~11 steps.
If I misunderstand, Please kindly explain
The load exclusive is going to check for a zero then try again until it is zero.
.spin_lock:
NOP
.stxr_fail:
LDXR R0, .data+0
CMP R0, #0
BNE .spin_lock
If not zero then you end up with a
load exclusive
store exclusive
check if the store worked.
repeat the whole thing if not.
If two masters A and B were to perfectly line up
loadx a
loadx b
storex a
storex b
Between the Exclusive Read and the Exclusive Write there can be other Non-exclusive transfers.
...
If no other master has written to that location since the Exclusive Read transfer, the Exclusive Write transfer is successful and updates memory.
...
If another master has written to that location since the Exclusive Read transfer, the Exclusive Write transfer is failed and the memory location is not updated.
the storex from master a would succeed, the storex from master b would fail so master a would exit the loop. master b will continue to loop until the load returns non-zero.
So it can't deadlock even for a little bit.
I would have to read some more to confirm that loadx a, loadx b, storex a would have a valid store. From the quotes above that would be the case. If not then you would be in a situation where neither would obtain lock until such time as one gets interrupted or for any other reason changes its beat frequency possibly allowing the other master to get a clean load store exclusive. For example can the logic simply remember the id of the last ldrex and compare that to the next strex
The Exclusive Access Monitor must be capable of concurrently monitoring at least one address location for each Exclusive access capable master in the system.
...
A slave that does not support exclusive accesses can ignore the AxLOCK signals. It must provide an OKAY response for both normal and exclusive accesses. A slave that supports exclusive access must have monitor hardware. This specification recommends that such a slave has a monitor unit for each exclusive-capable master ID that can access it. The ARM Architecture Reference Manual, ARMv7-A and ARMv7-R edition defines an exclusive access monitor, and a single-ported slave can have such an exclusive access monitor external to the slave. A multiported slave might require internal monitoring.
What that means is that if the slave supports exclusive access then it must have a monitor (must store the id from a prior ldrex and compare it to the current strex). but it is only recommended that it have a monitor per master, so if it doesn't have a monitor per master then you likely end up in a situation like this
ldrex a, ldrex b, strex a, strex b. The ldrex b and strex a don't match so the store doesn't happen, now in that case the ldrex b and strex b do match so we would assume that master b gets the lock leaves the loop master a has to wait for master b to zero the memory location (clrex or perhaps a simple str).
Arm has axi and ahb bus specifications as well as different revisions of these specifications and which one goes with which core is perhaps in the technical reference manual for that core. And to get the complete answer you should at least try to match these up and read the right revision spec for the core you are using and not assume that they all are exactly the same. Also understand the L1 cache is part of the arm core, the l2 cache is outside the core but you can buy an l2 from arm (or make your own) one would hope that ARMs logic supports exclusive access as documented.
Beyond that you are into the chip vendors territory and they can implement what they want broken or not, to truly share one would want these accesses to be in a common memory space shared by the various cores and not having the L1 or L2 cache answer and have coherency problem. The chip vendor may choose not to support exclusive access and will return OKAY. What that looks like to code like this is it will spin forever, the "return value" from the strex only passes on an EXOKAY if that is never returned because the design does not support exclusive access then the loop is infinite. Been there, seen this, that's how I know. An older document said that exclusive access support was not required for uniprocessor designs, current versions of the specs do not say that they simply say things related to if the slave supports or doesn't support exclusive access then.
If the ldrex/strex lock is going to work you have to be working against a slave that supports exclusive access in that case you have a single monitor or a monitor per master and I believe I have shown the worst cases above if you get really really really lucky ldrex a, ldrex b, strex a, strex b for two masters a and b and one should win on that first pass through. And the other gets stuck waiting as desired/designed. Add more masters and mix the loads and stores from them and you end up with the same situation, one will win the others will lose and go into the ldrex not zero loop. now interestingly if you have two or more of them in that loop then when the one master that has lock releases it you don't need to be all that lucky for the others competing for the lock to get a load load store store situation.