mulle_objc: Wasting a lot of time with the ABA problem

The recent “lull” in this blog, is due to my attempts at solving the ABA problem in a useful manner for the mulle_objc runtime.

The ABA problem in Objective-C happens, when you replace the method cache with a new one. The old cache can not just be discarded, because other threads might still be accessing it. There is no good way to determine, when it’s a good time to free it.

Easy solutions

• Just leak. This may not be as bad as it sounds, if the number of cache frees is small.
• Make the cache initially big enough, so that there is no need to resize. If the cache runs full, crash. Let user indicate preferred cache size with class method.
• Maintain a list of leaks and defer the problem to the user

More involved solutions

From the Wikipedia article:

1. Tagged state reference would mean another masking operation during message sending, no good.
2. Intermediate nodes is, as I understand it, even slower.
3. Deferred reclamation is actually a number of different algorithms

Deferred reclamation

1. Hazard pointers means I would have to “advertise” each read of the cache and then “un-advertise” it again. Way too slow.
2. Automatic garbage collector means magic, and I don’t have it in C anyway.
3. Platform specific niceties, I don’t want to depend on those.

So basically I am trying to write my own deferred reclamation algorithm. The basic idea is this:

• Every thread that wants to access the ObjC runtime has to “register” first.
• The number of threads registered at the time of the “free” is the retain count of the freed cache. The cache is not actually freed yet, but stored.
• Every thread periodically checks in (think `-[NSAutoreleasePool dealloc]), when a thread checks in the retain count is reduced. When all threads have checked in the retain count is zero and the cache can be freed.

That’s it in a nutshell. In real life it’s a bit more complicated because threads can appear and disappear pretty much at random. This doesn’t sound too bad to implement, but it really is a bitch, because I want to have it lock-free. With a lock it’s not really a problem, but then the runtime isn’t lock-free, which I would like to avoid.

An unavoidable obstacle with cooperative schemes

Assume that you have two threads, one thread is busy freeing caches and is also checking in at regular intervals, the other thread is blocked in getchar(). The retain count of all those freed caches will stay at 1 and nothing will be reclaimed. In a cooperative scheme, this is unavoidable, unless you unregister before each blocking operation. That is clearly beyond the scope of mulle_objc.