A practical multi-word compare-and-swap operation

Question

In the paper with the same title as that of this question, the authors describe how to build a nonblocking linearizable multi-word CAS operation using only a single-word CAS. They first introduce the double-compare-single-swap operation - RDCSS, as follows:

word_t RDCSS(RDCSSDescriptor_t *d) {
  do {
    r = CAS1(d->a2, d->o2, d);
    if (IsDescriptor(r)) Complete(r);
  } while (IsDescriptor(r));
  if (r == d->o2) Complete(d); // !!
  return r;
}

void Complete(RDCSSDescriptor_t *d) {
  v = *(d->a1);
  if (v == d->o1) CAS1(d->a2, d, d->n2);
  else CAS1(d->a2, d, d->o2);
}

where the RDCSSDescriptor_t is a structure with the following fields:

• a1 - address of the first condition
• o1 - value expected at the first address
• a2 - address of the second condition
• o2 - value expected at the second address
• n2 - the new value to be written at the second address

This descriptor is created and initialized once in a thread which initiates the RDCSS operation - no other thread has a reference to it until the first CAS1 in the function RDCSS succeeds, making the descriptor reachable (or active in the terminology of the paper).

The idea behind the algorithm is the following - replace the second memory location with a descriptor saying what you want to do. Then, given that the descriptor is present, check the first memory location to see if its value changed. If it hasn't, replace the descriptor at the second memory location with the new value. Otherwise, set the second memory location back to the old value.

The authors do not explain why the line with the !! comment is necessary within the paper. It seems to me that the CAS1 instructions in the Complete function will always fail after this check, provided that there is no concurrent modification. And if there was a concurrent modification between the check and the CAS in Complete, then the thread doing the check should still fail with its CAS in Complete, since the concurrent modification should not use the same descriptor d.

My question is: Can the check in the function RDCSSS, if (r == d->o2)... be omitted, with RDCSS still maintaining the semantics of a double compare, single swap instruction which is linearizable and lock-free? (line with !! comment)

If not, can you describe the scenario where this line is actually necessary to ensure correctness?

Thank you.

Answer 1

In a concurrent runtime environment simple things can seem weird ... hope this can help.

We have a BUILT-IN ATOMIC CAS1 having this semantic:

int CAS1(int *addr, int oldval, int newval) {
  int currval = *addr;
  if (currval == oldval) *addr = newval;
  return currval;
}

We need to define an ATOMIC RDCSS function using CAS1 and having the following semantic:

int RDCSS(int *addr1, int oldval1, int *addr2, int oldval2, int newval2) {
  int res = *addr;
  if (res == oldval2 && *addr1 == oldval1) *addr2 = newval2;
  return res;
}

Intuitively: we need to CONCURRENTLY change the value at addr2 only if *addr1 == oldval1 ... if another thread is changing it we can help the other thread to complete the operation, then we can retry.

RDCSS function will be used (see article) to define CASN. Now, we define a RDCSS Descriptor in the following way:

RDCSSDESCRI
int *addr1   
int oldval1
int *addr2   
int oldval2
int newval2

Then we implement RDCSS in the following way:

int RDCSS( RDCSSDESCRI *d ) {
  do {
    res = CAS1(d->addr2, d->oldval2, d);  // STEP1
    if (IsDescriptor(res)) Complete(res); // STEP2
  } while (IsDescriptor(res);             // STEP3
  if (res == d->oldval2) Complete(d);     // STEP4
  return res;
}

void Complete( RDCSSDESCRI *d ) {
  int val = *(d->addr1);
  if (val == d->oldval1) CAS1(d->addr2, d, d->newval2);
    else CAS1(d->addr2, d, d->oldval2);  
}

• STEP1: first we try to change the value of *addr2 to our (own) descriptor d, if CAS1 succeeds then res == d->oldval2 (i.e. res is NOT a descriptor)
• STEP2: check if res is a descriptor i.e. STEP1 failed (another thread changed addr2) ... help another thread completing the operation
• STEP3: retry the STEP1 if we didn't succeed in storing our descriptor d
• STEP4: if we fetched our expected value from addr2 then we succeeded in storing our descriptor (pointer) in addr2 and we can complete our task storing newval2 to *addr2 iif *addr1 == oldval1

ANSWER TO YOUR QUESTION

If we omit STEP4 then the if(... && *addr1==oldval1) *addr2=newval2 part of the RDCSS semantic will never be executed (... or better: it can be executed in an umpredictable way by other threads helping the current one).

As pointed out by you in your comment the condition if(res == d1->oldval2) at STEP4 is unnecessary: even if we omit it, both CAS1 in Complete() will fail because *(d->addr2)!=d. Its only purpouse is avoid a function call.

Example T1=thread1, T2=thread2:

remember that addr1 / addr2 are in a shared data zone !!!

T1 enter RDCSS function
T2 enter RDCSS function
T2 complete STEP1 (and store the pointer to its descriptor d2 in addr2)
T1 at STEP1 the CAS1 fails and res = d2
T2 or T1 completes *(d2->addr2)=d2->newval2 (suppose that *(d2->addr1)==d2->oldval1)
T1 execute STEP1 and now CAS1 can fail because *addr2 == d2->newval2
   and maybe d2->newval2 != d1->oldval2, in every case at the end 
   res == d2->newval2 (fail) or
   res == d1->oldval2 (success)
T1 at STEP2 skips the call to Complete() (because now res is not a descriptor)
T1 at STEP3 exits the loop (because now res is not a descriptor)
T1 at STEP4 T1 is ready to store d1->newval2 to addr2, but only if
   *(d1->addr2)==d (we are working on our descriptor) and *(d1->addr1)==d1->oldval1
   ( Custom() function)