GCD Source Analysis 3 - dispatch_queue

Preface

Dispatch queues are the center of GCD. Understanding their structure makes the rest of libdispatch easier to follow, because many APIs eventually package work into continuations and push that work through a queue.

Queue Definition

dispatch_queue_s is the central queue structure:

1
2
3
4
5
struct dispatch_queue_s {
DISPATCH_STRUCT_HEADER(dispatch_queue_s, dispatch_queue_vtable_s);
DISPATCH_QUEUE_HEADER;
char dq_label[DISPATCH_QUEUE_MIN_LABEL_SIZE]; // must be last
};

The structure contains two macros and one dq_label.

DISPATCH_STRUCT_HEADER

1
2
3
4
5
6
7
8
9
#define DISPATCH_STRUCT_HEADER(x, y)        \
const struct y *do_vtable; \ // operation functions for this dispatch_object_s
struct x *volatile do_next; \ // linked-list next pointer
unsigned int do_ref_cnt; \ // reference count
unsigned int do_xref_cnt; \ // external reference count
unsigned int do_suspend_cnt; \ // suspend count, used as a pause flag
struct dispatch_queue_s *do_targetq;\ // target queue where this struct x runs
void *do_ctxt; \ // context, the parameter to pass through
void *do_finalizer

In GCD, many structure definitions call DISPATCH_STRUCT_HEADER, passing the structure name as the first macro parameter x. The second macro parameter y is usually dispatch_queue_vtable_s.

struct x *volatile do_next means that x only affects the pointer type of do_next, which can be understood as preparation for later linked-list operations. In the queue definition, it expands to:

1
struct dispatch_queue_s *volatile do_next;

The second parameter y only affects the pointer type of do_vtable. Here it expands to:

1
const struct dispatch_queue_vtable_s *do_vtable;

dispatch_queue_vtable_s contains operation functions for this dispatch_object_s or its subclasses. GCD also defines shorter macros for these operations to make invocation more convenient:

1
2
3
4
5
6
unsigned long const do_type;    \                           // concrete data type
const char *const do_kind; \ // type description string
size_t (*const do_debug)(struct x *, char *, size_t); \ // obtains debug information
struct dispatch_queue_s *(*const do_invoke)(struct x *);\ // wakes or invokes the queue; global and main queues use NULL
bool (*const do_probe)(struct x *); \ // checks whether some values in the object meet certain conditions
void (*const do_dispose)(struct x *) // disposes the queue, usually by calling the finalizer

DISPATCH_QUEUE_HEADER

1
2
3
4
5
6
7
8
#define DISPATCH_QUEUE_HEADER \
uint32_t dq_running; \
uint32_t dq_width; \
struct dispatch_object_s *dq_items_tail; \
struct dispatch_object_s *volatile dq_items_head; \
unsigned long dq_serialnum; \
void *dq_finalizer_ctxt; \
dispatch_queue_finalizer_function_t dq_finalizer_func

dq_label

dq_label is the queue name, whose maximum length cannot exceed DISPATCH_QUEUE_MIN_LABEL_SIZE = 64.

Getting Queues

There are several common ways to obtain GCD queues.

Main Queue: dispatch_get_main_queue

1
#define dispatch_get_main_queue() (&_dispatch_main_q)

dispatch_get_main_queue is actually a macro that returns the address of the structure _dispatch_main_q.

1
2
3
4
5
6
7
8
9
10
11
12
struct dispatch_queue_s _dispatch_main_q = {
.do_vtable = &_dispatch_queue_vtable,
.do_ref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_xref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_suspend_cnt = DISPATCH_OBJECT_SUSPEND_LOCK,
.do_targetq = &_dispatch_root_queues[DISPATCH_ROOT_QUEUE_COUNT / 2],

.dq_label = "com.apple.main-thread",
.dq_running = 1,
.dq_width = 1,
.dq_serialnum = 1,
};

do_vtable

The main queue’s function pointer do_vtable points to _dispatch_queue_vtable:

1
2
3
4
5
6
7
8
static const struct dispatch_queue_vtable_s _dispatch_queue_vtable = {
.do_type = DISPATCH_QUEUE_TYPE,
.do_kind = "queue",
.do_dispose = _dispatch_queue_dispose,
.do_invoke = (void *)dummy_function_r0,
.do_probe = (void *)dummy_function_r0,
.do_debug = dispatch_queue_debug,
};

do_ref_cnt and do_xref_cnt

These two values are related to memory management of GCD objects. A GCD object can be released only when both values become 0. In the main queue, both values are DISPATCH_OBJECT_GLOBAL_REFCNT:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define DISPATCH_OBJECT_GLOBAL_REFCNT   (~0u)

void _dispatch_retain(dispatch_object_t dou)
{
if (dou._do->do_ref_cnt == DISPATCH_OBJECT_GLOBAL_REFCNT) {
return; // global object
}
...
}

void dispatch_release(dispatch_object_t dou)
{
typeof(dou._do->do_xref_cnt) oldval;

if (dou._do->do_xref_cnt == DISPATCH_OBJECT_GLOBAL_REFCNT) {
return;
}
...

From _dispatch_retain and dispatch_release, we can see that the main queue lives with the application and is not affected by retain and release.

do_targetq

The target queue is important. Non-global queues, such as the manager queue, usually need to be pushed into a global queue for processing, so their target_queue must be specified.

1
#define DISPATCH_ROOT_QUEUE_COUNT 6
1
2
.do_targetq = &_dispatch_root_queues[DISPATCH_ROOT_QUEUE_COUNT / 2],
.do_targetq = &_dispatch_root_queues[3],

This points to the global queue named com.apple.root.default-overcommit-priority.

Manager Queue: _dispatch_mgr_q

Note: this queue is used internally by GCD and is not exposed publicly.

1
2
3
4
5
6
7
8
9
10
11
struct dispatch_queue_s _dispatch_mgr_q = {
.do_vtable = &_dispatch_queue_mgr_vtable,
.do_ref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_xref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_suspend_cnt = DISPATCH_OBJECT_SUSPEND_LOCK,
.do_targetq = &_dispatch_root_queues[DISPATCH_ROOT_QUEUE_COUNT - 1],

.dq_label = "com.apple.libdispatch-manager",
.dq_width = 1,
.dq_serialnum = 2,
};

do_vtable

The manager queue’s do_vtable points to _dispatch_queue_mgr_vtable:

1
2
3
4
5
6
7
static const struct dispatch_queue_vtable_s _dispatch_queue_mgr_vtable = {
.do_type = DISPATCH_QUEUE_MGR_TYPE,
.do_kind = "mgr-queue",
.do_invoke = _dispatch_mgr_invoke,
.do_debug = dispatch_queue_debug,
.do_probe = _dispatch_mgr_wakeup,
};

do_ref_cnt and do_xref_cnt

Refer to the main queue section.

do_targetq

It points to the global queue named com.apple.root.high-overcommit-priority.

Global Queue: dispatch_get_global_queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
enum {
DISPATCH_QUEUE_PRIORITY_HIGH = 2,
DISPATCH_QUEUE_PRIORITY_DEFAULT = 0,
DISPATCH_QUEUE_PRIORITY_LOW = -2,
};

dispatch_queue_t dispatch_get_global_queue(long priority, unsigned long flags)
{
if (flags & ~DISPATCH_QUEUE_OVERCOMMIT) {
return NULL;
}
return _dispatch_get_root_queue(priority, flags & DISPATCH_QUEUE_OVERCOMMIT);
}

static inline dispatch_queue_t _dispatch_get_root_queue(long priority, bool overcommit)
{
if (overcommit) switch (priority) {
case DISPATCH_QUEUE_PRIORITY_LOW:
return &_dispatch_root_queues[1];
case DISPATCH_QUEUE_PRIORITY_DEFAULT:
return &_dispatch_root_queues[3];
case DISPATCH_QUEUE_PRIORITY_HIGH:
return &_dispatch_root_queues[5];
}
switch (priority) {
case DISPATCH_QUEUE_PRIORITY_LOW:
return &_dispatch_root_queues[0];
case DISPATCH_QUEUE_PRIORITY_DEFAULT:
return &_dispatch_root_queues[2];
case DISPATCH_QUEUE_PRIORITY_HIGH:
return &_dispatch_root_queues[4];
default:
return NULL;
}
}

The libdispatch version analyzed here defines six global queues. Newer versions have eight global queues.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
static struct dispatch_queue_s _dispatch_root_queues[] = {
{
.do_vtable = &_dispatch_queue_root_vtable,
.do_ref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_xref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_suspend_cnt = DISPATCH_OBJECT_SUSPEND_LOCK,
.do_ctxt = &_dispatch_root_queue_contexts[0],

.dq_label = "com.apple.root.low-priority",
.dq_running = 2,
.dq_width = UINT32_MAX,
.dq_serialnum = 4,
},
{
.do_vtable = &_dispatch_queue_root_vtable,
.do_ref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_xref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_suspend_cnt = DISPATCH_OBJECT_SUSPEND_LOCK,
.do_ctxt = &_dispatch_root_queue_contexts[1],

.dq_label = "com.apple.root.low-overcommit-priority",
.dq_running = 2,
.dq_width = UINT32_MAX,
.dq_serialnum = 5,
},
{
.do_vtable = &_dispatch_queue_root_vtable,
.do_ref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_xref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_suspend_cnt = DISPATCH_OBJECT_SUSPEND_LOCK,
.do_ctxt = &_dispatch_root_queue_contexts[2],

.dq_label = "com.apple.root.default-priority",
.dq_running = 2,
.dq_width = UINT32_MAX,
.dq_serialnum = 6,
},
{
.do_vtable = &_dispatch_queue_root_vtable,
.do_ref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_xref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_suspend_cnt = DISPATCH_OBJECT_SUSPEND_LOCK,
.do_ctxt = &_dispatch_root_queue_contexts[3],

.dq_label = "com.apple.root.default-overcommit-priority",
.dq_running = 2,
.dq_width = UINT32_MAX,
.dq_serialnum = 7,
},
{
.do_vtable = &_dispatch_queue_root_vtable,
.do_ref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_xref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_suspend_cnt = DISPATCH_OBJECT_SUSPEND_LOCK,
.do_ctxt = &_dispatch_root_queue_contexts[4],

.dq_label = "com.apple.root.high-priority",
.dq_running = 2,
.dq_width = UINT32_MAX,
.dq_serialnum = 8,
},
{
.do_vtable = &_dispatch_queue_root_vtable,
.do_ref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_xref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_suspend_cnt = DISPATCH_OBJECT_SUSPEND_LOCK,
.do_ctxt = &_dispatch_root_queue_contexts[5],

.dq_label = "com.apple.root.high-overcommit-priority",
.dq_running = 2,
.dq_width = UINT32_MAX,
.dq_serialnum = 9,
},
};

do_vtable

The global queue’s function pointer do_vtable points to _dispatch_queue_root_vtable:

1
2
3
4
5
6
static const struct dispatch_queue_vtable_s _dispatch_queue_root_vtable = {
.do_type = DISPATCH_QUEUE_GLOBAL_TYPE,
.do_kind = "global-queue",
.do_debug = dispatch_queue_debug,
.do_probe = _dispatch_queue_wakeup_global,
};

do_ref_cnt and do_xref_cnt

Refer to the main queue section.

do_ctxt

Notice that the global queue has a do_ctxt. This is the context, the parameter we want to pass through.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define MAX_THREAD_COUNT 255

static struct dispatch_root_queue_context_s _dispatch_root_queue_contexts[] = {
{
.dgq_thread_mediator = &_dispatch_thread_mediator[0],
.dgq_thread_pool_size = MAX_THREAD_COUNT,
},
{
.dgq_thread_mediator = &_dispatch_thread_mediator[1],
.dgq_thread_pool_size = MAX_THREAD_COUNT,
},
{
.dgq_thread_mediator = &_dispatch_thread_mediator[2],
.dgq_thread_pool_size = MAX_THREAD_COUNT,
},
{
.dgq_thread_mediator = &_dispatch_thread_mediator[3],
.dgq_thread_pool_size = MAX_THREAD_COUNT,
},
{
.dgq_thread_mediator = &_dispatch_thread_mediator[4],
.dgq_thread_pool_size = MAX_THREAD_COUNT,
},
{
.dgq_thread_mediator = &_dispatch_thread_mediator[5],
.dgq_thread_pool_size = MAX_THREAD_COUNT,
},
};

_dispatch_thread_mediator is defined as follows:

1
2
3
4
5
6
7
8
9
10
11
12
static struct dispatch_semaphore_s _dispatch_thread_mediator[] = {
{
.do_vtable = &_dispatch_semaphore_vtable,
.do_ref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_xref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
},
{
.do_vtable = &_dispatch_semaphore_vtable,
.do_ref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
.do_xref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT,
},
};

The original source contains six entries with the same shape; the key idea is that each root queue context owns a mediator semaphore and a thread-pool size.

Custom Queues

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
dispatch_queue_t dispatch_queue_create(const char *label, dispatch_queue_attr_t attr)
{
dispatch_queue_t dq;
size_t label_len;

if (!label) {
label = "";
}

label_len = strlen(label);
if (label_len < (DISPATCH_QUEUE_MIN_LABEL_SIZE - 1)) {
label_len = (DISPATCH_QUEUE_MIN_LABEL_SIZE - 1);
}

dq = calloc(1ul, sizeof(struct dispatch_queue_s) - DISPATCH_QUEUE_MIN_LABEL_SIZE + label_len + 1);
if (slowpath(!dq)) {
return dq;
}
_dispatch_queue_init(dq);

strcpy(dq->dq_label, label);

#ifndef DISPATCH_NO_LEGACY
if (slowpath(attr)) {
dq->do_targetq = _dispatch_get_root_queue(attr->qa_priority, attr->qa_flags & DISPATCH_QUEUE_OVERCOMMIT);

dq->dq_finalizer_ctxt = attr->finalizer_ctxt;
dq->dq_finalizer_func = attr->finalizer_func;

#ifdef __BLOCKS__
if (attr->finalizer_func == (void*)_dispatch_call_block_and_release2) {
dq->dq_finalizer_ctxt = Block_copy(dq->dq_finalizer_ctxt);
if (!(dq->dq_finalizer_ctxt)) {
goto out_bad;
}
}
#endif
}
#endif

return dq;

out_bad:
free(dq);
return NULL;
}

_dispatch_queue_init

Now look at the inline function _dispatch_queue_init:

1
2
3
4
5
6
7
8
9
10
11
inline void _dispatch_queue_init(dispatch_queue_t dq)
{
dq->do_vtable = &_dispatch_queue_vtable;
dq->do_next = DISPATCH_OBJECT_LISTLESS;
dq->do_ref_cnt = 1;
dq->do_xref_cnt = 1;
dq->do_targetq = _dispatch_get_root_queue(0, true);
dq->dq_running = 0;
dq->dq_width = 1;
dq->dq_serialnum = dispatch_atomic_inc(&_dispatch_queue_serial_numbers) - 1;
}

From the previous code, global queues all have dq_width equal to UINT32_MAX, while _dispatch_queue_init sets dq_width to 1. This means a custom queue defaults to a serial queue.

Also, dq->do_targetq = _dispatch_get_root_queue(0, true) involves an important GCD queue/block model: the target queue. Blocks submitted to any queue are eventually placed on its target queue for execution. For a normal serial queue, the target queue is an overcommit-capable global queue, and the global queue is backed by a thread pool.

Borrowing a classic Apple diagram:

GCD Source Analysis 3 - dispatch_queue: _dispatch_queue_init (figure 1)

Other fields can mostly be understood from the previous sections. Here, focus on dq_serialnum:

1
static unsigned long _dispatch_queue_serial_numbers = 10;
1
2
3
4
5
// skip zero
// 1 - main_q
// 2 - mgr_q
// 3 - _unused_
// 4,5,6,7,8,9 - global queues

Zero is skipped, 3 is unused, 1 is used by the main queue, 2 by the manager queue, and 4 to 9 by global queues. Custom queues start from 10. Each time a custom queue is created, _dispatch_queue_serial_numbers is updated atomically and then decremented by 1, which guarantees that every custom queue has a unique dq_serialnum.

Special Handling of dispatch_queue_attr_t

If an attr parameter is passed while creating a custom queue, it indicates overcommit support. An overcommit queue means that whenever a task is submitted, the system opens a new thread to handle it, avoiding overload on a single thread.

Also, if finalizer_func == _dispatch_call_block_and_release2, dq_finalizer_ctxt needs to be retained.

1
2
3
4
5
6
void _dispatch_call_block_and_release2(void *block, void *ctxt)
{
void (^b)(void*) = block;
b(ctxt);
Block_release(b);
}

Common API Analysis

dispatch_async

1
2
3
4
void dispatch_async(dispatch_queue_t dq, void (^work)(void))
{
dispatch_async_f(dq, _dispatch_Block_copy(work), _dispatch_call_block_and_release);
}

dispatch_async mainly prepares its parameters and then calls dispatch_async_f.

    1. _dispatch_Block_copy creates a copy of the incoming block on the heap, or increases its reference count, ensuring that the block is not destroyed before execution.
    1. _dispatch_call_block_and_release, as the name suggests, calls the block and then releases it.
1
2
3
4
5
6
void _dispatch_call_block_and_release(void *block)
{
void (^b)(void) = block;
b();
Block_release(b);
}

dispatch_async_f

Now analyze dispatch_async_f:

1
2
3
4
5
6
7
8
9
10
11
void dispatch_async_f(dispatch_queue_t dq, void *ctxt, dispatch_function_t func)
{
dispatch_continuation_t dc = fastpath(_dispatch_continuation_alloc_cacheonly());
if (!dc) {
return _dispatch_async_f_slow(dq, ctxt, func);
}
dc->do_vtable = (void *)DISPATCH_OBJ_ASYNC_BIT;
dc->dc_func = func;
dc->dc_ctxt = ctxt;
_dispatch_queue_push(dq, dc);
}
    1. First look at _dispatch_continuation_alloc_cacheonly. Its purpose is to fetch a dispatch_continuation_t structure from the thread’s TLS, or thread-local storage. Each thread has its own private storage, and that storage is not used by other threads.
1
2
3
4
5
6
7
8
static inline dispatch_continuation_t _dispatch_continuation_alloc_cacheonly(void)
{
dispatch_continuation_t dc = fastpath(_dispatch_thread_getspecific(dispatch_cache_key));
if (dc) {
_dispatch_thread_setspecific(dispatch_cache_key, dc->do_next);
}
return dc;
}
    1. If the current thread’s TLS does not contain a dispatch_continuation_t, _dispatch_async_f_slow() is used.
    1. If dc is not empty, set its do_vtable to DISPATCH_OBJ_ASYNC_BIT, mainly for type distinction. Store the incoming block in dc_ctxt as context, set dc_func to _dispatch_call_block_and_release, and finally call _dispatch_queue_push to enqueue it.

DISPATCH_OBJ_ASYNC_BIT is a macro used to distinguish async, group, and barrier:

1
2
3
#define DISPATCH_OBJ_ASYNC_BIT      0x1
#define DISPATCH_OBJ_BARRIER_BIT 0x2
#define DISPATCH_OBJ_GROUP_BIT 0x4

Continue into _dispatch_async_f_slow:

1
2
3
4
5
6
7
8
9
10
DISPATCH_NOINLINE static void _dispatch_async_f_slow(dispatch_queue_t dq, void *context, dispatch_function_t func)
{
dispatch_continuation_t dc = fastpath(_dispatch_continuation_alloc_from_heap());

dc->do_vtable = (void *)DISPATCH_OBJ_ASYNC_BIT;
dc->dc_func = func;
dc->dc_ctxt = context;

_dispatch_queue_push(dq, dc);
}
1
2
3
4
5
6
7
8
9
10
11
dispatch_continuation_t _dispatch_continuation_alloc_from_heap(void)
{
static dispatch_once_t pred;
dispatch_continuation_t dc;
dispatch_once_f(&pred, NULL, _dispatch_ccache_init);

while (!(dc = fastpath(malloc_zone_calloc(_dispatch_ccache_zone, 1, ROUND_UP_TO_CACHELINE_SIZE(sizeof(*dc)))))) {
sleep(1);
}
return dc;
}

After obtaining a dispatch_continuation_t from the heap, it sets the same fields as above and then enters _dispatch_queue_push.

_dispatch_queue_push

1
#define _dispatch_queue_push(x, y) _dispatch_queue_push_list((x), (y), (y))

_dispatch_queue_push is a macro. It actually calls _dispatch_queue_push_list.

_dispatch_queue_push_list

1
2
3
4
5
6
7
8
9
10
11
12
static inline void
_dispatch_queue_push_list(dispatch_queue_t dq, dispatch_object_t _head, dispatch_object_t _tail)
{
struct dispatch_object_s *prev, *head = _head._do, *tail = _tail._do;
tail->do_next = NULL;
prev = fastpath(dispatch_atomic_xchg(&dq->dq_items_tail, tail));
if (prev) {
prev->do_next = head;
} else {
_dispatch_queue_push_list_slow(dq, head);
}
}

_dispatch_queue_push_list is an inline function, which suggests it is called very frequently. Inline functions are common in kernel-style code and are efficient, though they can increase binary size: a classic space-for-time tradeoff.

    1. If the queue is not empty, place dc at the tail and redirect dq->dq_items_tail. Since there are already tasks before it, inserting at the tail is enough.

Why is this a redirection? According to the definition of dispatch_atomic_xchg, it “sets *p to n and returns the previous value of *p”. Therefore, dispatch_atomic_xchg(&dq->dq_items_tail, tail) is equivalent to setting dq->dq_items_tail = tail, while prev is the old tail element and prev->do_next = head links the new node at the end.

    1. If the queue is empty, call _dispatch_queue_push_list_slow:
1
2
3
4
5
6
7
void _dispatch_queue_push_list_slow(dispatch_queue_t dq, struct dispatch_object_s *obj)
{
_dispatch_retain(dq);
dq->dq_items_head = obj;
_dispatch_wakeup(dq);
_dispatch_release(dq);
}

_dispatch_queue_push_list_slow sets dq->dq_items_head to dc, then calls _dispatch_wakeup to wake the queue. It calls _dispatch_wakeup because the queue is empty, no task is running, and the queue is sleeping.

_dispatch_wakeup

Now analyze how a queue is woken up. Here dou refers to a queue:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
dispatch_queue_t _dispatch_wakeup(dispatch_object_t dou)
{
dispatch_queue_t tq;

if (slowpath(DISPATCH_OBJECT_SUSPENDED(dou._do))) {
return NULL;
}

if (!dx_probe(dou._do) && !dou._dq->dq_items_tail) {
return NULL;
}

if (!_dispatch_trylock(dou._do)) {
#if DISPATCH_COCOA_COMPAT
if (dou._dq == &_dispatch_main_q) {
_dispatch_queue_wakeup_main();
}
#endif
return NULL;
}

_dispatch_retain(dou._do);
tq = dou._do->do_targetq;
_dispatch_queue_push(tq, dou._do);
return tq;
}
    1. If it is the main queue, call _dispatch_queue_wakeup_main directly.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void _dispatch_queue_wakeup_main(void)
{
kern_return_t kr;

dispatch_once_f(&_dispatch_main_q_port_pred, NULL, _dispatch_main_q_port_init);

kr = _dispatch_send_wakeup_main_thread(main_q_port, 0);

switch (kr) {
case MACH_SEND_TIMEOUT:
case MACH_SEND_TIMED_OUT:
case MACH_SEND_INVALID_DEST:
break;
default:
dispatch_assume_zero(kr);
break;
}

_dispatch_safe_fork = false;
}

The core logic that wakes the main thread is inside _dispatch_send_wakeup_main_thread, but unfortunately that part is not open source.

    1. If it is a global queue, execution enters _dispatch_queue_wakeup_global, the function pointed to by the global queue’s dx_probe. Here we truly encounter pthread:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
bool _dispatch_queue_wakeup_global(dispatch_queue_t dq)
{
static dispatch_once_t pred;
struct dispatch_root_queue_context_s *qc = dq->do_ctxt;
pthread_workitem_handle_t wh;
unsigned int gen_cnt;
pthread_t pthr;
int r, t_count;

if (!dq->dq_items_tail) {
return false;
}

_dispatch_safe_fork = false;
dispatch_debug_queue(dq, __PRETTY_FUNCTION__);

dispatch_once_f(&pred, NULL, _dispatch_root_queues_init);

if (qc->dgq_kworkqueue) {
if (dispatch_atomic_cmpxchg(&qc->dgq_pending, 0, 1)) {
_dispatch_debug("requesting new worker thread");

r = pthread_workqueue_additem_np(qc->dgq_kworkqueue, _dispatch_worker_thread2, dq, &wh, &gen_cnt);
dispatch_assume_zero(r);
} else {
_dispatch_debug("work thread request still pending on global queue: %p", dq);
}
goto out;
}

if (dispatch_semaphore_signal(qc->dgq_thread_mediator)) {
goto out;
}

do {
t_count = qc->dgq_thread_pool_size;
if (!t_count) {
_dispatch_debug("The thread pool is full: %p", dq);
goto out;
}
} while (!dispatch_atomic_cmpxchg(&qc->dgq_thread_pool_size, t_count, t_count - 1));

while ((r = pthread_create(&pthr, NULL, _dispatch_worker_thread, dq))) {
if (r != EAGAIN) {
dispatch_assume_zero(r);
}
sleep(1);
}

r = pthread_detach(pthr);
dispatch_assume_zero(r);

out:
return false;
}

There are two main paths:

    1. If dgq_kworkqueue exists in the queue context, call pthread_workqueue_additem_np. This function uses the workq_kernreturn system call to notify the workqueue that a new item should be executed. Based on this notification, the XNU kernel decides whether to create a thread according to system state. For an overcommit priority queue, workqueue always creates a thread, and that thread later executes _dispatch_worker_thread2.
    1. If dgq_kworkqueue does not exist, call pthread_create to start a thread directly. The thread entry is _dispatch_worker_thread, but that function still calls _dispatch_worker_thread2, so both paths eventually converge.

_dispatch_worker_thread

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void *_dispatch_worker_thread(void *context)
{
dispatch_queue_t dq = context;
struct dispatch_root_queue_context_s *qc = dq->do_ctxt;
sigset_t mask;
int r;

r = sigfillset(&mask);
dispatch_assume_zero(r);
r = _dispatch_pthread_sigmask(SIG_BLOCK, &mask, NULL);
dispatch_assume_zero(r);

do {
_dispatch_worker_thread2(context);
} while (dispatch_semaphore_wait(qc->dgq_thread_mediator, dispatch_time(0, 65ull * NSEC_PER_SEC)) == 0);

dispatch_atomic_inc(&qc->dgq_thread_pool_size);
if (dq->dq_items_tail) {
_dispatch_queue_wakeup_global(dq);
}

return NULL;
}

The first part mainly sets the signal mask of the new thread. Real task scheduling happens in _dispatch_worker_thread2.

After task scheduling ends, this thread waits on a semaphore. The semaphore it waits on is the same one used in dispatch_queue_wakeup_global. Why do this? To avoid creating new threads too frequently. If a newly created thread has finished all tasks, it does not immediately exit. Instead, it waits on a semaphore for about 65 seconds. If a new signal arrives within 65 seconds, meaning a new task has arrived, the thread continues executing that task instead of creating another thread. If no signal arrives after 65 seconds, the thread exits and is destroyed.

_dispatch_worker_thread2

The two paths mentioned earlier eventually call _dispatch_worker_thread2, so the core execution logic is here and deserves special attention:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void _dispatch_worker_thread2(void *context)
{
struct dispatch_object_s *item;
dispatch_queue_t dq = context;
struct dispatch_root_queue_context_s *qc = dq->do_ctxt;

if (_dispatch_thread_getspecific(dispatch_queue_key)) {
DISPATCH_CRASH("Premature thread recycling");
}

_dispatch_thread_setspecific(dispatch_queue_key, dq);
qc->dgq_pending = 0;

while ((item = fastpath(_dispatch_queue_concurrent_drain_one(dq)))) {
_dispatch_continuation_pop(item);
}

_dispatch_thread_setspecific(dispatch_queue_key, NULL);

_dispatch_force_cache_cleanup();
}

This function schedules tasks. Two functions are important:

    1. _dispatch_queue_concurrent_drain_one, which takes one item from the queue.
    1. _dispatch_continuation_pop, which processes the item taken from the queue.

_dispatch_queue_concurrent_drain_one

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct dispatch_object_s *
_dispatch_queue_concurrent_drain_one(dispatch_queue_t dq)
{
struct dispatch_object_s *head, *next, *const mediator = (void *)~0ul;

// The mediator value acts both as a "lock" and a signal
head = dispatch_atomic_xchg(&dq->dq_items_head, mediator);

if (slowpath(head == NULL)) {
dispatch_atomic_cmpxchg(&dq->dq_items_head, mediator, NULL);
_dispatch_debug("no work on global work queue");
return NULL;
}

if (slowpath(head == mediator)) {
_dispatch_queue_wakeup_global(dq);
return NULL;
}

next = fastpath(head->do_next);

if (slowpath(!next)) {
dq->dq_items_head = NULL;

if (dispatch_atomic_cmpxchg(&dq->dq_items_tail, head, NULL)) {
goto out;
}

while (!(next = head->do_next)) {
_dispatch_hardware_pause();
}
}

dq->dq_items_head = next;
_dispatch_queue_wakeup_global(dq);
out:
return head;
}

mediator is used as both a lock and a signal. If the queue is empty, it returns NULL. If the current thread loses ownership of the queue during competition, it wakes the global queue and returns. Otherwise, it takes the head item, moves the queue head forward, and returns the old head.

_dispatch_continuation_pop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
static inline void _dispatch_continuation_pop(dispatch_object_t dou)
{
dispatch_continuation_t dc = dou._dc;
dispatch_group_t dg;

if (DISPATCH_OBJ_IS_VTABLE(dou._do)) {
return _dispatch_queue_invoke(dou._dq);
}

if ((long)dou._do->do_vtable & DISPATCH_OBJ_ASYNC_BIT) {
_dispatch_continuation_free(dc);
}

if ((long)dou._do->do_vtable & DISPATCH_OBJ_GROUP_BIT) {
dg = dc->dc_group;
} else {
dg = NULL;
}

dc->dc_func(dc->dc_ctxt);

if (dg) {
dispatch_group_leave(dg);
_dispatch_release(dg);
}
}

From this function, we can see that what is pushed into a queue is not only continuation tasks, but may also be another queue. If it is a queue, _dispatch_queue_invoke is executed directly. Otherwise, it executes dc->dc_func(dc->dc_ctxt).

Next, analyze _dispatch_queue_invoke, which explains how a popped queue is executed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
DISPATCH_NOINLINE void _dispatch_queue_invoke(dispatch_queue_t dq)
{
dispatch_queue_t tq = dq->do_targetq;

if (!slowpath(DISPATCH_OBJECT_SUSPENDED(dq)) && fastpath(_dispatch_queue_trylock(dq))) {
_dispatch_queue_drain(dq);
if (tq == dq->do_targetq) {
tq = dx_invoke(dq);
} else {
tq = dq->do_targetq;
}

dispatch_atomic_dec(&dq->dq_running);

if (tq) {
return _dispatch_queue_push(tq, dq);
}
}

dq->do_next = DISPATCH_OBJECT_LISTLESS;
if (dispatch_atomic_sub(&dq->do_suspend_cnt, DISPATCH_OBJECT_SUSPEND_LOCK) == 0) {
if (dq->dq_running == 0) {
_dispatch_wakeup(dq);
}
}

_dispatch_release(dq);
}

If execution is triggered directly through dx_invoke, it returns NULL.

Flow Summary

The implementation of dispatch_async is relatively complex because it involves many data structures and several branches. But the core idea is simple: store all submitted blocks in a linked list, then in the lower-level thread pool, take blocks out one by one and execute them. The function-call flow is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
dispatch_async
└──_dispatch_async_f_slow
└──_dispatch_queue_push
└──_dispatch_queue_push_list
└──_dispatch_queue_push_list_slow
└──_dispatch_wakeup
└──_dispatch_queue_wakeup_main
└──_dispatch_send_wakeup_main_thread
└──_dispatch_queue_wakeup_global
└──pthread_workqueue_additem_np
└──_dispatch_worker_thread2
└──pthread_create
└──_dispatch_worker_thread
└──_dispatch_worker_thread2
└──_dispatch_queue_concurrent_drain_one
└──_dispatch_continuation_pop
└──_dispatch_queue_invoke(queue)
└──dc->dc_func(dc->dc_ctxt)(continuation)

dispatch_sync

After dispatch_async, look at dispatch_sync.

1
2
3
4
5
6
7
8
9
10
void dispatch_sync(dispatch_queue_t dq, void (^work)(void))
{
#if DISPATCH_COCOA_COMPAT
if (slowpath(dq == &_dispatch_main_q)) {
return _dispatch_sync_slow(dq, work);
}
#endif
struct Block_basic *bb = (void *)work;
dispatch_sync_f(dq, work, (dispatch_function_t)bb->Block_invoke);
}
    1. If it is the main queue, call _dispatch_sync_slow. This method eventually calls dispatch_sync_f.
1
2
3
4
5
static void _dispatch_sync_slow(dispatch_queue_t dq, void (^work)(void))
{
struct Block_basic *bb = (void *)work;
dispatch_sync_f(dq, work, (dispatch_function_t)bb->Block_invoke);
}
    1. Otherwise, call dispatch_sync_f:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void dispatch_sync_f(dispatch_queue_t dq, void *ctxt, dispatch_function_t func)
{
typeof(dq->dq_running) prev_cnt;
dispatch_queue_t old_dq;

if (dq->dq_width == 1) {
return dispatch_barrier_sync_f(dq, ctxt, func);
}

if (slowpath(dq->dq_items_tail) || slowpath(DISPATCH_OBJECT_SUSPENDED(dq))){
_dispatch_sync_f_slow(dq);
}
else{
prev_cnt = dispatch_atomic_add(&dq->dq_running, 2) - 2;

if (slowpath(prev_cnt & 1)) {

if (dispatch_atomic_sub(&dq->dq_running, 2) == 0) {
_dispatch_wakeup(dq);
}
_dispatch_sync_f_slow(dq);
}
}

old_dq = _dispatch_thread_getspecific(dispatch_queue_key);
_dispatch_thread_setspecific(dispatch_queue_key, dq);
func(ctxt);
_dispatch_workitem_inc();
_dispatch_thread_setspecific(dispatch_queue_key, old_dq);

if (slowpath(dispatch_atomic_sub(&dq->dq_running, 2) == 0)) {
_dispatch_wakeup(dq);
}
}
    1. If a synchronous task is pushed into a serial queue, dispatch_barrier_sync_f is called:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dispatch_barrier_sync_f(dispatch_queue_t dq, void *ctxt, dispatch_function_t func)
{
dispatch_queue_t old_dq = _dispatch_thread_getspecific(dispatch_queue_key);

if (slowpath(dq->dq_items_tail)
|| slowpath(DISPATCH_OBJECT_SUSPENDED(dq))
|| slowpath(!_dispatch_queue_trylock(dq))) {
return _dispatch_barrier_sync_f_slow(dq, ctxt, func);
}

_dispatch_thread_setspecific(dispatch_queue_key, dq);
func(ctxt);
_dispatch_workitem_inc();
_dispatch_thread_setspecific(dispatch_queue_key, old_dq);
_dispatch_queue_unlock(dq);
}

The core logic sets the current thread’s dispatch_queue_key to dq, executes the block, and then restores the previous old_dq.

    1. If a synchronous task is pushed into a concurrent queue, and the queue is not empty, suspended, or already has running tasks, _dispatch_sync_f_slow is called to wait with a semaphore. Otherwise, _dispatch_wakeup is called directly to wake the queue and execute the task.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static void _dispatch_sync_f_slow(dispatch_queue_t dq)
{
// the global root queues do not need strict ordering
if (dq->do_targetq == NULL) {
dispatch_atomic_add(&dq->dq_running, 2);
return;
}

struct dispatch_sync_slow_s {
DISPATCH_CONTINUATION_HEADER(dispatch_sync_slow_s);
} dss = {
.do_vtable = NULL,
.dc_func = _dispatch_sync_f_slow2,
.dc_ctxt = _dispatch_get_thread_semaphore(),
};

_dispatch_queue_push(dq, (void *)&dss);

dispatch_semaphore_wait(dss.dc_ctxt, DISPATCH_TIME_FOREVER);
_dispatch_put_thread_semaphore(dss.dc_ctxt);
}

Flow Summary

The synchronous implementation of dispatch_sync is simpler by comparison. It only needs to push the task into the corresponding queue and use a semaphore to wait. The call stack is:

1
2
3
4
5
dispatch_sync
└──_dispatch_sync_slow
└──dispatch_sync_f
└──dispatch_barrier_sync_f(synchronous task pushed into a serial queue)
└──_dispatch_sync_f_slow(synchronous task pushed into a concurrent queue)

Summary

Queues contain a lot of material and are relatively complex. Because my own ability is limited, some parts may be imperfectly understood or not explained clearly enough. Corrections and comments are welcome.

-------------本文结束 感谢您的阅读-------------
If this article helped you, your support encourages me to keep writing.

Title:GCD Source Analysis 3 - dispatch_queue

Author:lingyun

Published:2018-02-03 00:35

Updated:2026-09-23 00:37

Original link:https://tsuijunxi.github.io/en/2018/02/03/gcd-source-analysis-3-dispatch-queue/

License: Attribution-NonCommercial-NoDerivatives 4.0 International Please keep the original link and author when sharing.