Semaphores are the most common operation in GCD and are often used to guarantee multi-threaded security of resources. Its essence is actually implemented based on the Semaphore interface of the Mach kernel, which will be analyzed in this article from the perspective of source code.

@interface MyObject : NSObject
@property (nonatomic, strong) dispatch_semaphore_t sema;
@end

@implementation MyObject
@end
Copy the code

Initialize the semaphore, and you can see a structure like this:

myObj.sema = dispatch_semaphore_create(0);
// (lldb) po myObj.sema
// <OS_dispatch_semaphore: semaphore[0x6000007f14f0] = { xref = 1, ref = 1, port = 0x0, value = 0, orig = 0 }>
Copy the code

Xref and ref are reference related. Value and Orig are key to the semaphore’s performance. After the dispatch_semaphore_WAIT operation is performed, the value value is deleted once.

dispatch_semaphore_wait(myObj.sema, DISPATCH_TIME_FOREVER);
// (lldb) po myObj.sema
// <OS_dispatch_semaphore: semaphore[0x60000133b890] = { xref = 2, ref = 1, port = 0x4007, value = -1, orig = 0 }>
Copy the code

So what do all these member variables mean?

dispatch_semaphore_t

The basic data structure of the semaphore is as follows:

struct dispatch_semaphore_s {
	DISPATCH_OBJECT_HEADER(semaphore);
	long volatile dsema_value;
	long dsema_orig;
	_dispatch_sema4_t dsema_sema;
};
Copy the code
  1. DISPATCH_OBJECT_HEADER(semaphore). This header is found in many objects in GCD and encapsulates some uniform data structure.
  2. Dsema_orig is the initial value of the semaphore.
  3. Dsema_value is the current value of the semaphore, and the semaphore API operates on dsema_value.
  4. _dispatch_sema4_t dsema_sema, semaphore structure.

The _DISPATCH_OBJECT_HEADER is a macro definition:

#define DISPATCH_OBJECT_HEADER(x) \
	struct dispatch_object_s _as_do[0]; \
	_DISPATCH_OBJECT_HEADER(x)
Copy the code

_DISPATCH_OBJECT_HEADER is as follows:

#define _DISPATCH_OBJECT_HEADER(x) \
	struct _os_object_s _as_os_obj[0]; \
	OS_OBJECT_STRUCT_HEADER(dispatch_##x); \
	struct dispatch_##x##_s *volatile do_next; \
	struct dispatch_queue_s *do_targetq; \
	void *do_ctxt; \
	void *do_finalizer
Copy the code

There are two key members:

struct dispatch_# #x# # _s *volatile do_next; \
struct dispatch_queue_s *do_targetq; \
Copy the code

We’ll talk about those two later.

The dispatch_object_s object also uses the _DISPATCH_OBJECT_HEADER:

struct dispatch_object_s {
	_DISPATCH_OBJECT_HEADER(object);
};

/* * Dispatch objects are NOT C++ objects. Nevertheless, we can at least keep C++ * aware of type compatibility. */
typedef struct dispatch_object_s {
private:
	dispatch_object_s();
	~dispatch_object_s();
	dispatch_object_s(const dispatch_object_s &);
	void operator= (const dispatch_object_s &);
} *dispatch_object_t;

typedef union {
	struct _os_object_s* _os_obj;
	struct dispatch_object_s* _do;
	struct dispatch_queue_s* _dq;
	struct dispatch_queue_attr_s* _dqa;
	struct dispatch_group_s* _dg;
	struct dispatch_source_s* _ds;
	struct dispatch_mach_s* _dm;
	struct dispatch_mach_msg_s* _dmsg;
	struct dispatch_semaphore_s* _dsema;
	struct dispatch_data_s* _ddata;
	struct dispatch_io_s* _dchannel;
} dispatch_object_t DISPATCH_TRANSPARENT_UNION;
Copy the code

Dispatch_object_t is a consortium, and all objects in libDispatch need to be used.

dispatch_semaphore_create

/ *! * @function dispatch_semaphore_create * * @abstract * Creates new counting semaphore with an initial value. * * @discussion * Passing zero for the value is useful for when two threads need to reconcile * the completion of a particular event. Passing a value greater than zero is * useful for managing a finite pool of resources, where the pool size is equal * to the value. * * @param value * The starting value for the semaphore. Passing a value less than zero will * cause NULL to be returned. * * @result * The newly created semaphore, or NULL on failure. */
API_AVAILABLE(macos(10.6), ios(4.0))
DISPATCH_EXPORT DISPATCH_MALLOC DISPATCH_RETURNS_RETAINED DISPATCH_WARN_RESULT
DISPATCH_NOTHROW
dispatch_semaphore_t
dispatch_semaphore_create(long value);
Copy the code

The value parameter is invalid if it is less than 0. Its implementation source code is as follows:

dispatch_semaphore_t
dispatch_semaphore_create(long value)
{
	dispatch_semaphore_t dsema;

	// If the internal value is negative, then the absolute of the value is
	// equal to the number of waiting threads. Therefore it is bogus to
	// initialize the semaphore with a negative value.
	if (value < 0) {
		return DISPATCH_BAD_INPUT;
	}

	dsema = _dispatch_object_alloc(DISPATCH_VTABLE(semaphore),
			sizeof(struct dispatch_semaphore_s));
	dsema->do_next = DISPATCH_OBJECT_LISTLESS;
	// The destination queue
	dsema->do_targetq = _dispatch_get_default_queue(false);
    / / the current value
	dsema->dsema_value = value;
	_dispatch_sema4_init(&dsema->dsema_sema, _DSEMA4_POLICY_FIFO);
    / / initial value
	dsema->dsema_orig = value;
	return dsema;
}
Copy the code

_dispatch_object_alloc

The first parameter of _dispatch_object_alloc is DISPATCH_VTABLE(semaphore). The callback function of dispatch_semaphore_t is set, such as the destruction function _dispatch_semaphore_Dispose.

void *
_dispatch_object_alloc(const void *vtable, size_t size)
{
#if OS_OBJECT_HAVE_OBJC1
	const struct dispatch_object_vtable_s* _vtable = vtable;
	dispatch_object_t dou;
	dou._os_obj = _os_object_alloc_realized(_vtable->_os_obj_objc_isa, size);
	dou._do->do_vtable = vtable;
	return dou._do;
#else
	return _os_object_alloc_realized(vtable, size);
#endif
}
Copy the code

The _OS_object_alloc_realized function looks like this, with the _OS_objc_alloc function called.

_os_object_t
_os_object_alloc_realized(const void *cls, size_t size)
{
	dispatch_assert(size >= sizeof(struct _os_object_s));
	return _os_objc_alloc(cls, size);
}
Copy the code
static inline id
_os_objc_alloc(Class cls, size_t size)
{
	id obj;
	size -= sizeof(((struct _os_object_s *)NULL)->os_obj_isa);
	while(unlikely(! (obj = class_createInstance(cls, size)))) { _dispatch_temporary_resource_shortage(); }return obj;
}
Copy the code

DISPATCH_VTABLE(semaphore)

The definition of DISPATCH_VTABLE is as follows:

#define DISPATCH_VTABLE(name) DISPATCH_OBJC_CLASS(name)

// vtable symbols
#define OS_OBJECT_VTABLE(name)		(&OS_OBJECT_CLASS_SYMBOL(name))
#define DISPATCH_OBJC_CLASS(name)	(&DISPATCH_CLASS_SYMBOL(name))

#define DISPATCH_CLASS_SYMBOL(name) OS_dispatch_##name##_class
Copy the code

In fact, DISPATCH_VTABLE(semaphore) is &os_dispatch_semaphore_class.

There’s also a macro called DISPATCH_VTABLE_INSTANCE,

DISPATCH_VTABLE_INSTANCE(semaphore,
	.do_type        = DISPATCH_SEMAPHORE_TYPE,
	.do_dispose     = _dispatch_semaphore_dispose,
	.do_debug       = _dispatch_semaphore_debug,
	.do_invoke      = _dispatch_object_no_invoke,
);

#define DISPATCH_VTABLE_INSTANCE(name, ...) \
		DISPATCH_VTABLE_SUBCLASS_INSTANCE(name, name, __VA_ARGS__)

#define DISPATCH_VTABLE_SUBCLASS_INSTANCE(name, ctype, ...) \
		OS_OBJECT_VTABLE_SUBCLASS_INSTANCE(dispatch_##name, dispatch_##ctype, \
				_dispatch_xref_dispose, _dispatch_dispose, __VA_ARGS__)		

// vtables for proper classes
#define OS_OBJECT_VTABLE_INSTANCE(name, xdispose, dispose, ...) \
		OS_OBJECT_VTABLE_SUBCLASS_INSTANCE(name, name, \
				xdispose, dispose, __VA_ARGS__)

#define OS_OBJECT_VTABLE_SUBCLASS_INSTANCE(name, ctype, xdispose, dispose, ...) \
		__attribute__((section("__DATA,__objc_data"), used)) \
		const struct ctype##_extra_vtable_s \
		OS_OBJECT_EXTRA_VTABLE_SYMBOL(name) = { __VA_ARGS__ }

#define OS_OBJECT_EXTRA_VTABLE_SYMBOL(name) _OS_##name##_vtable										
Copy the code

All of these macro definitions, going around and around, are intended to create a VTable. Vtable is a virtual function table that can be indexed to quickly obtain methods. Compared to OC method lookup, the vtable method provides a significant performance improvement. A similar vTABLE mechanism is heavily used in Swift, such as.

// Investigation method
let method = MyClass.vtable[methodIndex]
// Call the method
method()
Copy the code

_dispatch_sema4_create

DISPATCH_ALWAYS_INLINE
static inline void
_dispatch_sema4_create(_dispatch_sema4_t *sema, int policy)
{
	if (!_dispatch_sema4_is_created(sema)) {
		_dispatch_sema4_create_slow(sema, policy);
	}
}
Copy the code

_dispatch_sema4_create_slow

#define_dispatch_sema4_is_created(sema) (*(sema) ! = MACH_PORT_NULL)

void
_dispatch_sema4_create_slow(_dispatch_sema4_t *s4, int policy)
{
	semaphore_t tmp = MACH_PORT_NULL;

	_dispatch_fork_becomes_unsafe();

	// lazily allocate the semaphore port

	// Someday:
	// 1) Switch to a doubly-linked FIFO in user-space.
	// 2) User-space timers for the timeout.

#if DISPATCH_USE_OS_SEMAPHORE_CACHE
	if (policy == _DSEMA4_POLICY_FIFO) {
		tmp = (_dispatch_sema4_t)os_get_cached_semaphore();
		if(! os_atomic_cmpxchg(s4, MACH_PORT_NULL, tmp, relaxed)) { os_put_cached_semaphore((os_semaphore_t)tmp);
		}
		return;
	}
#endif

	kern_return_t kr = semaphore_create(mach_task_self(), &tmp, policy, 0);
	DISPATCH_SEMAPHORE_VERIFY_KR(kr);

	if (!os_atomic_cmpxchg(s4, MACH_PORT_NULL, tmp, relaxed)) {
		kr = semaphore_destroy(mach_task_self(), tmp);
		DISPATCH_SEMAPHORE_VERIFY_KR(kr);
	}
}
Copy the code

If the semaphore_cache is used (DISPATCH_USE_OS_SEMAPHORE_CACHE) and is FIFO, the semaphore_cache will be used directly from the cache.

Otherwise, a new semaphore is created using semaphore_create.

dispatch_semaphore_wait

The wait operation subtracted the value of the semaphore by one. If the result of the subtracted operation is negative, the function waits for the release of the semaphore.

/ *! * @function dispatch_semaphore_wait * * @abstract * Wait (decrement) for a semaphore. * * @discussion * Decrement the counting semaphore. If the resulting value is less than zero, * this function waits for a signal to occur before returning. * * @param dsema * The semaphore. The result of passing NULL in this parameter is undefined. * * @param timeout * When to timeout (see dispatch_time). As a convenience, there are the * DISPATCH_TIME_NOW and DISPATCH_TIME_FOREVER constants. * * @result * Returns zero on success, or non-zero if the timeout occurred. */
API_AVAILABLE(macos(10.6), ios(4.0))
DISPATCH_EXPORT DISPATCH_NONNULL_ALL DISPATCH_NOTHROW
long
dispatch_semaphore_wait(dispatch_semaphore_t dsema, dispatch_time_t timeout);
Copy the code

Source code implementation is as follows:

long
dispatch_semaphore_wait(dispatch_semaphore_t dsema, dispatch_time_t timeout)
{
	long value = os_atomic_dec2o(dsema, dsema_value, acquire);
	if (likely(value >= 0)) {
		return 0;
	}
	return _dispatch_semaphore_wait_slow(dsema, timeout);
}
Copy the code

Dispatch_semaphore_wait begins by calling the system’s atomic operation OS_atomic_DEC2O, which reduces the semaphore value by one. After this operation, semaphore resources are still available if the semaphore is not negative. If the value is negative, run the _dispatch_semaphore_wait_slow command.

DISPATCH_NOINLINE
static long
_dispatch_semaphore_wait_slow(dispatch_semaphore_t dsema,
		dispatch_time_t timeout)
{
	long orig;

	_dispatch_sema4_create(&dsema->dsema_sema, _DSEMA4_POLICY_FIFO);
	switch (timeout) {
	default:
		if(! _dispatch_sema4_timedwait(&dsema->dsema_sema, timeout)) {break;
		}
		// Fall through and try to undo what the fast path did to
		// dsema->dsema_value
	case DISPATCH_TIME_NOW:
		orig = dsema->dsema_value;
		while (orig < 0) {
			if (os_atomic_cmpxchgvw2o(dsema, dsema_value, orig, orig + 1,
					&orig, relaxed)) {
				return_DSEMA4_TIMEOUT(); }}// Another thread called semaphore_signal().
		// Fall through and drain the wakeup.
	case DISPATCH_TIME_FOREVER:
		_dispatch_sema4_wait(&dsema->dsema_sema);
		break;
	}
	return 0;
}
Copy the code

The _dispatch_semaphore_wait_slow function determines the wait behavior based on timeout,

  1. For a specific timeout period, call _dispatch_sema4_timedWait (&dsema-> dSEMa_sema, timeout) to wait for a timeout period.
  2. For DISPATCH_TIME_NOW, the current value of the semaphore is obtained, which must be non-negative. If it is negative, then the last time dispatch_semaphore_WAIT was called it must have been negative, and then dispatch_semaphore_wait will block. After that, the os_atomic_cmpxchgvw2O function is called, which adds one to the semaphore’s dsema_value variable. This plus one is to cancel out the minus one of dispatch_semaphore_WAIT. So DISPATCH_TIME_NOW will return a timeout immediately in this case.
  3. For DISPATCH_TIME_FOREVER, call _dispatch_sema4_wait(&dsema->dsema_sema); Wait forever until the semaphore is released.

The source code for _dispatch_sema4_wait and _dispatch_sema4_timedWait is as follows:

void
_dispatch_sema4_wait(_dispatch_sema4_t *sema)
{
	kern_return_t kr;
	do {
		kr = semaphore_wait(*sema);
	} while (kr == KERN_ABORTED);
	DISPATCH_SEMAPHORE_VERIFY_KR(kr);
}

bool
_dispatch_sema4_timedwait(_dispatch_sema4_t *sema, dispatch_time_t timeout)
{
	mach_timespec_t _timeout;
	kern_return_t kr;

	do {
		uint64_t nsec = _dispatch_timeout(timeout);
		_timeout.tv_sec = (typeof(_timeout.tv_sec))(nsec / NSEC_PER_SEC);
		_timeout.tv_nsec = (typeof(_timeout.tv_nsec))(nsec % NSEC_PER_SEC);
		kr = semaphore_timedwait(*sema, _timeout);
	} while (unlikely(kr == KERN_ABORTED));

	if (kr == KERN_OPERATION_TIMED_OUT) {
		return true;
	}
	DISPATCH_SEMAPHORE_VERIFY_KR(kr);
	return false;
}
Copy the code

Semaphore_wait and semaphore_timedwait of the Mach kernel are called to perform wait operation. So the GCD semaphore is actually implemented based on the Semaphore interface of the Mach kernel. The semaphore_timedwait function specifies the timeout period.

dispatch_semaphore_signal

Dispatch_semaphore_signal is responsible for releasing the semaphore.

/ *! * @function dispatch_semaphore_signal * * @abstract * Signal (increment) a semaphore. * * @discussion * Increment the counting semaphore. If the previous value was less than zero, * this function wakes a waiting thread before returning. * * @param dsema The counting semaphore. * The result of passing NULL in this parameter is undefined. * * @result * This function returns non-zero if a thread is woken. Otherwise, zero is * returned. */
API_AVAILABLE(macos(10.6), ios(4.0))
DISPATCH_EXPORT DISPATCH_NONNULL_ALL DISPATCH_NOTHROW
long
dispatch_semaphore_signal(dispatch_semaphore_t dsema);
Copy the code

The source code for dispatch_semaphore_signal is:

long
dispatch_semaphore_signal(dispatch_semaphore_t dsema)
{
	long value = os_atomic_inc2o(dsema, dsema_value, release);
	if (likely(value > 0)) {
		return 0;
	}
	if (unlikely(value == LONG_MIN)) {
		DISPATCH_CLIENT_CRASH(value,
				"Unbalanced call to dispatch_semaphore_signal()");
	}
	return _dispatch_semaphore_signal_slow(dsema);
}
Copy the code

For the “dispatch_semaphore_signal” operation, the atomic operation os_atomic_INC2O is performed, and the semaphore value is increased by one. If the signal is excessively discharged and the semaphore value is LONG_MIN, the crash will be triggered. The information is *** call to dispatch_semaphore_signal()***. So, similar to GCD group enter/leave, excessive calls to dispatch_semaphore_signal could theoretically cause a crash. But it doesn’t actually reproduce, which is weird.

_dispatch_semaphore_signal_slow actually calls the Semaphore_signal function of the Mach kernel.

DISPATCH_NOINLINE
long
_dispatch_semaphore_signal_slow(dispatch_semaphore_t dsema)
{
	_dispatch_sema4_create(&dsema->dsema_sema, _DSEMA4_POLICY_FIFO);
	_dispatch_sema4_signal(&dsema->dsema_sema, 1);
	return 1;
}

void
_dispatch_sema4_signal(_dispatch_sema4_t *sema, long count)
{
	do {
		kern_return_t kr = semaphore_signal(*sema);
		DISPATCH_SEMAPHORE_VERIFY_KR(kr);
	} while (--count);
}
Copy the code

Semaphore_signal wakes up a thread that is waiting in semaphore_WAIT. If there are multiple waiting threads, they wake up according to thread priority.

_dispatch_semaphore_dispose

The destruction function of the semaphore is as follows:

void
_dispatch_semaphore_dispose(dispatch_object_t dou,
		DISPATCH_UNUSED bool *allow_free)
{
	dispatch_semaphore_t dsema = dou._dsema;

	if (dsema->dsema_value < dsema->dsema_orig) {
		DISPATCH_CLIENT_CRASH(dsema->dsema_orig - dsema->dsema_value,
				"Semaphore object deallocated while in use");
	}

	_dispatch_sema4_dispose(&dsema->dsema_sema, _DSEMA4_POLICY_FIFO);
}
Copy the code

Dsema ->dsema_value < dsema->dsema_orig This is also one of the problems that can be easily encountered, as we’ll see later.

The _dispatch_sema4_Dispose code is as follows:

DISPATCH_ALWAYS_INLINE
static inline void
_dispatch_sema4_dispose(_dispatch_sema4_t *sema, int policy)
{
	if(_dispatch_sema4_is_created(sema)) { _dispatch_sema4_dispose_slow(sema, policy); }}Copy the code

Further down, the _dispatch_sema4_dispose_slow function is called,

void
_dispatch_sema4_dispose_slow(_dispatch_sema4_t *sema, int policy)
{
	semaphore_t sema_port = *sema;
	*sema = MACH_PORT_DEAD;
#if DISPATCH_USE_OS_SEMAPHORE_CACHE
	if (policy == _DSEMA4_POLICY_FIFO) {
		return os_put_cached_semaphore((os_semaphore_t)sema_port);
	}
#endif
	kern_return_t kr = semaphore_destroy(mach_task_self(), sema_port);
	DISPATCH_SEMAPHORE_VERIFY_KR(kr);
}
Copy the code

If the semaphore cache is used and FIFO is used, simply place the semaphore object to be reclaimed into the cache. Otherwise, the semaphore_destroy function of the Mach kernel is called to destroy the semaphore.

Some of the collapse

Similar to GCD Group’s Enter /leave interface, this type of interface should ensure that the operation is balanced. Doing so could lead to serious problems. Apple’s documentation makes it clear:

Calls to dispatch_semaphore_signal must be balanced with calls to dispatch_semaphore_wait. Attempting to dispose of a semaphore with a count lower than value causes an EXC_BAD_INSTRUCTION exception.

Unbalanced call to dispatch_semaphore_signal()

This has not yet been repeated. However, it should be caused by excessive calls to dispatch_semaphore_signal.

Semaphore object deallocated while in use

Exception Type:  EXC_BREAKPOINT (SIGTRAP)
Exception Codes: 0x0000000000000001.0x00000001a3b77ff4
Termination Signal: Trace/BPT trap: 5
Termination Reason: Namespace SIGNAL, Code 0x5
Terminating Process: exc handler [249]
Triggered by Thread:  15

Application Specific Information:
BUG IN CLIENT OF LIBDISPATCH: Semaphore object deallocated while in use
Abort Cause 1
Thread 15 name:  Dispatch queue: com.xxxx.xxxx.xxxxQueue (QOS: UNSPECIFIED)

Thread 15 Crashed:
0   libdispatch.dylib             	0x00000001a3b77ff4 0x1a3b75000 + 12276
1   libdispatch.dylib             	0x00000001a3b77014 0x1a3b75000 + 8212
2   libobjc.A.dylib               	0x00000001a336e7cc 0x1a336a000 + 18380
3   libobjc.A.dylib               	0x00000001a337e6b8 0x1a336a000 + 83640
4   libobjc.A.dylib               	0x00000001a337e720 0x1a336a000 + 83744
5   XXXX                          	0x000000010535056c -[MyXXXXObject dealloc] + 70960492 (MyXXXXObject.mm:xx)
6   XXXX                          	0x000000010535171c __destroy_helper_block_ea8_32s40s48s56s64r + 70965020 (MyXXXXObject.mm:xxx)
7   libsystem_blocks.dylib        	0x00000001a3c30a44 0x1a3c30000 + 2628
8   Foundation                    	0x00000001a4b09410 0x1a4aea000 + 128016
9   Foundation                    	0x00000001a4b97330 0x1a4aea000 + 709424
10  libsystem_blocks.dylib        	0x00000001a3c30a44 0x1a3c30000 + 2628
11  libdispatch.dylib             	0x00000001a3bd57d4 0x1a3b75000 + 395220
12  libdispatch.dylib             	0x00000001a3b7a01c 0x1a3b75000 + 20508
13  libdispatch.dylib             	0x00000001a3b796e0 0x1a3b75000 + 18144
14  libdispatch.dylib             	0x00000001a3b86030 0x1a3b75000 + 69680
15  libdispatch.dylib             	0x00000001a3b868d4 0x1a3b75000 + 71892
16  libsystem_pthread.dylib       	0x00000001a3db61b4 0x1a3daa000 + 49588
17  libsystem_pthread.dylib       	0x00000001a3db8cd4 0x1a3daa000 + 60628
Copy the code

This type of crash occurs when the object is released while the internal semaphore object is still in use (i.e. Dsema ->dsema_value < dsema->dsema_orig, the value of the semaphore is not restored to its original value by the signal operation). This is common when another thread performs a wait operation and releases the semaphore without a corresponding signal (as a result of the release of the object holding the semaphore).

This can be reproduced by the following code to see the call stack.

dispatch_semaphore_t sema = dispatch_semaphore_create(1);
dispatch_semaphore_wait(sema, DISPATCH_TIME_FOREVER);

sema = dispatch_semaphore_create(1);
Copy the code

Re-assigning sema while the semaphore is still in use will crash, even if sema = nil; Will be, too. The stack looks like this:

_dispatch_semaphore_dispose.cold1.
_disaptch_semaphore_dispose
_dispatch_dispose
sema = dispatch_semaphore_create(1);
Copy the code

Of course, _disaptch_semaphore_Dispose calls _dispatch_sema4_dispose_slow, which we have already analyzed in the previous code.

Solution: If you have a known semaphore, such as a semaphore with an initial value of 1, you can manually perform a signal operation on the dealloc object to avoid dsema->dsema_value < dsema->dsema_orig. After all, the signal operation is overdone, so it should not be a problem for now.

However, the actual usage scenario is to try to keep the semaphore’s wait and signal in balance so that the code logic is not problematic.

The resources

  • Dispatch
  • GCD Internals
  • dispatch_semaphore_create
  • dispatch_semaphore