multi-thread control issue

[XiaominZou]

hello，I find there is a issue in concurrent CCEH. As below code shows, suppose a write transaction T1 visits a invaild record R1(caused by lazy deletion) and goes to sleep before reseting the key to INVAILD. At this time, another write transaction T2 modifies R1. Then T1 wakes up and overwrite R1. There will incur a conflict .

#ifdef INPLACE
  if (sema == -1) return 2;
  if ((key_hash >> (8*sizeof(key_hash)-local_depth)) != pattern) return 2;
  auto lock = sema;
  int ret = 1;
  while (!CAS(&sema, &lock, lock+1)) {
    lock = sema;
  }
  Key_t LOCK = INVALID;
  for (unsigned i = 0; i < kNumPairPerCacheLine * kNumCacheLine; ++i) {
    auto slot = (loc + i) % kNumSlot;
    if ((h(&_[slot].key,sizeof(Key_t)) >> (8*sizeof(key_hash)-local_depth)) != pattern) {
      _[slot].key = INVALID;
    }
    if (CAS(&_[slot].key, &LOCK, SENTINEL)) {
      _[slot].value = value;
      mfence();
      _[slot].key = key;
      ret = 0;
      break;
    } else {
      LOCK = INVALID;
    }
  }
  lock = sema;
  while (!CAS(&sema, &lock, lock-1)) {
    lock = sema;
  }
  return ret;

[moohnam]

If the value isn't INVALID, the first transaction T1 cannot write its value as we use "Compare and Swap" instruction. Therefore, T1 should find another place to write.

[XiaominZou]

I mean, when the first thread goes to C1(showed in bellow codes) and sleeps before resetting the key to INVALID, the second thread also finds the record in the same slot doesn't match the pattern, so it set the key INVALID and write a record into that slot. Then the first thread wakes, and perform C2(resetting the key to INVALID again), which is not protected by CAS. So the first thread can go on, and overwrite the record that the second thread has just inserted before.

ifdef INPLACE

if (sema == -1) return 2; if ((key_hash >> (8sizeof(key_hash)-local_depth)) != pattern) return 2; auto lock = sema; int ret = 1; while (!CAS(&sema, &lock, lock+1)) { lock = sema; } Key_t LOCK = INVALID; for (unsigned i = 0; i < kNumPairPerCacheLine kNumCacheLine; ++i) { auto slot = (loc + i) % kNumSlot; if ((h(&_[slot].key,sizeof(Key_t)) >> (8*sizeof(key_hash)-localdepth)) != pattern) { //C1 [slot].key = INVALID; //C2 } if (CAS(&[slot].key, &LOCK, SENTINEL)) { [slot].value = value; mfence(); _[slot].key = key; ret = 0; break; } else { LOCK = INVALID; } } lock = sema; while (!CAS(&sema, &lock, lock-1)) { lock = sema; } return ret;

[moohnam]

Oh, I get it now. I've looked at the wrong part. Thank you. I've just fixed the code.