preface

The previous articles have taken a peek at the structure of classes by looking at the internal structure of objc_class, and the last one skipped cache_t and looked at the structure of class_data_bits_t by memory translation. Having seen methods, properties, and protocols stored in bits in class_rw_T, this article focuses on the internal structure of cache_T. That is, what data is stored in the class cache? And how do you cache it?

The structure diagram of cache_t

Cache_t code

Before we look at the structure of cache_t, let’s copy the structure code from the source code to understand the internal structure of the cache:

struct cache_t { private: explicit_atomic<uintptr_t> _bucketsAndMaybeMask; // 8 bytes union {struct {explicit_atomic<mask_t> _maybeMask; // 4 bytes #if __LP64__ uint16_t _flags; // 3 bytes #endif uint16_t _occupied; // 2 bytes}; explicit_atomic<preopt_cache_t *> _originalPreoptCache; // 8 bytes}; }Copy the code

chart

According to the above code structure, we can simply draw a structure diagram, as follows: cache_tIn the store_buckets,_mask,_flags,_occupiedInformation such as,_bucketsIt’s in storageselandimpNext, let’s verify with the codecache_tMemory structure of.

LLDB debugging

By the abovecache_tThe code structure, we came up with a rough structure diagram, now we go throughlldbStep by step debugging to see the data obtained.First of all byp/x LGPerson.clasgetLGPersonThe first address0x0000000100008818And then memory shifted by 16 bytes, which is plus0x10get0x0000000100008828, print outcache_tThe structure of theThe $1Through the* $1The outputcache_tFrom the result, the obtained data is consistent with the code defined above, continue to fetch_bucketsAndMaybeMask,_maybeMaskand_originalPreoptCacheAnd see what the output is?

Cache_t; insert; bucket; insert; bucket; bucket_t;

Struct bucket_t {private: struct bucket_t {private: struct bucket_t; // IMP-first is better for arm64e ptrauth and no worse for arm64. // SEL-first is better for armv7* and i386 and x86_64.  #if __arm64__ explicit_atomic<uintptr_t> _imp; explicit_atomic<SEL> _sel; #else explicit_atomic<SEL> _sel; explicit_atomic<uintptr_t> _imp; #endif }Copy the code

Next we look at the output by calling buckets()

You can see the outputselandimp, but the value is nil because we didn’t call the method, keep calling the method, and then the LLDB starts running again (updating the memory data) and prints out

[p say1] has been successfully called, but sel and IMP are still empty.

Through printbuckets()[1]You can seeselandimpIt’s worth something, right herebucketsThere’s a notion that it’sThe hash function.bucketsThere’s more than one in therebucketAnd theThe hash functionIt’s not stored from zero, it’s stored by the function definition, so we have the output at position one, with respect toThe hash functionRelated knowledge points can be consulted separately, this article does not explain too much; Let’s do this by callingsel()You can see the output of the method, calledimp()The error was reported due to missing parameters.

inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls)
Copy the code

Source code analysis

Combined with the LLDB debugging above, we found that refetching the class’s memory after calling a method and then performing the cache_t data retrieval step by step is not easy to debug and cannot be done in a project that does not have the source code. For this reason, we can customize objC_class and cache_t based on the source code design.

Customize the cache structure

typedef uint32_t mask_t;  // x86_64 & arm64 asm are less efficient with 16-bits

// bucket_t
struct kc_bucket_t {
    SEL _sel;
    IMP _imp;
};

// cache_t
struct kc_cache_t {
    struct kc_bucket_t *_bukets; // 8
    mask_t    _maybeMask; // 4
    uint16_t  _flags;  // 2
    uint16_t  _occupied; // 2
};

// class_data_bits_t
struct kc_class_data_bits_t {
    uintptr_t bits;
};

// cache class
struct kc_objc_class {
    Class isa;
    Class superclass;
    struct kc_cache_t cache;
    struct kc_class_data_bits_t bits;
};
Copy the code

Next we do it in main

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        LGPerson *p  = [LGPerson alloc];
        Class pClass = p.class;
        [p say1];

        struct kc_objc_class *kc_class = (__bridge struct kc_objc_class *)(pClass);
        NSLog(@"%hu - %u",kc_class->cache._occupied,kc_class->cache._maybeMask);
        
        for (mask_t i = 0; i<kc_class->cache._maybeMask; i++) {
            struct kc_bucket_t bucket = kc_class->cache._bukets[i];
            NSLog(@"%@ - %pf",NSStringFromSelector(bucket._sel),bucket._imp);
        }
    }
    return 0;
}
Copy the code

Code to run

Call just one method [p say1] first to see the result

The outputsay1Method, and output 2 below(null) - 0x0f,bucketsOpened up 3 capacity, savedsay1Method, the other two are empty,_occupied = 1._maybeMask = 3, then call three methods to see the result

You can see that three methods are printed, but only the output issay3._maybeMaskFrom the original3Increased to7Why did this happen? Next, go to the source code to see the specific logic.

Insert the source code

Let’s take a look at some of the source code for the INSERT () method in cache_t (filter out some judgments and assertions because it’s long)

// Historical fill ratio of 75% (since the new objc Runtime was introduced). Static inline mask_t cache_FILL_ratio (mask_t capacity) {return capacity * 3/4; }Copy the code
Void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld) { bucket_t *oldBuckets = buckets(); bucket_t *newBuckets = allocateBuckets(newCapacity); setBucketsAndMask(newBuckets, newCapacity - 1); If (freeOld) {collect_free(oldBuckets, oldCapacity); }}Copy the code
void cache_t::insert(SEL sel, IMP imp, id receiver) { runtimeLock.assertLocked(); // Use the cache as-is if until we exceed our expected fill ratio. mask_t newOccupied = occupied() + 1; Prepare () = _occupied + 1; 0+1 unsigned oldCapacity = capacity(), capacity = oldCapacity; If (slowpath(isConstantEmptyCache())) {// Cache is read-only. Replace it. // Assign a value to capacity, INIT_CACHE_SIZE: 1 << 2 = 4 Capacity equals 4 for the first time if (! capacity) capacity = INIT_CACHE_SIZE; Reallocate (oldCapacity, capacity, /* freeOld */false); } else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) { // Cache is less than 3/4 or 7/8 Full. Use it as-is. // If the bucket storage capacity +1 <= 75% is not processed, } #if CACHE_ALLOW_FULL_UTILIZATION else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) { // Allow 100% cache utilization for small buckets. Use it as-is. } #endif else { // When the capacity of the bucket exceeds 3/4, the capacity is doubled. Capacity = Capacity? capacity * 2 : INIT_CACHE_SIZE; if (capacity > MAX_CACHE_SIZE) { capacity = MAX_CACHE_SIZE; } // Re-allocate memory to bucket reallocate(oldCapacity, capacity, true); } bucket_t *b = buckets(); mask_t m = capacity - 1; // 4 - 1 = 3 mask_t begin = cache_hash(sel, m); // sel&m mask_t I = begin; // Scan for the first unused slot and insert there. // There is guaranteed to be an empty slot. Do {if (fastPath (b[I].sel() == 0)) {incrementOccupied(); b[i].set<Atomic, Encoded>(b, sel, imp, cls()); return; } if (b[i].sel() == sel) { // The entry was added to the cache by some other thread // before we grabbed the cacheUpdateLock. return; } } while (fastpath((i = cache_next(i, m)) ! = begin)); // cache_next(): hash function, compare and begin are equal, inconsistent continue next loop bad_cache(receiver, (SEL) SEL); #endif // ! DEBUG_TASK_THREADS }Copy the code

conclusion

The insert() method checks for methods in the cache, fetching them from the cache, and inserting them into the cache if not. Sel and IMPs are stored at the buckets in the cache_t function. In this example, setBucketsAndMask is capacity-1, and when the buckets exceed this threshold, they expand their memory capacity by twice. In the second invocation of say1, say2, and say3, only one say3 is output and other methods are (null) -0x0F. The reason is that the memory space of buckets is reclaimed when say3 is called.

That’s how you explore cache_t with an example and source code.