[Question] find_harris_herlihy_shavit relaxed load for tag

[leporia]

I was looking at the lock free list implementation and on find_harris_herlihy_shavit where we check the tag with a Relaxed load.

Is it because the tag is only ever set with a RMW on deletion? And only ever set from 0 to 1?

[kingdoctor123]

The reason for this is because what we really need at that point is the tag value, not the message view. To elaborate,

• Acquire load during traversal (e.g. find_harris, find_harris_michael, find_harris_herlihy_shavit) is necessary to guarantee that "in next iteration, it is safe to access next node." Suppose you are at node n1 and you are going to the next node n2 by reading the .next field of n1. If you just used relaxed load, then the current thread may see very old state of n2 (e.g. before initialization, or even before allocation of n2). This is indeed severe problem. So, to avoid this problem, we use acquire load on n1.next. Then, since message view of n1.next includes initialization of n2, it is now guaranteed that current thread never sees very old state of n2.
• However, at the end of find_harris_herlihy_shavit, we don't need acquire load since we will not access the next node.

[leporia]

But couldn't we get an old tag value then? For example we get a tag value of 0 and because of the relaxed load it is actually an old state. The new state is a tag value of 1. Then we return that we found the node and for example proceed with a lookup of an actually deleted value.

Is that a possibility?

[kingdoctor123]

Reading an old value cannot be prevented even if you use acquire load. Recall from the promising semantics that there is no guarantee that thread should read the latest value.

Consequently, as you said, it may happen that a thread reads tag value 0 even if latest tag value is 1. Nevertheless, this is a correct behavior and a good specification that accounts for this situation is an open research problem. For this class, you can just consider SC setting when reasoning about linearizability, and use promising semantics when reasoning about safety of traversal.

[BraSDon]

How can it happen that we get an old tag value?

We only change the tag with the RMW operation "fetch_or", therefore doing a relaxed read will not be able to get the value before the RMW as the message is adjacent.

[kingdoctor123]

According to promising semantics, each load operation reads from any message no earlier than the timestamp pointed by thread view. We don't have any constraints on reading from messages adjacent to other messages. To illustrate, consider a case where

• Messages are written on timestamps t=t0, t=t0+1, t=t0+2, t=t0+3
• Current thread view is pointing to t=t0+1
• Then, if a thread performs load operation, then it can read from any message between t=t0+1 and t=t0+3.

Note that adjacency of messages is designed for representing uniqueness of thread who wins the race. To illustrate,

• Suppose a memory location X initially has a value 0 at timestamp t=0
• Suppose there are multiple threads trying to perform CAS on X from 0 to 1.
• Since successful CAS only writes to the timestamp t=1, there must be at most one thread who succeeds in CAS.

[leporia]

Thanks for the detailed response. I also misunderstood how RMW writes work with promising semantics. Now it makes much more sense.