PowerPC e500 Core Family Reference Manual, Rev. 1
A-6 Freescale Semiconductor
Programming Examples
A.1.3 List Insertion
This example shows how lwarx and stwcx. can be used to implement simple insertion into a singly
linked list. (Complicated list insertion, in which multiple values must be changed atomically, or in
which the correct order of insertion depends on the contents of the elements, cannot be
implemented in the manner shown below and requires a more complicated strategy such as using
locks.)
The next element pointer from the list element after which the new element is to be inserted, here
called the parent element, is stored into the new element, so that the new element points to the next
element in the list: this store is performed unconditionally. Then the address of the new element is
conditionally stored into the parent element, thereby adding the new element to the list.
In this example it is assumed that the address of the parent element is in GPR3, the address of the
new element is in GPR4, and the next element pointer is at offset 0 from the start of the element.
It is also assumed that the next element pointer of each list element is in a reservation granule
separate from that of the next element pointer of all other list elements. See Section 3.3.1.7,
“Atomic Update Primitives Using lwarx and stwcx.”
loop: lwarx r2,0,r3 #get next pointer
stw r2,0(r4) #store in new element
msync #order stw before stwcx.(can omit if not MP)
stwcx. r4,0,r3 #add new element to list
bc 4,2,loop #loop if stwcx. failed
In the preceding example, if two list elements have next element pointers in the same reservation
granule then, in a multiprocessor, livelock can occur. (Livelock is a state in which processors
interact in a way such that no processor makes progress.)
If it is not possible to allocate list elements such that each element's next element pointer is in a
different reservation granule, livelock can be avoided by using the following, more complicated,
sequence.
lwz r2,0(r3) #get next pointer
loop1: or r5,r2,r2 #keep a copy
stw r2,0(r4) #store in new element
msync #order stw before stwcx.
loop2: lwarx r2,0,r3 #get it again
cmpw r2,r5 #loop if changed (someone
bc 4,2,loop1 # else progressed)
stwcx. r4,0,r3 #add new element to list
bc 4,2,loop #loop if failed
To Next Page
Loading...
