-2

I want to atomically swap two big memory locations defined as the struct VValue. Since the size of the struct is bigger that long, there is no architectural support to directly compare and swap the two structs. However, one way is to swap the pointers of the two structs and indirectly swap the memory locations.

Below is my code that is supposed to swap oldValue with b. The compare and swap builtin is used inside a do-while loop to make sure that the value of oldValue has not changed possibly by other threads while the swap is taking place (this code snippet is the simplified version of a more complicated swap with other conditions. Conditions are removed for brevity).


  template<typename A, typename B, typename C, typename D>
  struct VStructType{
    A a;
    B b;
    C c;
    D d;

    VStructType () {
      ;

    }

    VStructType (A a, B b, C c, D d) {
      this->a = a;
      this->b = b;
      this->c = c;
      this->d = d;

    }

  };

  typedef VStructType<uint32_t,uint32_t,uint32_t,uint32_t> VValue;

  bool swap(VValue* oldValue, VValue b)
  {
    bool r = 0;
    VValue* c;
    VValue *w = new VValue();

    do{
      c = oldValue;
      w->a = b.a;
      w->b = b.b;
      w->c = b.c;
      w->d = b.d;
    } while (!(r = __sync_bool_compare_and_swap(&oldValue, c, w)));
    return r;
  }

  int main()
  {
    VValue oldValue = VValue(1,2,3,4);
    VValue b = VValue(10,12,2,8);
    swap(&oldValue, b);
  }

The problem is that after the swap inside the swap function, the value of the oldValue is changed to the new value, but after returning from the swap function the oldValue is not changed. It seems like the reference to the oldValue is a temporary reference and when the swap happens it only swaps the new reference not the actual pointer to the oldValue. The reason that the reference is passed to the __sync_bool_compare_and_swap function is that the first argument is the pointer to a variable whose value is to be compared with.

My questions:

1) Is there a way to pass the pointer of the pointer of oldValue directly to the __sync_bool_compare_and_swap function?

2) Is this approach possible when the oldValue is an element in an array?

Note: use g++ -latomic -std=gnu++11 to compile.

Branky
  • 373
  • 8
  • 23
  • 2
    To be perfectly honest, I don't even know what happens in this code. What is swapped with what? What is new value, what is old value, why there is suddenly "new" in the code? Why are you not fine with just swapping pointers? – Jędrzej Dudkiewicz Feb 25 '20 at 20:41
  • I want to swap ```oldValue``` with ```b``` and both are just struct instances. Since I need to synchronize my code I have to use atomic primitives. – Branky Feb 25 '20 at 20:50
  • `I need to synchronize my code` - with what do you synchronize the code? Why do you have to use `__sync_bool_compare_and_swap`? – KamilCuk Feb 25 '20 at 20:55
  • Changing the approach is an option only when I'm sure this does not work. Using ```mutex``` or lock-based synchronization degrades the performance. – Branky Feb 25 '20 at 20:55
  • Well, I'm not a world class expert on lock-free algorithms and such, but my understanding is that you either swap atomically values fitting into longest variable supported by CAS on your platform or you simply use locks. Or you simply copy structures to separate locations and returns pointers to them like it is done in languages with garbage collector - old values will be collected as required. – Jędrzej Dudkiewicz Feb 25 '20 at 21:03
  • You have a local b shadowing the parameter b. This and other things make this code hard to understand. It isnt obvious what it is supposed to achieve in detail – 463035818_is_not_an_ai Feb 25 '20 at 21:05
  • Your argument to `swap` is `VValue* oldValue`, but you then declare `VValue oldValue = VValue(1,2,3,4);`. I'm not even sure that's legal, but assuming it is, it definitely means you do nothing with the argument (because from the moment you declare `VValue oldValue`, the argument is shadowed). – ShadowRanger Feb 25 '20 at 21:05
  • @idclev463035818 post edited – Branky Feb 25 '20 at 21:06
  • @ShadowRanger I edited the post – Branky Feb 25 '20 at 21:06
  • 2
    @Branky: Okay, less bad, but you received `oldValue` as a *copy* of the pointer in the caller (it refers to the same data, but it's not linked to the caller, as it's not a reference). So swapping out its value doesn't matter to the caller, the caller's *pointer* can't be changed, only what it points to (and only as long as the function's copy of the pointer isn't reassigned to point elsewhere). You need to receive a reference to the pointer, or a double-pointer, if you want to change the caller's pointer. – ShadowRanger Feb 25 '20 at 21:09
  • @ShadowRanger That's exactly what I want but don't know how to do it. I'm just passing the reference of the oldValue and not a copy. Is copying happening under the hood? Can you suggest a solution? – Branky Feb 25 '20 at 21:14
  • @ShadowRanger You won't be able to get a mutable reference or pointer to non-const to the value of `&oldValue`. – François Andrieux Feb 25 '20 at 21:20
  • It looks like you are trying to change the address of an object. It's entirely impossible in C++ to change the address of an existing object by any means. If you think that's what your code is doing and it compiles, either it isn't actually doing what you expect or it has Undefined Behavior and still won't do what you expect. – François Andrieux Feb 25 '20 at 21:21
  • 1
    @Branky: [Pointers are not references](https://stackoverflow.com/q/57483/364696). If you don't understand the difference between them, it is *way* too early for you to be looking at implementing complex lock-free algorithms in C++; you need to walk before you can run. As is, your code can't work anyway; you want to swap a pointer in the caller, but the caller doesn't *have* a pointer, it gave you a pointer to its stack-allocated memory. There's no pointer to change in the caller. – ShadowRanger Feb 25 '20 at 21:22
  • 1
    You have a `new`, and the result is neither managed by an owning class like a smart pointer nor is it release with `delete`. You have a memory leak in your function. – François Andrieux Feb 25 '20 at 21:23
  • @FrançoisAndrieux: Yeah, I noticed that later. I was considering the function on its own (which couldn't work at all given the prototype), and only noticed that the caller was trying to use it in a way that no prototype change could fix later. – ShadowRanger Feb 25 '20 at 21:24
  • @FrançoisAndrieux See the answer posted – Branky Feb 26 '20 at 02:41
  • @ShadowRanger See the answer posted – Branky Feb 26 '20 at 02:41

1 Answers1

-1

The trick is to pass the reference of the pointer to the oldValue to the swap function and change the swap as follows:

bool swap(VValue** oldValue, VValue b)
  {
    bool r = 0;
    VValue* c;
    VValue *w = new VValue();

    do{
      c = *oldValue;
      w->a = b.a;
      w->b = b.b;
      w->c = b.c;
      w->d = b.d;
    } while (!(r = __sync_bool_compare_and_swap(oldValue, c, w)));
    if(!r)
      delete w;
    return r;
  }

int main()
  {
    VValue* oldValue = new VValue(1,2,3,4);
    VValue b = VValue(10,12,2,8);
    swap(&oldValue, b);
  }
Branky
  • 373
  • 8
  • 23
  • This isn't legal code as written; `swap` would need to accept `VValue**` for this to work correctly. Also, semantically, you didn't pass a reference, you passed a double-pointer. – ShadowRanger Feb 26 '20 at 02:48
  • `b` is left unchanged. This is a complicated assignment operation which only works with a raw owning pointer. – François Andrieux Feb 26 '20 at 11:57
  • ''' b ''' was never meant to be changed. That's why it is passed by value. Also, I don't see any problem with a complicated solution when the performance is crucial. – Branky Feb 26 '20 at 16:03