preface

Reading the source code on the one hand can make us realize the principle of some things, but also to see some subtle design. This article will be combined with @synchronized source code to feel apple engineers on one-way linked lists clever use. This article is based on objC4-818.2 source code.

๐Ÿ‘‹

  • Wechat: RyukieW
  • Wechat official account: LabLawliet
  • ๐Ÿ“ฆ Archive of technical articles
  • ๐Ÿ™ making
My personal project Minesweeper Elic Endless Ladder Dream of books
type The game financial
AppStore Elic Umemi

A, locate to synchronized related source code

So how does synchronized work? @synchronized is not directly accessible in Xcode. We tried to find clues in objC’s source code.

Objc_sync_exit/objc_sync_Enter are found in pairs. Suspected of being the underlying implementation of @synchronized. So how do you verify that?

Here I decided to restore the OC code to C++ code to take a look.

Restore using clang-rewrite-objc main.m -o main.cpp. Navigate to the main function, where objc_sync_exit/objc_sync_Enter does appear in pairs.

int main(int argc, const char * argv[]) {
    /* @autoreleasepool */ { __AtAutoreleasePool __autoreleasepool;
        NSObject *obj = ((NSObject *(*)(id, SEL))(void *)objc_msgSend)((id)objc_getClass("NSObject"), sel_registerName("new"));
        { id _rethrow = 0; id _sync_obj = (id)obj; objc_sync_enter(_sync_obj);
            try {
                struct _SYNC_EXIT { _SYNC_EXIT(id arg) : sync_exit(arg) {}
                    ~_SYNC_EXIT() {objc_sync_exit(sync_exit); } id sync_exit; } _sync_exit(_sync_obj);NSLog((NSString *)&__NSConstantStringImpl__var_folders_py_7v1wvf813z5bmw0hr97yplwc0000gn_T_main_7d2c6c_mi_0);
            } catch(id e) {_rethrow = e; } {struct _FIN { _FIN(id reth) : rethrow(reth) {}
                ~_FIN() { if (rethrow) objc_exception_throw(rethrow); } id rethrow; } _fin_force_rethow(_rethrow); }}}return 0;
}
Copy the code

Next we can rest assured in objC source code to continue to explore.

Second, the objc_sync_enter

int objc_sync_enter(id obj)
{
    int result = OBJC_SYNC_SUCCESS;
    if (obj) {
        // Create a SyncData from the obj passed in
        SyncData* data = id2data(obj, ACQUIRE);
        ASSERT(data);
        data->mutex.lock(a); }else {
        /// do nothing if obj passed is null
        // @synchronized(nil) does nothing
        if (DebugNilSync) {
            _objc_inform("NIL SYNC DEBUG: @synchronized(nil); set a breakpoint on objc_sync_nil to debug");
        }
        objc_sync_nil(a); }return result;
}
Copy the code
  • I’m going to use the incoming hereobjthroughid2dataTo get aSyncDataStructure pointer
  • If the incomingobjTo do nothing

Third, objc_sync_exit

int objc_sync_exit(id obj)
{
    int result = OBJC_SYNC_SUCCESS;
    if (obj) {
        SyncData* data = id2data(obj, RELEASE); 
        if(! data) { result = OBJC_SYNC_NOT_OWNING_THREAD_ERROR; }else {
            // Try unlocking
            bool okay = data->mutex.tryUnlock(a);if(! okay) {// Unlock failedresult = OBJC_SYNC_NOT_OWNING_THREAD_ERROR; }}}else {
        // @synchronized(nil) does nothing
    }
    return result;
}
Copy the code

4. Data structure of SyncData

typedef struct alignas(CacheLineSize) SyncData {
    struct SyncData* nextData;
    DisguisedPtr<objc_object> object;
    int32_t threadCount;  // number of THREADS using this block
    recursive_mutex_t mutex;
} SyncData;
Copy the code
  • nextData
    • SyncData pointer, which isSingly linked listThe structure of the
    • This structure issynchronizedThe key points for nested use will be covered later
  • object
    • The incoming obj
  • threadCount
    • How many threads are using the current block
  • mutex
    • Recursive locking

Fifth, id2data

static SyncData* id2data(id object, enum usage why)
{
    spinlock_t *lockp = &LOCK_FOR_OBJ(object);
    SyncData **listp = &LIST_FOR_OBJ(object);
    SyncData* result = NULL; . }Copy the code

5.1 Finding the Data Structure corresponding to Object

  • LOCK_FOR_OBJ
    • Find the correspondingLock an
  • LIST_FOR_OBJ
    • Find the correspondingSyncData ็š„Pointer of pointer

The source code is obtained from the static StripedMap

sDataLists, a static hash table.

5.2 sDataLists Static hash tables

Through the source can be found, looks like a Hash table structure.

Capacity size StripeCount

The real machine capacity is 8, other 64

#ifTARGET_OS_IPHONE && ! TARGET_OS_SIMULATOR
    enum { StripeCount = 8 };
#else
    enum { StripeCount = 64 };
#endif
Copy the code

Generic container array

Here the container is of type SyncList

struct PaddedT {
    T value alignas(CacheLineSize);
};

PaddedT array[StripeCount];
Copy the code

The container element SyncList

struct SyncList {
    SyncData *data;
    spinlock_t lock;
    constexpr SyncList(a) : data(nil), lock(fork_unsafe_lock) {}};Copy the code

Hash subscript indexForPointer

  • addressaddrMoves to the rightfourgetA
  • addressaddrMoves to the rightninegetB
  • AExclusive orBgetC
  • withC ๆจก capacityGet the subscript
    • I made sure I didn’t cross the line
static unsigned int indexForPointer(const void *p) {
    uintptr_t addr = reinterpret_cast<uintptr_t>(p);
    return ((addr >> 4) ^ (addr >> 9)) % StripeCount;
}
Copy the code

Think about it: what if subscripts conflict?

Hashing conflict: The Zipper method (One-way linked List)

The following diagram nicely depicts the hashing situation

5.3 Find TLS Fast Cache (if supported)

Find fast caches through TLS: Thread Local Storage.

5.4 fetch_cache Searching the cache

Internal operation and lookup TLS fast cache are basically the same.

5.5 Cache miss

Traverse the list for lookup

5.6 First entry and linked list operation

The hash conflict is resolved by head insertion

Would it be clearer to go back to the zipper diagram?

Six, SyncCacheItem

As a cached data structure, the lockCount represents how many times this Block has been locked in the current thread (i.e., nested locks).

typedef struct {
    SyncData *data;
    unsigned int lockCount;  // number of times THIS THREAD locked this block
} SyncCacheItem;
Copy the code

Seven,

The design here is very clever. At first, when I found that the size of the container on the real machine was only 8, I still thought, can there only be 8 locks at most? As a result, the data structure of one-way linked list also exists and hash conflicts are resolved by using one-way linked list. Praise really is very exquisite design! ๐Ÿ‘

  • From the source we can also notice a few points:
    • The lock object should not be empty
    • The life of the locked object should be appropriate and not be released in the middle of the process
      • That’s what we useselfThe reason why
    • Try to choose the same OBJ to lock, can makesDataListsSimpler structure

reference

  • There’s more to @synchronized than you ever wanted to know
  • OSSpinLock is no longer secure