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.

The actual source code of the linked list is in mulle_aba_linked_list.c and mulle_aba_linked_list.h

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.

void  _mulle_aba_linked_list_add( struct _mulle_aba_linked_list *list,
                                  struct _mulle_aba_linked_list_entry  *entry)
{
   struct _mulle_aba_linked_list_entry  *head;

   do
   {
      head         = _mulle_atomic_read_pointer( &list->_head);
      entry->_next = head;
   }
   while( ! _mulle_atomic_compare_and_swap_pointer( &list->_head, entry, head));
}

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.

struct _mulle_aba_linked_list_entry  *_mulle_aba_linked_list_remove_all( struct _mulle_aba_linked_list *list)
{
   struct _mulle_aba_linked_list_entry  *head;

   do
   {
      head = _mulle_atomic_read_pointer( &list->_head);
      if( ! head)
         break;
   }
   while( ! _mulle_atomic_compare_and_swap_pointer( &list->_head, NULL, head));

   return( head);
}

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