Using Immortality to Kill Accidental Callback Cycles

Using Immortality to Kill Accidental Callback Cycles

In this post: how I ensure consuming futures and cancel tokens from the collapsing futures library can’t introduce space leaks.

Human Error

Me, you, and humans in general are all terrible at consistently doing anything. Any process that relies on you not making a mistake is fundamentally error-prone. As programmers we spend all day every day being reminded of this fact when our code doesn’t work because of trivial mistake #628.

I worry about human error a lot when coding. How can I design things to minimize the opportunities we have to make a mistake? How do I make a human error impossible by design? How do I match the genius of, say, PHP’s self-salting self-versioning password hashing/verification functions?

That’s why the collapsing futures library has collapsing futures. Automatic flattening makes a particular type of brain-dead mistake I kept making (unwrapping too many or too few times, because the type system in Objective-C is too weak to detect that error) fundamentally impossible.

Another type of human error the collapsing futures library tries to make impossible is leaking memory due to an accidental reference cycle.

Automatic Reference Counting

In Objective-C, memory is managed by reference counting.

The main strength of reference counting, over “real” garbage collection, is predictable performance (especially when memory constrained). Cleanup is done eagerly, giving consistently good responsiveness instead of inconsistently great responsiveness.

The downside of reference counting is that it is too conservative. If you accidentally make a cycle of objects referencing each other, and fail to break the cycle before losing track of the objects, they will never be deallocated and so you have a memory leak. Being human, you’ll make that mistake now and then.

In most languages, reference counting is done automatically. Objective-C recently joined this club. Programmers used to have to handle the count manually by calling retain and release at the appropriate times but, thankfully, those days are almost over due to the introduction of ARC.

ARC is great. It (mostly) eliminates create-vs-get distinctions, handles retain-release matching, and generally saves you from human error. However, it does have costs. In particular, ARC makes it easier to accidentally create a reference cycle.

Accidental Cycles

Consider the following code:

...
self->counter = 0;
self->callback = ^{ counter++; };
...

Did you catch that? There’s a reference cycle in the code.

The block assigned to the callback field needs to be able to increment the counter field, so the block’s closure will include a reference to self. But self is storing a reference back to the block in the callback field. If we don’t nil the callback field before losing track of the object currently referred to as self, that’s a memory leak.

Assuming we know the block assigned to callback can’t outlive self, we can fix the leak by using a weak or unretained reference:

...
self->counter = 0;
__unsafe_unretained SomeType* weakSelf = self; // note: should use __weak in newer versions of iOS
self->callback = ^{ weakSelf->counter++; };
...

That’s not too complicated. Of course the real trick is consistently catching the problem. There’s lots of places for it to show up, especially if you’re coding in a block heavy style.

When using futures and cancel tokens you do tend to use a lot of blocks. Consequently, you’ll probably create references cycles all the time. For example, here’s code I’ve written:

...
self->lifetime = untilCancelledToken;
[untilCancelledToken whenCancelledDo:^{ [self terminate]; }];
...

Yup, that’s a reference cycle. self references untilCancelledToken which indirectly stores a reference to self (in the closure of a block in its list of handlers to run when it is cancelled).

Good thing we don’t have to fix it. That would be really inconvenient. I use this pattern all the time, because storing the token determining an object’s lifetime on that object makes it easy to ensure things created for it can be given the same lifetime. (Secondarily, failing to cancel the token determining an object’s lifetime does seem to imply you want it to operate forever, but nevermind that for now.)

This reference cycle is okay because of how TOCCancelToken is designed. It ensures the cycle is not self-sustaining. The cycle can only exist while the token’s source, which is not being kept alive by the cycle, continues to exist.

Discard upon Immortal

In last week’s post about cancellation tokens I said tokens are either cancelled or not-cancelled. In reality, there are two types of not-cancelled tokens: tokens in the StillCancellable state and tokens in the Immortal states.

Every token starts off in the StillCancellable state. A token can be manually transitioned to the Cancelled state via its source’s cancel method. That’s how things normally work. However, it’s also possible that a token’s source will be lost and deallocated before the token is cancelled. In that case, as soon as the source’s dealloc methods get called, its last act is to transition its token to the Immortal state.

The callbacks on an immortal token will never be called. They’re only supposed to be called if the token is cancelled, and it never will be. Since the callbacks will never be run, there’s no need to keep them around. They can be discarded without being run, allowing anything they reference to be cleaned up. This clears any and all references originating from the cancel token, breaking any cycles that involved it.

Here’s a diagram of a situation where a reference cycle can be broken by a token becoming immortal:

The above diagram shows a cancel token being used by some consumers and managed by a producer. The consumers have created reference cycles involving themselves and the token, but the producer has been careful to not expose the cancel token’s source to the consumers and to not create any cycles involving the source.

Now suppose the producer loses track of the cancel token’s source, or perhaps is cleaned up without telling the source to cancel its token. What happens?

• The only reference to the cancel token’s source dies, allowing the source to be deallocated.
• In its dealloc method, the source orders its cancel token to become immortal.
• The cancel token discards all of its cancel handlers.
• The reference cycles have been broken.

The resulting state looks like this:

The consumers created reference cycles, but those cycles were dependent instead of self-sustaining. The cycles could only exist as long as the token’s source was alive, so they were broken when the producer died.

Ultimately this means that, although consumers can make a space leak created by a producer worse, it’s impossible for them to introduce their own space leaks. The scope of the problem has been cut in half. Producers still have to be careful, but consumers don’t.

I have no doubt that, despite the source code of the iOS port of whispersystems‘ RedPhone we’re finishing up (and where I did the initial iterations on futures in Objective-C) being picked over and reviewed, this particular feature will nullify some brain-dead memory leak I didn’t even realize I wrote.

The same producer-careful consumer-safe semantics that apply to TOCCancelToken and TOCancelTokenSource also apply to TOCFuture and TOCFutureSource. All cycles created by consuming a future are broken if its source is deallocated.

The collapsing futures library also uses other tricks to avoid human error:

• If you register a callback when you’re on the main thread, the callback will run on the main thread. I got tired of constantly forgetting to get back before touching the UI, when callbacks just ran inline as the future/token was set.
• There used to be a whenCancelledCancel method. It was possible to make a tricky space leak by having a group of tokens all registered to cancel each others’ sources. It was replaced by the cancelTokenSourceUntil constructor method, which can’t introduce reference cycles because it only adds leaf nodes.
• There’s cycle detection in the automatic future flattening code, to ensure if a future ends up set to itself (even via intermediaries), it gets marked as immortal instead of hanging. Hopefully, when someone inevitably makes that particular mistake, the observable effect (the future mysteriously being in the immortal state instead of the flattening state) will save them some time.

Interesting fact: Garbage collection wouldn’t make all these issues moot. Last time I checked, the cancellation token in .Net fails to discard its callbacks when its source is finalized. It’s why I had to implement Lifetime. There are use cases where, despite having a proper garbage collector, the .Net token leaks space accumulating callbacks that TOCCancelToken would just discard.

Summary

In Objective-C, accidentally referencing an object in a block assigned to that object creates a reference cycle that can lead to a space leak.

The collapsing futures library makes all reference cycles involving a future or a cancel token (but not their source) dependent instead of self-sustaining.

When the source of a future or cancel token is deallocated, the token/future is marked as immortal. This discards all outgoing references, breaking any reference cycles that involved the token/future.

Discuss on Reddit

My Twitter: @CraigGidney

Comments are closed.

Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

Archive