Why am I getting deadlock with dispatch_once?

Question

Why am I deadlocking?

- (void)foo
{
    static dispatch_once_t onceToken;
    dispatch_once(&onceToken, ^{

        [self foo];

    });

    // whatever...
}

I expect foo to be executed twice on first call.

Answer 1

Neither of the existing answers are quite accurate (one is dead wrong, the other is a bit misleading and misses some critical details). First, let's go right to the source:

void
dispatch_once_f(dispatch_once_t *val, void *ctxt, dispatch_function_t func)
{
    struct _dispatch_once_waiter_s * volatile *vval =
            (struct _dispatch_once_waiter_s**)val;
    struct _dispatch_once_waiter_s dow = { NULL, 0 };
    struct _dispatch_once_waiter_s *tail, *tmp;
    _dispatch_thread_semaphore_t sema;

    if (dispatch_atomic_cmpxchg(vval, NULL, &dow)) {
        dispatch_atomic_acquire_barrier();
        _dispatch_client_callout(ctxt, func);

        dispatch_atomic_maximally_synchronizing_barrier();
        //dispatch_atomic_release_barrier(); // assumed contained in above
        tmp = dispatch_atomic_xchg(vval, DISPATCH_ONCE_DONE);
        tail = &dow;
        while (tail != tmp) {
            while (!tmp->dow_next) {
                _dispatch_hardware_pause();
            }
            sema = tmp->dow_sema;
            tmp = (struct _dispatch_once_waiter_s*)tmp->dow_next;
            _dispatch_thread_semaphore_signal(sema);
        }
    } else {
        dow.dow_sema = _dispatch_get_thread_semaphore();
        for (;;) {
            tmp = *vval;
            if (tmp == DISPATCH_ONCE_DONE) {
                break;
            }
            dispatch_atomic_store_barrier();
            if (dispatch_atomic_cmpxchg(vval, tmp, &dow)) {
                dow.dow_next = tmp;
                _dispatch_thread_semaphore_wait(dow.dow_sema);
            }
        }
        _dispatch_put_thread_semaphore(dow.dow_sema);
    }
}

So what really happens is, contrary to the other answers, the onceToken is changed from its initial state of NULL to point to an address on the stack of the first caller &dow (call this caller 1). This happens before the block is called. If more callers arrive before the block is completed, they get added to a linked list of waiters, the head of which is contained in onceToken until the block completes (call them callers 2..N). After being added to this list, callers 2..N wait on a semaphore for caller 1 to complete execution of the block, at which point caller 1 will walk the linked list signaling the semaphore once for each caller 2..N. At the beginning of that walk, onceToken is changed again to be DISPATCH_ONCE_DONE (which is conveniently defined to be a value that could never be a valid pointer, and therefore could never be the head of a linked list of blocked callers.) Changing it to DISPATCH_ONCE_DONE is what makes it cheap for subsequent callers (for the rest of the lifetime of the process) to check the completed state.

So in your case, what's happening is this:

• The first time you call -foo, onceToken is nil (which is guaranteed by virtue of statics being guaranteed to be initialized to 0), and gets atomically changed to become the head of the linked list of waiters.
• When you call -foo recursively from inside the block, your thread is considered to be "a second caller" and a waiter structure, which exists in this new, lower stack frame, is added to the list and then you go to wait on the semaphore.
• The problem here is that this semaphore will never be signaled because in order for it to be signaled, your block would have to finish executing (in the higher stack frame), which now can't happen due to a deadlock.

So, in short, yes, you're deadlocked, and the practical takeaway here is, "don't try to call recursively into a dispatch_once block." But the problem is most definitely NOT "infinite recursion", and the flag is most definitely not only changed after the block completes execution -- changing it before the block executes is exactly how it knows to make callers 2..N wait for caller 1 to finish.

Answer 2

You could alter code a little, so that the calls are outside the block and there's no deadlock, something like this:

- (void)foo
{
    static dispatch_once_t onceToken;
    BOOL shouldRunTwice = NO;
    dispatch_once(&onceToken, ^{
        shouldRunTwice = YES;
    });
    if (shouldRunTwice) {
        [self foo];
    }
    // whatever...
}