Nat! bio photo

Nat!

Senior Mull.

Twitter RSS

Github

mulle-aba: How it works, part 1

mulle-aba is my solution to the ABA problem, released as an alpha version.

mulle-aba works when all threads accessing the shared resource cooperate. For that each thread has to register. At the end of it's life it (automatically) unregisters.

As an example the following drawing shows the lifetime of three threads.

3 Threads

mulle-aba separates the thread life-times into time segments. (the space between the vertical lines). A new segment begins, when a thread registers or unregisters.

In the first time segment, there is one thread running concurrently. In the second time segment two threads are active. in the third time segment three, then only two again and then one.

The basic principles of operation

  1. Each thread registers with mulle-aba.
  2. Every resource that is freed through mulle-aba gets retained by each currently active thread. It's retain count is therefore equal to the number of registered threads in the current time segment. The resource is not immediately freed.
  3. Each thread at its end of life unregisters. It then releases all its retaining resources. When the retain count of the resource reaches zero, the resource is freed.

This is foolproof, but not terribly useful, as resources won't be freed often enough. Therefore a thread can and should act, as if it periodically unregisters and registers again. This is done by doing a check in, which behaves just like that.

A check in is like unregister + register

  1. When a thread checks in all resources that have been retained until up to this point in time will be released. The thread will put up a memory barrier, thereby ensuring that it will not read stale data. Subsequent "frees" will be retained by the thread.

Because of the memory barrier, the thread will be cleansed of all stale cached data and can resume with execution, that is like just having registered with mulle-aba for the first time.

A check in therefore creates a new time segment.

The Snafu principle

It is of great use to mulle-aba that the retain counts of the time segments will act like the Worm of Bemer more commonly known as the Snafu worm. The retain counts may stretch out, but they never snap in half.

Here is a drawing of the scenario above as it progresses.

Snafu

In the first picture all three threads are still active. In the second picture thread #1 has unregistered and in the third picture thread #3 has unregistered.

Looking at all retain counts at any given moment in time, the values never decrease from past to present. In other words the oldest time segment is always decremented to zero first.

A bit more technical

Technically mulle-aba keeps a small struct storage for each time segment. There is a linked list of the resources to be freed in this storage, there is also a retain count.

Each thread remembers the current time segment when it registers. When it unregisters all the time segments from registration time until now will get their retain count decreased.

If the retain count is zero, the resource will be freed. This is nice, because the storage for the time segment can be reclaimed and also the linked list can be reused.

3 Threads with resources

In the drawing above the third thread has not unregistered yet. Seven resources named 'A' - 'G' were freed in alphabetical order. You can see the linked lists of each time segment and (again) the retain counts of the time segments.

Optimizations

Technically a new time segment is only created, when necessary at the time of a free. So lots of check ins coalesce and do not by themselves create new time segments. A time segment without an entry in the linked list does not happen.

With only one thread running mulle-aba switches to single-threaded mode. In single-threaded mode resources will be freed immediately.

Yeah so ?

OK that's basically it, it's not too complicated. The trick is how to make all this lock free. That will be covered in part #2.

Continue to mulle-aba: How it works, part 2


Post a comment

All comments are held for moderation; basic HTML formatting accepted.

Name:
E-mail: (not published)
Website: