A Curious Case of Deadlock

Some knowledge of Swift and thread synchronization is required ahead.

Normally, on this blog, I write about games and game development. However, most of my time is spent on working on something else entirely; by day, I’m an iOS app developer at a big company you’ve probably heard of.

Recently, our team ran into a really interesting deadlock. I was working on writing a threadsafe cache implementation - a cache only one thread can read from, or write to, at a time. Seems like by-the-book multithreading. Except… well, it wasn’t, of course.

The Code

I wasn’t really sure which locking construct to use, at first. Apparently Swift has no language-supported implementation of thread synchronization. I did a bit of research and came to the conclusion that I’d use objc_sync_enter - if it’s good enough for Objective-C, it’s good enough for Swift, right?

The code I ended up with looked something like this:

class ThreadsafeCache
{
    private var dict: [String: CachedObject]

    init()
    {
        dict = UnarchiveCache() ?? [String: CachedObject]()
    }

    func read(key: String) -> Object?
    {
        objc_sync_enter(dict)
        defer { objc_sync_exit(dict) }
        return dict[key]
    }

    func write(key: String, value: Object)
    {
        objc_sync_enter(dict)
        defer { objc_sync_exit(dict) }
        dict[key] = value
    }

    func UnarchiveCache() -> [String: CachedObject]?
    {
        // Some unarchiving code goes here...
        if (unarchivedSuccessfully)
        {
            return dict
        }
        else
        {
            return nil
        }
    }
}

objc_sync_enter associates a lock with an object, and then holds that lock. If thread A calls objc_sync_enter, then thread B calls objc_sync_enter on the same object, thread B blocks until Thread A calls objc_sync_exit.

Well, that’s what should happen. But that’s not what was happening.

The Symptom

The first time read() or write() was called, objc_sync_enter would simply deadlock.

The first time this happened, I looked at my screen in disbelief. Surely there was a rational explanation for this. I set breakpoints on both to make sure neither method was getting called before the other. For sure, the very first time either was called, the code would deadlock.

I call my coworker over. “Any idea what’s going on here?”

He shrugged. “I used basically this same code elsewhere to synchronize a dictionary and it seems to work fine.”

We stepped through his code which synchronizes a dictionary in a similar way. No deadlock.

“Maybe it’s device specific?”

We gave it a try on his development iPad, and - of course - the issue does not reproduce. I then tried it on the simulator, and again, it doesn’t repro. But it was still reproducing on my dev iPhone.

By this time, I am gnashing my teeth in frustration.

The Debugging

I was determined to get to the bottom of this. There was literally no way anyone was locking on the same instance of dict:

• Only one instance of ThreadsafeCache is ever created in the program (as a private static let in a different class).
• dict is private, so no one else can access it.

With that knowledge, I knew it had to be something the system was doing. I did a quick google search to see if anyone had already debugged through objc_sync_enter, and found this post. Inside, it basically says that objc_sync_enter associates a lock with your object by hashing the object’s memory address.

Well, that got me thinking - what actually is the memory address of the object we’re passing to objc_sync_enter? The language hides all those details from you, and it’s surprisingly hard to tease it out. The first thing I tried was to set a symbolic breakpoint on objc_sync_enter in Xcode, ran the code, and got this:

Not very useful, unless you’re fluent in ARMv8 assembly (which I am not). Well, if we’re nearly at the lowest level we can get, surely, there’s a way to grab the pointer value of what we pass into objc_sync_enter.

At first, I tried to follow this guide from the apple developer website. However, neither the x86 version nor the ARM version seemed to work.

So, dredging up memories of stack pointers and registers from college, I start looking into ARM calling conventions. It turns out that parameters to a function are passed in registers x0 through x7 in ARMv8, which is the first version of ARM to support 64-bit registers. (My suspicion is that the above Apple guide was written before ARMv8 existed.)

Conveniently, there is a command in lldb just for reading registers: register read. So I fire up that breakpoint again, run register read, and here’s what I get:

So, if you recall, register x0 is supposed to hold the first argument to the function. But, hey, what’s _swiftEmptyDictionaryStorage? That’s not my dictionary…

Well, what gets passed on objc_sync_exit?

Oh.

ooooooh

The Cause

_swiftEmptyDictionaryStorage is not explicitly documented anywhere, but we can infer a lot from just the name and what we get from googling it. This appears to be an optimization in the Swift language.

When you create an empty dictionary, no dictionary actually gets allocated - instead, this singleton, _swiftEmptyDictionaryStorage, is assigned. Only when you attempt to insert a value into the dictionary is any actual memory allocated and assigned. In essence, the dictionary is lazily initialized.

Remember when I said my coworker’s code was working fine? His code is actually the cause of my deadlock. Here’s what was happening. His code, which runs before mine, does this:

var dict = [String: Any]()  // dict is assigned _swiftEmptyDictionaryStorage

objc_sync_enter(dict)       // _swiftEmptyDictionaryStorage is now locked
dict[key] = value           // A new dictionary is actually allocated here
objc_sync_exit(dict)        // This no-ops because we the new dict is not locked

Notice that the lock on _swiftEmptyDictionaryStorage remains. Now, when my own code runs, I attempt to take a lock on my empty dictionary, which points to _swiftEmptyDictionaryStorage. Since it’s already locked, and no one is ever going to release that lock - bam - deadlock.

One last thing - why wasn’t it reproducible sometimes? Take another look at the ThreadsafeCache code. If unarchiveCache() succeeded in init, a real dictionary with values would be allocated before any lock was taken, causing everything to behave correctly. Well, except that the _swiftEmptyDictionaryStorage lock would still remain, waiting to ensnare another naive developer.

In Closing

In most StackOverflow posts, people will recommend using either a DispatchQueue or objc_sync_enter/objc_sync_exit to do synchronization in Swift. In lieu of proper language support, I guess that’s the best we can get.

For my part, I’m going to start avoiding objc_sync_enter like the plague. It’s true that, in this case, I could just pass self instead of dict and probably get reasonable results (i.e. not a deadlock). But it seems like tying your code to a function which relies on implementation details of the language itself is an unwise choice at best.

I’ve read Cocoa With Love’s excellent post on the subject of synchronization in Swift, which recommends against the use of DispatchQueue for performance reasons. In fact, it’s the reason I went with objc_sync_enter in the first place. His recommend solution is somewhat in-depth, and I’m not going to cover all of it here. My basic gripe with it is that I think it’s not reusable enough. Perhaps if my application were performance-critical in some way, but it’s not, so I can’t justify the cost.

Thus, I think I’m going to go with DispatchQueue for my synchronization needs in the future. It seems to be better enough than the alternatives.

As a closing thought - massive, massive props to whoever put that feature in lldb which prints out the description of the values contained within the registers. Without that, I’d have had no idea that we were passing something named _swiftEmptyDictionaryStorage. Debugger developers are the unsung heroes of our generation.