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 | struct dispatch_queue_s { |
The structure contains two macros and one dq_label.
DISPATCH_STRUCT_HEADER
1 |
|
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 | unsigned long const do_type; \ // concrete data type |
DISPATCH_QUEUE_HEADER
1 |
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 |
dispatch_get_main_queue is actually a macro that returns
the address of the structure _dispatch_main_q.
1 | struct dispatch_queue_s _dispatch_main_q = { |
do_vtable
The main queue’s function pointer do_vtable points to
_dispatch_queue_vtable:
1 | static const struct dispatch_queue_vtable_s _dispatch_queue_vtable = { |
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 |
|
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 |
1 | .do_targetq = &_dispatch_root_queues[DISPATCH_ROOT_QUEUE_COUNT / 2], |
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 | struct dispatch_queue_s _dispatch_mgr_q = { |
do_vtable
The manager queue’s do_vtable points to
_dispatch_queue_mgr_vtable:
1 | static const struct dispatch_queue_vtable_s _dispatch_queue_mgr_vtable = { |
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 | enum { |
The libdispatch version analyzed here defines six global queues. Newer versions have eight global queues.
1 | static struct dispatch_queue_s _dispatch_root_queues[] = { |
do_vtable
The global queue’s function pointer do_vtable points to
_dispatch_queue_root_vtable:
1 | static const struct dispatch_queue_vtable_s _dispatch_queue_root_vtable = { |
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 |
|
_dispatch_thread_mediator is defined as follows:
1 | static struct dispatch_semaphore_s _dispatch_thread_mediator[] = { |
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 | dispatch_queue_t dispatch_queue_create(const char *label, dispatch_queue_attr_t attr) |
_dispatch_queue_init
Now look at the inline function
_dispatch_queue_init:
1 | inline void _dispatch_queue_init(dispatch_queue_t dq) |
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:
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 | // skip zero |
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 | void _dispatch_call_block_and_release2(void *block, void *ctxt) |
Common API Analysis
dispatch_async
1 | void dispatch_async(dispatch_queue_t dq, void (^work)(void)) |
dispatch_async mainly prepares its parameters and then
calls dispatch_async_f.
_dispatch_Block_copycreates a copy of the incoming block on the heap, or increases its reference count, ensuring that the block is not destroyed before execution.
_dispatch_call_block_and_release, as the name suggests, calls the block and then releases it.
1 | void _dispatch_call_block_and_release(void *block) |
dispatch_async_f
Now analyze dispatch_async_f:
1 | void dispatch_async_f(dispatch_queue_t dq, void *ctxt, dispatch_function_t func) |
- First look at
_dispatch_continuation_alloc_cacheonly. Its purpose is to fetch adispatch_continuation_tstructure 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 | static inline dispatch_continuation_t _dispatch_continuation_alloc_cacheonly(void) |
- If the current thread’s TLS does not contain a
dispatch_continuation_t,_dispatch_async_f_slow()is used.
- If
dcis not empty, set itsdo_vtabletoDISPATCH_OBJ_ASYNC_BIT, mainly for type distinction. Store the incoming block indc_ctxtas context, setdc_functo_dispatch_call_block_and_release, and finally call_dispatch_queue_pushto enqueue it.
DISPATCH_OBJ_ASYNC_BIT is a macro used to distinguish
async, group, and barrier:
1 |
Continue into _dispatch_async_f_slow:
1 | DISPATCH_NOINLINE static void _dispatch_async_f_slow(dispatch_queue_t dq, void *context, dispatch_function_t func) |
1 | dispatch_continuation_t _dispatch_continuation_alloc_from_heap(void) |
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 |
_dispatch_queue_push is a macro. It actually calls
_dispatch_queue_push_list.
_dispatch_queue_push_list
1 | static inline void |
_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.
- If the queue is not empty, place
dcat the tail and redirectdq->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.
- If the queue is empty, call
_dispatch_queue_push_list_slow:
1 | void _dispatch_queue_push_list_slow(dispatch_queue_t dq, struct dispatch_object_s *obj) |
_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 | dispatch_queue_t _dispatch_wakeup(dispatch_object_t dou) |
- If it is the main queue, call
_dispatch_queue_wakeup_maindirectly.
1 | void _dispatch_queue_wakeup_main(void) |
The core logic that wakes the main thread is inside
_dispatch_send_wakeup_main_thread, but unfortunately that
part is not open source.
- If it is a global queue, execution enters
_dispatch_queue_wakeup_global, the function pointed to by the global queue’sdx_probe. Here we truly encounter pthread:
1 | bool _dispatch_queue_wakeup_global(dispatch_queue_t dq) |
There are two main paths:
- If
dgq_kworkqueueexists in the queue context, callpthread_workqueue_additem_np. This function uses theworkq_kernreturnsystem call to notify theworkqueuethat 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,workqueuealways creates a thread, and that thread later executes_dispatch_worker_thread2.
- If
dgq_kworkqueuedoes not exist, callpthread_createto 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 | void *_dispatch_worker_thread(void *context) |
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 | void _dispatch_worker_thread2(void *context) |
This function schedules tasks. Two functions are important:
_dispatch_queue_concurrent_drain_one, which takes one item from the queue.
_dispatch_continuation_pop, which processes the item taken from the queue.
_dispatch_queue_concurrent_drain_one
1 | struct dispatch_object_s * |
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 | static inline void _dispatch_continuation_pop(dispatch_object_t dou) |
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 | DISPATCH_NOINLINE void _dispatch_queue_invoke(dispatch_queue_t 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 | dispatch_async |
dispatch_sync
After dispatch_async, look at
dispatch_sync.
1 | void dispatch_sync(dispatch_queue_t dq, void (^work)(void)) |
- If it is the main queue, call
_dispatch_sync_slow. This method eventually callsdispatch_sync_f.
1 | static void _dispatch_sync_slow(dispatch_queue_t dq, void (^work)(void)) |
- Otherwise, call
dispatch_sync_f:
1 | void dispatch_sync_f(dispatch_queue_t dq, void *ctxt, dispatch_function_t func) |
- If a synchronous task is pushed into a serial queue,
dispatch_barrier_sync_fis called:
1 | void dispatch_barrier_sync_f(dispatch_queue_t dq, void *ctxt, dispatch_function_t func) |
The core logic sets the current thread’s
dispatch_queue_key to dq, executes the block,
and then restores the previous old_dq.
- 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_slowis called to wait with a semaphore. Otherwise,_dispatch_wakeupis called directly to wake the queue and execute the task.
1 | static void _dispatch_sync_f_slow(dispatch_queue_t dq) |
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 | dispatch_sync |
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.