mulle-aba: How it works, part 2
Continued from mulle-aba: How it works, part 1
Please read up on atomic operations, if you are unfamiliar with them.
Basic principles of retain counting
- A resource will be freed if the retain count is 0
- A resource that has just been allocated has a retain count of 1.
- A resource that has a retain count of 1 or 0 is single threaded
The lockfree linked list
Here the trick is, that the usage of the linked list by
mulle-aba is extremely limited.
As used by the time segment resource chain the linked list grows and never shrinks until the retain count reaches zero. At that time the time segment is single-threaded anyway and we just deal with it without atomic operations.
Adding to the linked list
When this code executes list is multi-threaded by principle, but entry is known to be single-threaded. Therefore only one pointer needs to be CASed. No problem.
Removing the complete linked list
This is simple, just CAS the head with a NULL. If it works, then we’ve got it. This is not actually used directly by
mulle-aba, but the next function builds on top of it.
Removing the first entry of the linked list
The lock free linked list is also used to store various stuff, that
mulle-aba uses for management like the linked list entries themselves. A unused linked list entry is just like any other unused linked list entry, so removal of the first node is good enough.
This code is more complicated. Here the solution is:
- remove the whole linked list
- lop off the first entry, if there is one
- try to place the remainder of the list back
- if someone else added something to the list, grab the new whole list. Join both lists. Repeat.
In the worst case there will not be a linked list entry available for reuse to all threads, but it is harmless, because those thread can just
malloc a new entry.
Continue to mulle-aba: How it works, part 3