3 ms·

> Simply compare-and-swap the head (and on failure, try again). It doesn't help with ABA at all, does it? Unless you assume that nodes are immutable and the sa

> Simply compare-and-swap the head (and on failure, try again). It doesn't help with ABA at all, does it? Unless you assume that nodes are immutable and the same pointer is never reused, of course.

dragontamer 4y ago
I forgot about that other ABA issue. Still, that's easily solved: 64-bit version number + 64-bit pointer (or 32-bit version number + 32-bit pointer) for a 128-bit (or 64-bit) compare-and-swap. All modern CPUs support 128-bit CAS. EDIT: The version number is incremented by +1 each time. It is unlikely that you'd overflow 64-bit version number and risk an ABA problem, though 32-bits can be overflowed surprisingly quickly in today's computers. -------- EDIT2: Note: I'm pretty sure (but not 100% sure) that the Head of a linked-list stack can be "simply" compared-and-swapped to remain lock-free and 100% valid (ie: 64-bit compare and swap over the 64-bit pointer). I did not mean to imply that you can "CAS any arbitrary node of a linked-list". A fully generic linked list is possible and I've seen it with the 128-bit CAS operator, but that wasn't what I was going for originally.
- murderfs 4y ago
  > EDIT2: Note: I'm pretty sure (but not 100% sure) that the Head of a linked-list stack can be "simply" compared-and-swapped to remain lock-free and 100% valid (ie: 64-bit compare and swap over the 64-bit pointer). No, you cannot. The problem is what you're comparing and swapping into the head during a pop. You want to do the moral equivalent of `current = list; list.compare_exchange(current, current->next)`, but current->next might have changed if someone else popped the original head, pushed something else, and then pushed the original head again. You need double CAS or LL/SC or a more complicated scheme to make this work.
  - dragontamer 4y ago
    Fair catch. That's obscure but it looks like you're correct in this case.
    - murderfs 4y ago
      It might not be immediately obvious that this can happen, but in practice, this scenario happens very frequently, because if you free a node and then malloc a node, you're very likely to get the same address back with most memory allocators.
  - AstralStorm 4y ago
    You can get away with single CAS if you don't need full size pointers. Of course then you're actually using your list to refer to an array.
    - dragontamer 4y ago
      It should be noted that on most x86 machines, they only support 48-bit pointers, with 16 free bits you can use. I think some Intel chips have 57-bit support. But no CPU actually reads all 64-bits for some reason. So yeah, you can shove count-bits, either 16 of them or 7 of them or so.

> Simply compare-and-swap the head (and on failure, try again). It doesn't help with ABA at all, does it? Unless you assume that nodes are immutable and the same pointer is never reused, of course.

dragontamer 4y ago

I forgot about that other ABA issue. Still, that's easily solved: 64-bit version number + 64-bit pointer (or 32-bit version number + 32-bit pointer) for a 128-bit (or 64-bit) compare-and-swap. All modern CPUs support 128-bit CAS. EDIT: The version number is incremented by +1 each time. It is unlikely that you'd overflow 64-bit version number and risk an ABA problem, though 32-bits can be overflowed surprisingly quickly in today's computers. -------- EDIT2: Note: I'm pretty sure (but not 100% sure) that the Head of a linked-list stack can be "simply" compared-and-swapped to remain lock-free and 100% valid (ie: 64-bit compare and swap over the 64-bit pointer). I did not mean to imply that you can "CAS any arbitrary node of a linked-list". A fully generic linked list is possible and I've seen it with the 128-bit CAS operator, but that wasn't what I was going for originally.

murderfs 4y ago
> EDIT2: Note: I'm pretty sure (but not 100% sure) that the Head of a linked-list stack can be "simply" compared-and-swapped to remain lock-free and 100% valid (ie: 64-bit compare and swap over the 64-bit pointer). No, you cannot. The problem is what you're comparing and swapping into the head during a pop. You want to do the moral equivalent of `current = list; list.compare_exchange(current, current->next)`, but current->next might have changed if someone else popped the original head, pushed something else, and then pushed the original head again. You need double CAS or LL/SC or a more complicated scheme to make this work.
- dragontamer 4y ago
  Fair catch. That's obscure but it looks like you're correct in this case.
  - murderfs 4y ago
    It might not be immediately obvious that this can happen, but in practice, this scenario happens very frequently, because if you free a node and then malloc a node, you're very likely to get the same address back with most memory allocators.
- AstralStorm 4y ago
  You can get away with single CAS if you don't need full size pointers. Of course then you're actually using your list to refer to an array.
  - dragontamer 4y ago
    It should be noted that on most x86 machines, they only support 48-bit pointers, with 16 free bits you can use. I think some Intel chips have 57-bit support. But no CPU actually reads all 64-bits for some reason. So yeah, you can shove count-bits, either 16 of them or 7 of them or so.