GCD Source Analysis 1 - Introduction

Preface

In everyday iOS development, GCD isolates us very well from direct interaction with threads, or pthread. What we usually deal with are queues and blocks. After using it for a long time, it is easy to stop feeling the presence of threads at all.

I had long wanted to find an opportunity to study the lower layers of GCD and appreciate the essence of its design. After some initial research, I found that materials analyzing GCD source code were scarce and scattered, making it difficult to form a complete understanding. One possible reason is that business demand does not strongly require this knowledge; the existing GCD APIs are already enough for most work. Even so, my curiosity about the underlying principles of GCD could not be stopped. On impulse, I decided to dig myself a hole and write a GCD source-code analysis series, describing my own understanding of GCD’s internals.

Choosing the GCD Version

The first step was choosing which version of the GCD source code to analyze. After comparing versions vertically, I found that later versions became larger and larger, with a rapidly increasing number of files and increasingly unfriendly source style. They were filled with a large number of macro-based build options, which made the code mentally expensive to read and not very helpful for understanding the core mechanism. After comparing multiple versions, I finally chose libdispatch-84.5.5.

GCD Source Analysis 1 - Introduction: Choosing the GCD Version (figure 1)

These are all the project files in that version. It is small, but complete enough; it still contains everything in GCD.

Preparation

Before reading the GCD source code, we need to understand some related basics.

Atomic Operations

Before analyzing the source code, first look at some atomic-operation macros. You do not need to memorize them; just keep an impression and look them up later when needed.

1
2
3
4
5
6
7
8
#define dispatch_atomic_xchg(p, n)  __sync_lock_test_and_set((p), (n))
#define dispatch_atomic_cmpxchg(p, o, n) __sync_bool_compare_and_swap((p), (o), (n))
#define dispatch_atomic_inc(p) __sync_add_and_fetch((p), 1)
#define dispatch_atomic_dec(p) __sync_sub_and_fetch((p), 1)
#define dispatch_atomic_add(p, v) __sync_add_and_fetch((p), (v))
#define dispatch_atomic_sub(p, v) __sync_sub_and_fetch((p), (v))
#define dispatch_atomic_or(p, v) __sync_fetch_and_or((p), (v))
#define dispatch_atomic_and(p, v) __sync_fetch_and_and((p), (v))
  • __sync_lock_test_and_set((p), (n)) sets *p to value and returns the previous value of *p.
  • __sync_bool_compare_and_swap((p), (o), (n)) provides atomic compare-and-swap: if *p == o, write n into *p. Here p is the address, o is the old value, and n is the new value.
  • __sync_add_and_fetch((p), 1) increments by 1 first, then returns.
  • __sync_sub_and_fetch((p), 1) decrements by 1 first, then returns.
  • __sync_add_and_fetch((p), (v)) adds v first, then returns.
  • __sync_sub_and_fetch((p), (v)) subtracts v first, then returns.
  • __sync_fetch_and_or((p), (v)) returns first, then performs OR.
  • __sync_fetch_and_and((p), (v)) returns first, then performs AND.

__builtin_expect

1
long __builtin_expect (long EXP, long C)  

Processors generally use a pipeline model, and some contain multiple logical execution units. The system can fetch multiple instructions in advance and process them in parallel. But when it encounters a branch, it may need to fetch instructions again, which is slower than continuing with already-prefetched instructions.

Because programmers are often bad at branch prediction, this built-in function, __builtin_expect, helps programmers provide branch-prediction hints and optimize programs. Its first parameter, EXP, is an integer expression, and the return value of the built-in function is also EXP. C is a compile-time constant. Its meaning is: I expect the value of EXP to equal constant C; the compiler should optimize based on that expectation.

For example:

1
2
3
4
if (__builtin_expect(x, 0))  
return 1;
else
return 2;

Obviously, the expected value of x is 0, meaning x is very likely to be 0. So the if branch is less likely. The compiler may compile it like this:

1
2
3
4
if (!x)  
return 2;
else
return 1;

This way, the CPU is more likely to execute the prefetched compiled if branch, improving branch-prediction accuracy and thus instruction execution speed.

fastpath and slowpath

1
2
#define fastpath(x) ((typeof(x))__builtin_expect((long)(x), ~0l))
#define slowpath(x) ((typeof(x))__builtin_expect((long)(x), 0l))

With __builtin_expect as the foundation, Apple’s fastpath and slowpath macros are easy to understand:

  • fastpath means this condition usually happens.
  • slowpath means you are confident this condition rarely happens.

DISPATCH_DECL

1
#define DISPATCH_DECL(name) typedef struct name##_s *name##_t

This macro appears in many places in the GCD source code. For example:

1
DISPATCH_DECL(dispatch_queue);

It expands to:

1
typedef struct dispatch_queue_s *dispatch_queue_t

So dispatch_queue_t can be used to define a pointer to a dispatch_queue_s structure.

Basic Data Structures

dispatch_object_t

1
2
3
4
5
6
7
8
9
10
typedef union {
struct dispatch_object_s *_do; // dispatch_object_s, the base class of GCD
struct dispatch_continuation_s *_dc; // task type; blocks in dispatch_async are usually wrapped into this type
struct dispatch_queue_s *_dq; // task queue; all queues we create use this type, serial or concurrent
struct dispatch_queue_attr_s *_dqa; // queue attributes
struct dispatch_group_s *_dg; // GCD group
struct dispatch_source_s *_ds; // GCD source; can monitor kernel events, file I/O events, socket events, etc.
struct dispatch_source_attr_s *_dsa; // source attributes
struct dispatch_semaphore_s *_dsema; // semaphore; if you know pthread, semaphores can schedule threads
} dispatch_object_t __attribute__((transparent_union));

dispatch_object_t is a union, so it can represent every data type inside that union.

Pay attention to __attribute__((transparent_union)). This is a typical transparent union. A transparent union weakens C’s type-checking mechanism and works somewhat like an implicit cast. With it, dispatch_object_s behaves like a C++ base class, making function parameter passing in C much more convenient.

At the lower level, types do not really exist in the same way we usually think about them. A transparent union breaks some of the constraints that types impose on us, allowing data to be viewed from a lower-level perspective. But it also weakens C’s type checking, which can lead to serious errors.

dispatch_object_s

1
2
3
4
5
6
7
8
9
10
11
12
13
struct dispatch_object_s {
DISPATCH_STRUCT_HEADER(dispatch_object_s, dispatch_object_vtable_s);
};

#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

dispatch_object_s is the base structure of the entire GCD system, and it is very important. Some fields are briefly explained in the comments. As the analysis goes deeper, we will gradually understand why each of these fields exists.

The type of do_vtable is dispatch_object_vtable_s:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct dispatch_object_vtable_s {
DISPATCH_VTABLE_HEADER(dispatch_object_s);
};

#define DISPATCH_VTABLE_HEADER(x) \
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 the queue; NULL for global and main queues
bool (*const do_probe)(struct x *); \ // checks whether values in the object satisfy conditions
void (*const do_dispose)(struct x *) // disposes the queue, usually calling the finalizer

#define dx_type(x) (x)->do_vtable->do_type
#define dx_kind(x) (x)->do_vtable->do_kind
#define dx_debug(x, y, z) (x)->do_vtable->do_debug((x), (y), (z))
#define dx_dispose(x) (x)->do_vtable->do_dispose(x)
#define dx_invoke(x) (x)->do_vtable->do_invoke(x)
#define dx_probe(x) (x)->do_vtable->do_probe(x)

This structure contains operation functions for dispatch_object_s, and it defines short macros for those operations to make calls more convenient.

dispatch_continuation_s

This structure is mainly used to wrap blocks and functions:

1
2
3
4
5
6
7
8
9
10
11
struct dispatch_continuation_s {
DISPATCH_CONTINUATION_HEADER(dispatch_continuation_s);
dispatch_group_t dc_group;
void * dc_data[3];
};

#define DISPATCH_CONTINUATION_HEADER(x) \
const void * do_vtable; \
struct x *volatile do_next; \
dispatch_function_t dc_func; \
void * dc_ctxt

dispatch_continuation_s represents a task. Blocks passed to dispatch_async are usually wrapped into this data type.

If dc_vtable is less than 127, then the object is a continuation. Otherwise, the object has a private layout and memory management rules. The first two words must align with normal objects.

dispatch_queue_s

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define DISPATCH_QUEUE_MIN_LABEL_SIZE   64

#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

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 difference between dispatch_queue_s and dispatch_object_s is that dispatch_queue_s adds DISPATCH_QUEUE_HEADER and dq_label[DISPATCH_QUEUE_MIN_LABEL_SIZE]. This also tells us that queue names should be shorter than 64 characters.

dispatch_group_s

1
2
3
DISPATCH_DECL(dispatch_group);

#define DISPATCH_DECL(name) typedef struct name##_s *name##_t;

dispatch_group_t is equivalent to dispatch_group_s *. But what is dispatch_group_s really? I could not find its structure definition anywhere in the source. So I had to take another path.

While reading the source, I found a clue in the definition of dispatch_group_create in semaphore.c:

1
2
3
4
5
dispatch_group_t
dispatch_group_create(void)
{
return (dispatch_group_t)dispatch_semaphore_create(LONG_MAX);
}

The result is quite surprising: dispatch_group_t is essentially a semaphore whose value is LONG_MAX.

dispatch_source_s

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
struct dispatch_source_s {
DISPATCH_STRUCT_HEADER(dispatch_source_s, dispatch_source_vtable_s);
DISPATCH_QUEUE_HEADER;
union {
char _ds_pad[DISPATCH_QUEUE_MIN_LABEL_SIZE];
struct {
char dq_label[8];
dispatch_kevent_t ds_dkev;
dispatch_source_handler_function_t ds_handler_func;
void *ds_handler_ctxt;
void *ds_cancel_handler;
unsigned int ds_is_level:1,
ds_is_adder:1,
ds_is_installed:1,
ds_needs_rearm:1,
ds_is_armed:1,
ds_is_legacy:1,
ds_cancel_is_block:1,
ds_handler_is_block:1;
unsigned int ds_atomic_flags;
unsigned long ds_data;
unsigned long ds_pending_data;
unsigned long ds_pending_data_mask;
TAILQ_ENTRY(dispatch_source_s) ds_list;
unsigned long ds_ident_hack;
struct dispatch_timer_source_s ds_timer;
};
};
};

dispatch_semaphore_s

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct dispatch_semaphore_s {
DISPATCH_STRUCT_HEADER(dispatch_semaphore_s, dispatch_semaphore_vtable_s);
long dsema_value; // semaphore value
long dsema_orig; // initial/original value set when the semaphore is created

// Prevents accidental semaphore wake-ups. This value is incremented during signal.
// During wait, if the value is not 1, the function returns directly instead of entering sem_wait.
size_t dsema_sent_ksignals;

semaphore_t dsema_port;
semaphore_t dsema_waiter_port;
size_t dsema_group_waiters;
struct dispatch_sema_notify_s *dsema_notify_head;
struct dispatch_sema_notify_s *dsema_notify_tail;
};

UML Diagram

GCD Source Analysis 1 - Introduction: UML Diagram (figure 2)

libdispatch Initialization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void libdispatch_init(void)
{
// These asserts ensure that macro definitions are correct.
dispatch_assert(DISPATCH_QUEUE_PRIORITY_COUNT == 3);
dispatch_assert(DISPATCH_ROOT_QUEUE_COUNT == 6);

dispatch_assert(DISPATCH_QUEUE_PRIORITY_LOW == -DISPATCH_QUEUE_PRIORITY_HIGH);
dispatch_assert(countof(_dispatch_root_queues) == DISPATCH_ROOT_QUEUE_COUNT);
dispatch_assert(countof(_dispatch_thread_mediator) == DISPATCH_ROOT_QUEUE_COUNT);
dispatch_assert(countof(_dispatch_root_queue_contexts) == DISPATCH_ROOT_QUEUE_COUNT);

// TSD pool allocation.
_dispatch_thread_key_init_np(dispatch_queue_key, _dispatch_queue_cleanup);
_dispatch_thread_key_init_np(dispatch_sema4_key, (void (*)(void *))dispatch_release); // use the extern release
_dispatch_thread_key_init_np(dispatch_cache_key, _dispatch_cache_cleanup2);
#if DISPATCH_PERF_MON
_dispatch_thread_key_init_np(dispatch_bcounter_key, NULL);
#endif

// Set TSD for the main thread.
_dispatch_thread_setspecific(dispatch_queue_key, &_dispatch_main_q);

_dispatch_queue_set_width_init();
}

pthread_key_t

In a multithreaded environment, data space is shared, so global variables are also shared by all threads. But sometimes an application needs thread-private global variables: values that are valid only inside a certain thread but can still be accessed across multiple functions. For example, each thread may need to maintain its own linked list while using the same functions to operate on it.

The simplest way is to use thread-specific data structures with the same name but different variable addresses. This kind of data structure is called Thread-Specific Data, or TSD.

GCD defines four keys:

1
2
3
4
static const unsigned long dispatch_queue_key = __PTK_LIBDISPATCH_KEY0;
static const unsigned long dispatch_sema4_key = __PTK_LIBDISPATCH_KEY1;
static const unsigned long dispatch_cache_key = __PTK_LIBDISPATCH_KEY2;
static const unsigned long dispatch_bcounter_key = __PTK_LIBDISPATCH_KEY3;

pthread_key_create

_dispatch_thread_key_init_np calls pthread_key_create:

1
int pthread_key_create(pthread_key_t *key, void (*destr_function) (void *))

This function allocates an entry from the TSD pool and assigns its value to key for later access. If destr_function is not empty, when the thread exits through pthread_exit(), destr_function() is called with the data associated with key, allowing allocated buffers to be released.

No matter which thread calls pthread_key_create(), the created key is accessible to all threads. But each thread can fill that key with a different value according to its own needs. These values are thread-specific and maintained independently for each thread. This is equivalent to providing a global variable with the same name but different values per thread.

pthread_setspecific and pthread_getspecific

Here, the main thread sets its TSD to the address of _dispatch_main_q:

1
_dispatch_thread_setspecific(dispatch_queue_key, &_dispatch_main_q);

Summary

The basic data structures covered in this article are mainly here to make them familiar. Explaining data structures only for the sake of data structures is not enough to make everything clear. In the following GCD source-code analysis articles, these pieces will be clarified step by step.

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

Title:GCD Source Analysis 1 - Introduction

Author:lingyun

Published:2018-01-31 22:05

Updated:2026-10-07 00:00

Original link:https://tsuijunxi.github.io/en/2018/01/31/gcd-source-analysis-1-introduction/

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