3 ms·
> 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
by 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 agoFair catch. That's obscure but it looks like you're correct in this case.
- murderfs 4y agoIt 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 agoYou 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 agoIt 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.