Ios-12. cache_t structure analysis

Summary of ios low-level articles

1. Member composition of the objc_class structure

Cache_t Cache_t Cache_t Cache_t Cache_sel (sel imp);

The members of the objc_class structure are as follows

2. Cache_t source code


struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED// Emulator (x86_64) and MacOS (i386)
    explicit_atomic<struct bucket_t* > _buckets;
    explicit_atomic<mask_t> _mask;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16/ / true machine (arm64)
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
    
    // maskZeroBits=4,bucket=44,
    static constexpr uintptr_t maskShift = 48;
    
    // Reserve four extra bits between mask and bucket, which must be 0
    static constexpr uintptr_t maskZeroBits = 4;
    
    // The maximum number of masks stored
    static constexpr uintptr_t maxMask = ((uintptr_t)1< < (64 - maskShift)) - 1;
    
    // bucket = _maskAndBuckets & bucketsMask;
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
    
    // Ensure we have enough bits for the buckets pointer.
    static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers.");
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 // True (32 bits)
    // _maskAndBuckets stores the mask shift in the low 4 bits, and
    // the buckets pointer in the remainder of the value. The mask
    // shift is the value where (0xffff >> shift) produces the correct
    // mask. This is equal to 16 - log2(cache_size).
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;

    static constexpr uintptr_t maskBits = 4;
    static constexpr uintptr_t maskMask = (1 << maskBits) - 1;
    static constexpr uintptr_t bucketsMask = ~maskMask;
#else
#error Unknown cache mask storage type.
#endif
    
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;

public:
   
    
    struct bucket_t *buckets(a);
    mask_t mask(a);
    mask_t occupied(a);
    void incrementOccupied(a);
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    unsigned capacity(a);
    //....

Copy the code

As you can see from the source code, ObjC4-781 defines cache_t differently depending on the architecture. Macos: I386 simulator: x86 real machine: ARM64

CACHE_MASK_STORAGE == cache_mask_storage_may include emulators and macos

CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16: True machine (arm64)

CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4: true machine (32-bit)

3. View the source code of bucket

struct bucket_t {
private:
#if __arm64__ / / real machine
    //explicit_atomic atomic protection
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else / / the real machine
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
    //....
}
Copy the code

LLDB debugs the cache_T and bucket contents

3.1 define the class


@interface LGPerson : NSObject
@property (nonatomic.copy) NSString *lgName;
@property (nonatomic.strong) NSString *nickName;
- (void)sayHello;
- (void)sayCode;
- (void)sayMaster;
- (void)sayNB;
+ (void)sayHappy;
@end


@implementation LGPerson
- (void)sayHello{
    NSLog(@"LGPerson say : %s",__func__);
}

- (void)sayCode{
    NSLog(@"LGPerson say : %s",__func__);
}

- (void)sayMaster{
    NSLog(@"LGPerson say : %s",__func__);
}

- (void)sayNB{
    NSLog(@"LGPerson say : %s",__func__);
}

+ (void)sayHappy{
    NSLog(@"LGPerson say : %s",__func__);
}
@end
Copy the code

3.2 using class

1. LGPerson *p  = [LGPerson alloc];
2. Class pClass = [LGPerson class];
3. [p sayHello];
4. [p sayCode];
5. [p sayMaster];
Copy the code

3.3 You can query the content and structure of cache_t by running the LLDB command

With a breakpoint set at line 5, you can print the LLDB command to get cache_t as shown below:

Open the target executable file with machoView, check the list of methods to see if the imp value is consistent, as shown below, and find that it is consistent, so the sel-IMP printed is LGPerson instance method

4. Cache write process

4.1 Exploring ideas:

1. In the cache_occupiedAs the method is calledincreasing, from which we can explore the increased function of _occupiedincrementOccupied, its source code implementation is as follows:

void cache_t::incrementOccupied(a) 
{
    _occupied++;
}
Copy the code

1. Global searchincrementOccupied Find one and only one call,cache_t::insert
1. If you set a breakpoint in cache_t:: INSERT, you can find the insert call location incache_fill, while cache_fill is called atlookupMethodInClassAndLoadCache

Conclusion: Based on the above exploration, it can be preliminarily concluded that the write flow of cache is as follows:

Method call –> compile generates objc_msgSend–> pass lookUpImpOrForward according to the class and SEL, look for IMP –> fast lookup –> Fast lookup does not find IMP, enter slow lookup, walk through the list of methods –> find IMP,cache_fill–> Cache_t ::insert–> Modifies the cache_t content

Note :_occupied modifies the value

Calling the init method, _occupied +1
_occupied +1 when the set method is called with an attribute assignment
_occupied is also increased when there are method calls
Reallocate memory,_occupied = 0 returns to zero

4.2 Insert Execution logic

4.3 Cache Memory Allocation Logic

The underlying cache_t::insert objC cache_t::insert

 mask_t newOccupied = occupied() + 1;
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    if (slowpath(isConstantEmptyCache())) {
        if(! capacity) capacity = INIT_CACHE_SIZE;//INIT_CACHE_SIZE=4
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { // CACHE_END_MARKER= 1
        //newOccupied+1<=capacity / 4 * 3
    }
    else {// newOccupied+1 > Capacity / 4 x 3 Requires capacity expansion
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // Double capacity :INIT_CACHE_SIZE=4
        if (capacity > MAX_CACHE_SIZE) { //MAX_CACHE_SIZE<<16; MAX_CACHE_SIZE: MAX_CACHE_SIZE; occupied by MAX_CACHE_SIZE*3/4
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);  // Reapply memory to free up the original memory space
    }
    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;

    do {

        if (fastpath(b[i].sel() == 0)) {
            incrementOccupied();
            b[i].set<Atomic, Encoded>(sel, imp, cls);
            return;
        }

        if (b[i].sel() == sel) {
            return; }}while(fastpath((i = cache_next(i, m)) ! = begin));cache_t::bad_cache(receiver, (SEL)sel, cls);
Copy the code

The first time we call the method,_occupied = 0 and isConstantEmptyCache = true, we request four buckets of memory
Each time objc_msgSend is called, the bucket in the cache will be searched first. If the corresponding IMP is not found in the cache, the slow search method list will be entered, and then the insert method will be called
If newOccupied+1<= Capacity / 4 * 3, perform a bucket insert
If newOccupied+1 > capacity / 4 * 3, reapply for memory for the first time and enter the insert method for the third time, capacity*2 will be expanded _occupied = 0; _occupied = 0; _occupied = 0;
MAX_CACHE_SIZE= 32. A maximum of 32 buckets can be cached.
Capacity =MAX_CACHE_SIZE = 32 If the occupied memory is occupied by 32 x 3/4 (occupied by 24), the occupied memory will be re-allocated to release memory space and discard the cache

4.4 New bucket Insert logic

// Get buckets first address
bucket_t *b = buckets();
// mask = capacity - 1;
mask_t m = capacity - 1;
// Cache_hash computes (sel & mask) The first attempt to insert the index position of the bucket. If the index position is occupied, the insertion position needs to be recalculated
mask_t begin = cache_hash(sel, m);
mask_t i = begin;
// Iterating through buckets' address space, the cache_next loop finds a location to store a new bucket
    do {
        if (fastpath(b[i].sel() == 0)) {
            incrementOccupied();
            b[i].set<Atomic, Encoded>(sel, imp, cls);
            return;
        }
        if (b[i].sel() == sel) {
            // If this location is occupied and the sel stored in the bucket is the sel we need to cache, it does not need to be stored again, which may occur in the case of multi-threaded async
            return; }}while(fastpath((i = cache_next(i, m)) ! = begin));Copy the code

Get the first address of buckets and calculate mask (mask = capacity-1)
Cache_hash Computes (SEL & mask) The index position of the bucket for the first time. If the index position is occupied, the insertion position needs to be recalculated
The do-while loop (cache_next(I, m)) finds an unoccupied location of buckets and stores the buckets that need to be cached. Exit loop by finding empty storage or exit loop by finding cached buckets

Cache_next works as follows:

static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask; // add a new subscript to mask
}

Copy the code

4.5 When reapplying for memory on the real computer, you need to update the _maskAndBuckets in the cache (call setBucketsAndMask).

In order to optimize the memory, the mask value and buckets address of arm64 occupy 64 bit space together. The bit fields are stored in memory as shown in the following figure

Therefore, we also need to perform some displacement operations when caching buckets, which are as follows:

5. Explore cache_t away from the source code

Given the underlying structure, we can customize a similar structure from the underlying objC_class,cache_t, and bucket_t structures in the source code format and type. Then we can convert the class to our own structure and see the underlying structure and transformation process clearly

5.1 Preparing class and call source code

Define LGPerson class

@interface LGPerson : NSObject
@property (nonatomic.copy) NSString *lgName;
@property (nonatomic.strong) NSString *nickName;

- (void)say1;
- (void)say2;
- (void)say3;
- (void)say4;
- (void)say5;
- (void)say6;
- (void)say7;

+ (void)sayHappy;

@end


@implementation LGPerson

- (void)say1{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say2{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say3{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say4{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say5{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say6{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say7{
    NSLog(@"LGPerson say : %s",__func__);
}


+ (void)sayHappy{
    NSLog(@"LGPerson say : %s",__func__);
}
@end

Copy the code

Custom structobjc_class.cache_t.bucket_t, and calling code

#import "LGPerson.h"
#import <objc/runtime.h>

typedef uint32_t mask_t;

struct lg_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct lg_cache_t {
    struct lg_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct lg_class_data_bits_t {
    uintptr_t bits;
};

struct lg_objc_class {
    Class ISA; // Notice that objc_class has an ISA
    Class superclass;
    struct lg_cache_t cache;
    struct lg_class_data_bits_t bits;
};


int main(int argc, const char * argv[]) {
    @autoreleasepool {
        LGPerson *p  = [LGPerson alloc];
        Class pClass = [LGPerson class];  // objc_clas
        [p say1];
        [p say2];
        struct lg_objc_class *lg_pClass = (__bridge struct lg_objc_class *)(pClass);
               NSLog(@"(1)_occupied: %hu - _mask:%u",lg_pClass->cache._occupied,lg_pClass->cache._mask);
               for (mask_t i = 0; i<lg_pClass->cache._mask; i++) {
                   // Prints the bucket
                   struct lg_bucket_t bucket = lg_pClass->cache._buckets[i];
                   NSLog(@"%@ - %p".NSStringFromSelector(bucket._sel),bucket._imp);
               }

        [p say3];
        NSLog(@"(2)_occupied: %hu - _mask:%u",lg_pClass->cache._occupied,lg_pClass->cache._mask);
        for (mask_t i = 0; i<lg_pClass->cache._mask; i++) {
            // Prints the bucket
            struct lg_bucket_t bucket = lg_pClass->cache._buckets[i];
            NSLog(@"%@ - %p".NSStringFromSelector(bucket._sel),bucket._imp);
        }
        [p say4];
         

       NSLog(@"(3) _occupied: %hu - _mask:%u",lg_pClass->cache._occupied,lg_pClass->cache._mask);
              for (mask_t i = 0; i<lg_pClass->cache._mask; i++) {
                  // Prints the bucket
                  struct lg_bucket_t bucket = lg_pClass->cache._buckets[i];
                  NSLog(@"%@ - %p".NSStringFromSelector(bucket._sel),bucket._imp);
              }
        [p say1];
        [p say2];
        NSLog(@"(4) _occupied: %hu - _mask:%u",lg_pClass->cache._occupied,lg_pClass->cache._mask);
               for (mask_t i = 0; i<lg_pClass->cache._mask; i++) {
                   // Prints the bucket
                   struct lg_bucket_t bucket = lg_pClass->cache._buckets[i];
                   NSLog(@"%@ - %p".NSStringFromSelector(bucket._sel),bucket._imp);
               }

        
        NSLog(@"Hello, World!");
    }
    return 0;
}

Copy the code

5.2 Printout parsing

_occupied: number of buckets used by the cache buckets (number of methods cached in the cache). The value is 0 when the object is created, and will be cleared after the memory is applied for again. _occupied++ is used when a bucket is added
_mask: the total capacity of buckets is -1(the number of buckets that can be stored is -1). When four buckets are applied for for the first time, _mask =4-1=3.
If you apply for buckets’ memory again, the memory of the former buckets will be emptied,_occupied will be zeroed out, and the bucket cached in the cache will be discarded
The new bucket insertion sequence, which is not sequential, computes the initial query location based on cache_hash and loops cache_next to find an empty location store