preface

This document is based on the X86_64 schema. Some contents vary depending on the schema.

1. `cache_t`parsing

We know that iOS method calls are a process of looking for an IMP(method pointer) in memory through SEL (method number), but if there are a large number of methods, then each call to any method would require traversal of all methods, which is inefficient. In order to improve efficiency and make the response faster, cache_T structures appear. The pointer in cache_t points to the first address of the hash list stored in the bucket_t structure of SEL and IMP of the invoked method (converted to decimal, storing only the first address saves memory and does not cause the class to grow indefinitely, and subsequent values are shifted through memory) for subsequent methods to find.

Cache_t simple structure diagram:

1.1 `cache_t`Structure part source parsing

struct cache_t {
private:
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask;            / / 8
    union {
        struct {
            explicit_atomic<mask_t>    _maybeMask;              / / 4
#if __LP64__
            uint16_t                   _flags;                  / / 2
#endif
            uint16_t                   _occupied;               / / 2
        };
        explicit_atomic<preopt_cache_t *> _originalPreoptCache; / / 8
    };
    
    // The cache is empty and is used for the first time
    bool isConstantEmptyCache() const;
    bool canBeFreed() const;
    // The total available capacity is capacity - 1
    mask_t mask() const;
    
    // Double the capacity
    void incrementOccupied();
    // Set buckets and mask
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    // Re-create the memory
    void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
    // Collect oldBuckets according to oldCapacity
    void collect_free(bucket_t *oldBuckets, mask_t oldCapacity);
    
public:
    // The total capacity opened
    unsigned capacity() const;
    / / to get buckets
    struct bucket_t *buckets() const;
    / / for the class
    Class cls() const;
    // Get the number of caches
    mask_t occupied() const;
    // Insert the called method into the memory area where the buckets are located
    void insert(SEL sel, IMP imp, id receiver);
    
    // The code is omitted in many places
}
Copy the code

1.2 `cache_t`Partial member variable resolution

_bucketsAndMaybeMask: Store different information according to different architectures,X86_64storebuckets.arm64high16A storagemaskLow,48positionbuckets.
_maybeMask: Capacity of the current cache,arm64Not used under architecture.
_occupied: Indicates the number of methods in the cache.

_bucketsAndMaybeMask for X86_64 architecture

(lldb) p/x XJPerson.class
(Class) $0 = 0x0000000100008308 XJPerson
(lldb) p/x 0x0000000100008308 + 0x10
(long) $1 = 0x0000000100008318
(lldb) p (cache_t *)0x0000000100008318
(cache_t *) $2 = 0x0000000100008318
(lldb) p *$2
(cache_t) $3 = {
  _bucketsAndMaybeMask = {
    std::__1::atomic<unsigned long> = {
      Value = 4298437504
    }
  }
   = {
     = {
      _maybeMask = {
        std::__1::atomic<unsigned int> = {
          Value = 0
        }
      }
      _flags = 32784
      _occupied = 0
    }
    _originalPreoptCache = {
      std::__1::atomic<preopt_cache_t *> = {
        Value = 0x0000801000000000
      }
    }
  }
}
(lldb) p $3.buckets()
(bucket_t *) $4 = 0x000000010034f380
// Output _bucketsAndMaybeMask in hexadecimal
// Restore buckets address
(lldb) p/x 4298437504                
(long) $5 = 0x000000010034f380       

$4 == $5, and the _bucketsAndMaybeMask pointer points to the first address of buckets
Copy the code

Illustration:

1.3 `cache_t`Analysis of some key functions

1.3.1 `cache_t::insert`Function analysis

Gets the number of methods currently cached (0 for the first time), then +1.
Gets the cache capacity from, the first time is 0.
Determine if it is the first cache method, the first cache is openedCapacity (1 << INIT_CACHE_SIZE_LOG2 (X86_64 is 2, arm64 is 1)) * sizeof(bucket_t)The size of the memory space will bebucket_t *First address save_bucketsAndMaybeMaskThat will benewCapacity - 1themaskdeposit_maybeMask._occupiedSet it to 0.
If it is not the first cache, determine whether it needs to be expanded (the cache capacity exceeds 3/4 or 7/8 of the total capacity), double the capacity if it needs to be expanded (but not more than the maximum), and then redo the memory as in step 3 and reclaim the old cache.
The hash algorithm calculates the location of the method cache,do{} while()Loop to determine whether the current location can be stored, if the hash conflict, keep hashing until the location can be stored, if not found, callbad_cacheFunction.

// Omit part of the code for length reasons
void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    // Get the number of methods currently cached (0 for the first time), then +1
    mask_t newOccupied = occupied() + 1;
    // Get the cache capacity from it, the first time being 0
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    // Check whether it is the first cache method
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        INIT_CACHE_SIZE = 1 << INIT_CACHE_SIZE_LOG2,
        // INIT_CACHE_SIZE_LOG2 has different values for different schemas,
        // X86_64 is 2, arm64 is 1
        if(! capacity) capacity = INIT_CACHE_SIZE;// Create a new memory space with capacity * sizeof(bucket_t);
        // Store the first address of 'bucket_t *' in '_bucketsAndMaybeMask',
        // Store 'mask' of 'newCapacity - 1' in '_maybeMask',
        // Occupied is set to 0
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    // Do not exceed 3/4 or 7/8 of capacity (depending on the architecture), normal use
    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 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 {
        // If the capacity exceeds 3/4 or 7/8, double the capacity expansion
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        MAX_CACHE_SIZE = 1 << MAX_CACHE_SIZE_LOG2, MAX_CACHE_SIZE_LOG2 = 16
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        // Create a new memory space with capacity * sizeof(bucket_t);
        // Store the first address of 'bucket_t *' in '_bucketsAndMaybeMask',
        // Store 'mask' of 'newCapacity - 1' in '_maybeMask',
        // The _occupied function is set to 0
        reallocate(oldCapacity, capacity, true);
    }
    
    / / create bucket_t
    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    // Hash algorithm to calculate the memory bit
    mask_t begin = cache_hash(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)) { // I is empty and can be inserted
            // _occupied++, number of cached methods +1incrementOccupied(); [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));// Hash conflict, hash again

    bad_cache(receiver, (SEL)sel);
#endif / /! DEBUG_TASK_THREADS
}
Copy the code

1.3.2 `cache_fill_ratio`Function analysis

The load factor is the bucket_T memory space usage ratio. Different architectures have different policies. The value of CAPACITY x 7/8 for ARM64 is capacity x 3/4 for X86_64.

A 3/4 occupancy rate is good for space utilization and prevents hash collisions.
7/8 Increasing the cache usage reduces the fragmentation and waste of space in the cache, but at the cost of a corresponding increase in hash collisions.

// X86_64
static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 3 / 4;
}
// arm64
// 87.5%
static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 7 / 8;
}
Copy the code

1.3.3 `reallocate`Function analysis

New memory space newCapacity * sizeof(bucket_t), bucket_t * first address stored in _bucketsAndMaybeMask, newCapacity – 1 mask stored in _maybeMask, FreeOld indicates whether to reclaim the old memory. The value is false for the first insert method and true for subsequent expansion. Call the collect_free function to clear and reclaim the old memory.

ALWAYS_INLINE
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = buckets();
    bucket_t *newBuckets = allocateBuckets(newCapacity);

    // Cache's old contents are not propagated. 
    // This is thought to save cache memory at the cost of extra cache fills.
    // fixme re-measure this

    ASSERT(newCapacity > 0);
    ASSERT((uintptr_t)(mask_t)(newCapacity- 1) == newCapacity- 1);

    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if(freeOld) { collect_free(oldBuckets, oldCapacity); }}Copy the code

1.3.4 `allocateBuckets`Function analysis

Open up newCapacity * sizeof (bucket_t) the size of memory space, create a new bucket_t pointer, CACHE_END_MARKER to 1 (__arm__ | | __x86_64__ | | __i386__ architecture). It stores the end flag, which is a bucket_t pointer at capacity-1 with SEL 1, IMP newBuckets or newBuckets 1, and class nil, depending on the architecture.

#if CACHE_END_MARKER

bucket_t *cache_t::endMarker(struct bucket_t *b, uint32_t cap)
{
    return (bucket_t *)((uintptr_t)b + bytesForCapacity(cap)) - 1;
}

bucket_t *cache_t::allocateBuckets(mask_t newCapacity)
{
    // Allocate one extra bucket to mark the end of the list.
    // This can't overflow mask_t because newCapacity is a power of 2.
    bucket_t *newBuckets = (bucket_t *)calloc(bytesForCapacity(newCapacity), 1);

    bucket_t *end = endMarker(newBuckets, newCapacity);

#if __arm__
    // End marker's sel is 1 and imp points BEFORE the first bucket.
    // This saves an instruction in objc_msgSend.
    end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)(newBuckets - 1), nil);
#else
    // End marker's sel is 1 and imp points to the first bucket.
    end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity);

    return newBuckets;
}

#else 
// The M1 version of the iMac goes here, because the M1 was first created with a capacity of 2 and a ratio of 7/8, so endMarker is not set
bucket_t *cache_t::allocateBuckets(mask_t newCapacity)
{
    if (PrintCaches) recordNewCache(newCapacity);

    return (bucket_t *)calloc(bytesForCapacity(newCapacity), 1);
}
#endif
Copy the code

Expansion policy Description:

Why empty the oldBuckets instead of expanding the space and attaching new caches later?

Answer: The memory already opened cannot be changed. This is actually a false capacity expansion, as a new memory is opened instead of the old one. First, if you take out the old buckets and put them in the new one, it consumes performance and time. Second, Apple’s caching strategy is that newer is better. For example, after method A is invoked once, the probability of method A being invoked again is very low. Therefore, it is meaningless to keep the cache after capacity expansion. If method A is invoked again, the cache will be used again until the next capacity expansion. Third, prevent the infinite number of methods to cache, resulting in slow method lookup.

1.3.5 `setBucketsAndMask`Function analysis

willbucket_t *First address save_bucketsAndMaybeMask.
willnewCapacity - 1themaskdeposit_maybeMask.
_occupiedSet it to 0 because I just set itbucketsThere is no real caching method.

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    // objc_msgSend uses mask and buckets with no locks.
    // It is safe for objc_msgSend to see new buckets but old mask.
    // (It will get a cache miss but not overrun the buckets' bounds).
    // It is unsafe for objc_msgSend to see old buckets and new mask.
    // Therefore we write new buckets, wait a lot, then write new mask.
    // objc_msgSend reads mask first, then buckets.

#ifdef __arm__
    // ensure other threads see buckets contents before buckets pointer
    mega_barrier();

    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_relaxed);

    // ensure other threads see new buckets before new mask
    mega_barrier();

    _maybeMask.store(newMask, memory_order_relaxed);
    _occupied = 0;
#elif __x86_64__ || i386
    // ensure other threads see buckets contents before buckets pointer
    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_release);

    // ensure other threads see new buckets before new mask
    _maybeMask.store(newMask, memory_order_release);
    _occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}
Copy the code

1.3.6 `collect_free`Function analysis

Recycle memory by emptying the contents of the memory address passed in.

void cache_t::collect_free(bucket_t *data, mask_t capacity)
{
#if CONFIG_USE_CACHE_LOCK
    cacheUpdateLock.assertLocked();
#else
    runtimeLock.assertLocked();
#endif

    if (PrintCaches) recordDeadCache(capacity);

    _garbage_make_room ();
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    garbage_refs[garbage_count++] = data;
    cache_t::collectNolock(false);
}
Copy the code

1.3.7 `cache_hash`Function analysis

Hash algorithm, calculates where the method inserts.

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    uintptr_t value = (uintptr_t)sel;
#if CONFIG_USE_PREOPT_CACHES
    value ^= value >> 7;
#endif
    return (mask_t)(value & mask);
}
Copy the code

1.3.8 `cache_next`Function analysis

Re-hash algorithm, used to re-calculate the position of the method inserted after a hash collision.

#if CACHE_END_MARKER
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
#elif __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i- 1 : mask;
}
#else
#error unexpected configuration
#endif
Copy the code

2 `bucket_t`parsing

2.1 `bucket_t`Structure part source parsing

struct bucket_t {
private:
    // 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; // Imp address stored in uintPtr_t (unsigned long) format
    explicit_atomic<SEL> _sel;       // sel
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
    
    // uintPtr_t newImp ^ (uintPtr_t) CLS
    // IMP address to 10 ^ class address to 10
    // Imp is stored in bucket_t in uintptr_t (unsigned long) format
    // Sign newImp, with &_imp, newSel, and cls as modifiers.
    uintptr_t encodeImp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, IMP newImp, UNUSED_WITHOUT_PTRAUTH SEL newSel, Class cls) const {
        if(! newImp)return 0;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
        return (uintptr_t)
            ptrauth_auth_and_resign(newImp,
                                    ptrauth_key_function_pointer, 0,
                                    ptrauth_key_process_dependent_code,
                                    modifierForSEL(base, newSel, cls));
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
        // IMP address to 10 ^ class address to 10
        return (uintptr_t)newImp ^ (uintptr_t)cls;
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
        return (uintptr_t)newImp;
#else
#error Unknown method cache IMP encoding.
#endif
    }
    
public:
    / / return sel
    inline SEL sel() const { return _sel.load(memory_order_relaxed); }
    
    // uintptr_t CLS
    // Imp address decimal ^ class address decimal, and then converted to IMP type
    C = a ^ b; a = c ^ b; -> b ^ a ^ b = a
    inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const {
        uintptr_t imp = _imp.load(memory_order_relaxed);
        if(! imp)return nil;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
        SEL sel = _sel.load(memory_order_relaxed);
        return (IMP)
            ptrauth_auth_and_resign((const void *)imp,
                                    ptrauth_key_process_dependent_code,
                                    modifierForSEL(base, sel, cls),
                                    ptrauth_key_function_pointer, 0);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
        // Imp address decimal ^ class address decimal, and then converted to IMP type
        return (IMP)(imp ^ (uintptr_t)cls);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
        return (IMP)imp;
#else
#error Unknown method cache IMP encoding.
#endif
    }
    
    // This is just a declaration, see the following function parse
    void set(bucket_t *base, SEL newSel, IMP newImp, Class cls);

// Omit part of the code for length reasons
}
Copy the code

2.2 `bucket_t`Member variable resolution

_sel, method sel.
_imp, method to implement the address of the decimal, required^To the decimal of the class address, and then to theIMPType.

2.3 `bucket_t`Analysis of some key functions

2.3.1 `sel`Function analysis

Get the sel of bucket_.

/ / return sel
    inline SEL sel() const { return _sel.load(memory_order_relaxed); }
Copy the code

2.3.2 `encodeImp`Function analysis

IMP code, IMP address decimal ^ class address decimal. Imp is stored in bucket_t in uintPtr_t (unsigned long) format.

// uintPtr_t newImp ^ (uintPtr_t) CLS
    // IMP address to 10 ^ class address to 10
    // Imp is stored in bucket_t in uintptr_t (unsigned long) format
    // Sign newImp, with &_imp, newSel, and cls as modifiers.
    uintptr_t encodeImp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, IMP newImp, UNUSED_WITHOUT_PTRAUTH SEL newSel, Class cls) const {
        if(! newImp)return 0;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
        return (uintptr_t)
            ptrauth_auth_and_resign(newImp,
                                    ptrauth_key_function_pointer, 0,
                                    ptrauth_key_process_dependent_code,
                                    modifierForSEL(base, newSel, cls));
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
        // IMP address to 10 ^ class address to 10
        return (uintptr_t)newImp ^ (uintptr_t)cls;
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
        return (uintptr_t)newImp;
#else
#error Unknown method cache IMP encoding.
#endif
    }
Copy the code

2.3.3 `imp`Function analysis

The IMP decodes and returns the IMP address in decimal to the class address in decimal, which is converted to the IMP type (the preceding encoding functions constitute the symmetric codec).

Codec principle: a twice ^ b, or equal to a, namely: C = a ^ b; a = c ^ b; -> b ^ a ^ b = a.

The class is the salt of the algorithm. The class is the salt of the algorithm. The imp belongs to the class.

// uintptr_t CLS
    // Imp address decimal ^ class address decimal, and then converted to IMP type
    B ^ a ^ b = a
    inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const {
        uintptr_t imp = _imp.load(memory_order_relaxed);
        if(! imp)return nil;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
        SEL sel = _sel.load(memory_order_relaxed);
        return (IMP)
            ptrauth_auth_and_resign((const void *)imp,
                                    ptrauth_key_process_dependent_code,
                                    modifierForSEL(base, sel, cls),
                                    ptrauth_key_function_pointer, 0);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
        // Imp address decimal ^ class address decimal, and then converted to IMP type
        return (IMP)(imp ^ (uintptr_t)cls);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
        return (IMP)imp;
#else
#error Unknown method cache IMP encoding.
#endif
    }
Copy the code

2.3.4 `bucket_t::set`Function analysis

Set sel, IMP, and class for bucket_t.

void bucket_t::set(bucket_t *base, SEL newSel, IMP newImp, Class cls)
{
    ASSERT(_sel.load(memory_order_relaxed) == 0 ||
           _sel.load(memory_order_relaxed) == newSel);

    // objc_msgSend uses sel and imp with no locks.
    // It is safe for objc_msgSend to see new imp but NULL sel
    // (It will get a cache miss but not dispatch to the wrong place.)
    // It is unsafe for objc_msgSend to see old imp and new sel.
    // Therefore we write new imp, wait a lot, then write new sel.
    
    uintptr_t newIMP = (impEncoding == Encoded
                        ? encodeImp(base, newImp, newSel, cls)
                        : (uintptr_t)newImp);

    if (atomicity == Atomic) {
        _imp.store(newIMP, memory_order_relaxed);
        
        if(_sel.load(memory_order_relaxed) ! = newSel) {#ifdef __arm__
            mega_barrier();
            _sel.store(newSel, memory_order_relaxed);
#elif __x86_64__ || __i386__
            _sel.store(newSel, memory_order_release);
#else
#error Don't know how to do bucket_t::set on this architecture.
#endif}}else{ _imp.store(newIMP, memory_order_relaxed); _sel.store(newSel, memory_order_relaxed); }}Copy the code

2.4 `imp`codec`lldb`Debug verification

incache_t::insertFunction of thedo{} while()In a loopbucket_t::setAdd the relevant code after the function.

inimpFunction to add a breakpoint andlldbDebug validation.

(lldb) p imp
(uintptr_t) $0 = 48640
(lldb) p (IMP)(imp ^ (uintptr_t)cls)  // Direct decoding
(IMP) $1 = 0x0000000100003d20 (KCObjcBuild`-[XJPerson smileToLife])
// Next step by step decoding, and again encoding verification
(lldb) p (uintptr_t)cls
(uintptr_t) $2 = 4295000864
(lldb) p 48640 ^ 4295000864
(long) $3 = 4294982944
(lldb) p/x 4294982944
(long) $4 = 0x0000000100003d20
(lldb) p (IMP)0x0000000100003d20
// Decoded successfully
(IMP) $5 = 0x0000000100003d20 (KCObjcBuild`-[XJPerson smileToLife])
// Code validation again
(lldb) p 4294982944 ^ 4295000864
(long) $6 = 48640
Copy the code

Illustration:

3. Verify LLDB dynamic debugging`cache_t`structure

3.1 Sample Code

@interface XJPerson : NSObject

- (void)loveEveryone;

- (void)smileToLife;

- (void)takeCareFamily;

@end

@implementation XJPerson

- (void)loveEveryone
{
    NSLog(@"%s", __func__);
}

- (void)smileToLife
{
    NSLog(@"%s", __func__);
}

- (void)takeCareFamily
{
    NSLog(@"%s", __func__);
}

@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {

        XJPerson *p  = [XJPerson alloc];
        Class pClass = [XJPerson class];
        NSLog(@ "% @",pClass);
        
    }
    return 0;
}
Copy the code

3.2 LLDB Debugging procedure

(lldb) p/x XJPerson.class
(Class) $0 = 0x0000000100008308 XJPerson
(lldb) p/x 0x0000000100008308 + 0x10         // Offset 16 bytes and get the cache_t pointer (ISA8 bytes, Superclass8 bytes)
(long) $1 = 0x0000000100008318
(lldb) p (cache_t *)0x0000000100008318       // Type conversion
(cache_t *) $2 = 0x0000000100008318          
(lldb) p *$2                                 // Value cache output
(cache_t) $3 = {
  _bucketsAndMaybeMask = {
    std::__1::atomic<unsigned long> = {
      Value = 4298437504
    }
  }
   = {
     = {
      _maybeMask = {                        // _maybeMask- The cache capacity is 0, because the method has not been called yet, so no cache space has been opened
        std::__1::atomic<unsigned int> = {
          Value = 0
        }
      }
      _flags = 32784
      _occupied = 0                        // _occupied- Number of cached methods that are not currently called
    }
    _originalPreoptCache = {
      std::__1::atomic<preopt_cache_t *> = {
        Value = 0x0000801000000000
      }
    }
  }
}
(lldb) p [p loveEveryone]                  // LLDB calls the method
2021- 0626 - 21:00:31.415209+0800 KCObjcBuild[2793:42005] -[XJPerson loveEveryone]
(lldb) p *$2                               // Value cache output again
(cache_t) $4 = {
  _bucketsAndMaybeMask = {
    std::__1::atomic<unsigned long> = {
      Value = 4302872208
    }
  }
   = {
     = {
      _maybeMask = {    // _maybeMask- Cache size 7,
                        // The x86_64 schema should have a capacity of 4 for the first time,
                        // There is an unexpected result. The reasons will be analyzed later
        std::__1::atomic<unsigned int> = {
          Value = 7
        }
      }
      _flags = 32784
      _occupied = 1     // _occupied- number of cached methods
    }
    _originalPreoptCache = {
      std::__1::atomic<preopt_cache_t *> = {
        Value = 0x0001801000000007
      }
    }
  }
}
(lldb) p [p takeCareFamily]             // Call the two methods again
2021- 0626 - 21:00:55.714319+0800 KCObjcBuild[2793:42005] -[XJPerson takeCareFamily]
(lldb) p [p smileToLife]
2021- 0626 - 21:01:16.249795+0800 KCObjcBuild[2793:42005] -[XJPerson smileToLife]
(lldb) p *$2                            // Value cache output again
(cache_t) $5 = {
  _bucketsAndMaybeMask = {
    std::__1::atomic<unsigned long> = {
      Value = 4302872208
    }
  }
   = {
     = {
      _maybeMask = {    // _maybeMask- Cache size 7,
                        // The x86_64 schema should have a capacity of 4 for the first time,
                        // There is an unexpected result. The reasons will be analyzed later
        std::__1::atomic<unsigned int> = {
          Value = 7
        }
      }
      _flags = 32784
      _occupied = 5     // _occupied- number of cached methods
                        // A total of three methods were called, but five were cached
                        // Indicates that other unknown methods may be cached
    }
    _originalPreoptCache = {
      std::__1::atomic<preopt_cache_t *> = {
        Value = 0x0005801000000007}}}}// Memory translation
// Take the bucket_t in the first position
(lldb) p $5.buckets()[0]
(bucket_t) $6 = {
  _sel = {
    std::__1::atomic<objc_selector *> = "" {
      Value = ""
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 3359864
    }
  }
}
(lldb) p $6.sel()
(SEL) $7 = "respondsToSelector:"    // The first position is -[NSObject respondsToSelector:], which is not called by me, but inserted by the LLDB system
(lldb) p $6.imp(nil, pClass)
(IMP) $8 = 0x000000010033c770 (libobjc.A.dylib`-[NSObject respondsToSelector:] at NSObject.mm:2307)

// Take the bucket_t in the second position
(lldb) p $5.buckets()[1]
(bucket_t) $9 = {
  _sel = {
    std::__1::atomic<objc_selector *> = "" {
      Value = ""
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 48728
    }
  }
}
(lldb) p $9.sel()
(SEL) $10 = "takeCareFamily"    // The second position is -[XJPerson takeCareFamily]
(lldb) p $9.imp(nil, pClass)
(IMP) $11 = 0x0000000100003d50 (KCObjcBuild`-[XJPerson takeCareFamily])

// Take the third position bucket_t
(lldb) p $5.buckets()[2]
(bucket_t) $12 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null) {
      Value = (null)
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 0
    }
  }
}
(lldb) p $12.sel()            // The third position is empty and the method is not cached yet
(SEL) $13 = <no value available>

// Take the fourth position bucket_t
(lldb) p $5.buckets()[3]
(bucket_t) $14 = {
  _sel = {
    std::__1::atomic<objc_selector *> = "" {
      Value = ""
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 48680
    }
  }
}
(lldb) p $14.sel()
(SEL) $15 = "smileToLife"    // The fourth location is -[XJPerson smileToLife]
(lldb) p $14.imp(nil, pClass)
(IMP) $16 = 0x0000000100003d20 (KCObjcBuild`-[XJPerson smileToLife])

// Take the fifth position bucket_t
(lldb) p $5.buckets()[4]
(bucket_t) $17 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null) {
      Value = (null)
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 0
    }
  }
}
(lldb) p $17.sel()    // The fifth position is empty and the method is not cached yet
(SEL) $18 = <no value available>

// Take the sixth position bucket_t
(lldb) p $5.buckets()[5]
(bucket_t) $19 = {
  _sel = {
    std::__1::atomic<objc_selector *> = "" {
      Value = ""
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 3358936
    }
  }
}
(lldb) p $19.sel()
(SEL) $20 = "class"     // The sixth position is -[NSObject class]
(lldb) p $19.imp(nil, pClass)
(IMP) $21 = 0x000000010033c3d0 (libobjc.A.dylib`-[NSObject class] at NSObject.mm:2243)

// Take the seventh position bucket_t
(lldb) p $5.buckets()[6]
(bucket_t) $22 = {
  _sel = {
    std::__1::atomic<objc_selector *> = "" {
      Value = ""
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 49144
    }
  }
}
(lldb) p $22.sel()
(SEL) $23 = "loveEveryone"    // The seventh position is -[XJPerson loveEveryone]
(lldb) p $22.imp(nil, pClass)
(IMP) $24 = 0x0000000100003cf0 (KCObjcBuild`-[XJPerson loveEveryone])
(lldb) 
Copy the code

Illustration:

3.3 ANALYSIS of LLDB Debugging Results

Call a method,_occupiedfor1._maybeMaskfor7(The first discovery was actually4), according to the frontAllocateBuckets function parsingIt’s mentioned in thereCACHE_END_MARKERfor1(__arm__ || __x86_64__ || __i386__Architecture for1), will be storedendTag, plus call-[XJPerson loveEveryone]Methods beforelldbInsert the-[NSObject class]and-[NSObject respondsToSelector:]Method in insert-[XJPerson loveEveryone]It will be judged that it has exceededThree quarters ofCapacity, so insert-[XJPerson loveEveryone]Method was expanded, the previous cache was cleared, and the new cache was stored-[XJPerson loveEveryone]Methods.
After calling two more methods,_occupiedfor5._maybeMaskfor7Because thelldbInserted again before our method call-[NSObject class]and-[NSObject respondsToSelector:]Method. This, in addition to one of the methods already cached above, is the method in the cache5A.

3.4 `lldb`Automatic insert method validation

Verification method 1:

incache_t::insertFunction to add printoutsel,imp,receiver.

Run the source code after the creationXJPersonThe object of the classp1And then I break the break pointXcodeThe console is going to output a lot of information, which is not what we want, so just clear it.

Then use thelldbcallp1Object methodsp [p1 smileToLife]And thenp p1The outputp1Object to compare the console printout methodreceiverandp1You’ll find outlldbIt does insert before we call the methodrespondsToSelector:andclassMethods.

Conclusion:

lldbIt may be necessary to insert the corresponding other method before calling the method entered by the user, which is now being testedX86_64Architecture, which is inserted every time the underlying system creates a cacheendMarkeraddlldbWe insert two methods before our method call, and when our method is inserted, the underlying layer determines that the cache usage ratio exceeds the set ratio, expands the size, and stores the method we call in the new cachesmileToLife, and empty and reclaim the old cache, which is why a method is called before_occupiedfor1._maybeMaskfor7In the case.

Verification method 2:

incache_t::insertAdd the code in the function before the expansion judgment, and output everything in the cache when we insert the method we are callingbucketthesel,impAnd the address.

Run the source code after the creationXJPersonThe object of the classp1Then break the break point and uselldbcallp1Object methodsp [p1 smileToLife], the console will output all of the cachebucketCan be clearly seenclassMethods,respondsToSelector:Methods andselfor1Imp is the first address of the cache,ClassforniltheendMarker.

4. Counterfeit source debugging`cache_t`

4.1 Counterfeit source debugging advantages

Counterfeit source debugging mainly solves three problems:

No source code, or downloaded source code can not run debugging directly.
Don’tlldbDebugging, andlldbDebugging is troublesome and the process is tedious.
Suitable for small scale sampling test.

4.2 Imitation process:

Mimic the source definitionxj_objc_classStructure to add hidden member variablesisa.
Mimic the source definitionxj_class_data_bits_tStructure, only keepbitsMember variables.
Mimic the source definitionxj_bucket_tStructure.
renameuint32_tformask_t.
Mimic the source definitionxj_cache_tStructure, retain only a few member variables that need to be used, and will source_bucketsAndMaybeMaskI’m going to replace it withxj_bucket_tPointer.
instantiationXJPersonClass instance object, calls method, and willXJPersonStrong class intoxj_objc_classPointer.
Output method cache number and cache capacity.
forLoop the output cache methodselandimp.

4.3 Example code:

struct xj_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct xj_class_data_bits_t {
    uintptr_t bits;
};

typedef uint32_t mask_t;
struct xj_cache_t {
    struct xj_bucket_t *_buckets;   / / 8
    mask_t              _maybeMask; / / 4
    uint16_t            _flags;     / / 2
    uint16_t            _occupied;  / / 2
};

struct xj_objc_class {
    Class isa;
    Class superclass;
    struct xj_cache_t cache;             // formerly cache pointer and vtable
    struct xj_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        XJPerson *person = [XJPerson alloc];
        Class pClass = person.class;
        [person likeFood];
        [person enjoyLife];
        [person smileToLife];
        [person likeSwimming];
        [person loveEveryone];
        [person takeCareFamily];
        
        struct xj_objc_class *xj_class = (__bridge struct xj_objc_class *)(pClass);
        
        NSLog(@"occupied = %hu - mask = %u", xj_class->cache._occupied, xj_class->cache._maybeMask);
        
        for (mask_t i = 0; i < xj_class->cache._maybeMask; i++) {
            struct xj_bucket_t bucket = xj_class->cache._buckets[i];
            NSLog(@"%@ - %pf".NSStringFromSelector(bucket._sel), bucket._imp);
        }
        
        NSLog(@"Hello, World!");
    }
    return 0; } * * * * * * * * * * * * * * * * * * * * * * * * printing * * * * * * * * * * * * * * * * * * * * * * * *2021- 0627 - 16:16:14.561903+0800 cache_tAnalysis[2857:57028] -[XJPerson likeFood]
2021- 0627 - 16:16:14.562789+0800 cache_tAnalysis[2857:57028] -[XJPerson enjoyLife]
2021- 0627 - 16:16:14.562965+0800 cache_tAnalysis[2857:57028] -[XJPerson smileToLife]
2021- 0627 - 16:16:14.563129+0800 cache_tAnalysis[2857:57028] -[XJPerson likeSwimming]
2021- 0627 - 16:16:14.563242+0800 cache_tAnalysis[2857:57028] -[XJPerson loveEveryone]
2021- 0627 - 16:16:14.563362+0800 cache_tAnalysis[2857:57028] -[XJPerson takeCareFamily]
2021- 0627 - 16:16:14.563403+0800 cache_tAnalysis[2857:57028] occupied = 4 - mask = 7
2021- 0627 - 16:16:14.563495+0800 cache_tAnalysis[2857:57028] takeCareFamily - 0xba68f
2021- 0627 - 16:16:14.563553+0800 cache_tAnalysis[2857:57028] likeSwimming - 0xbdf8f
2021- 0627 - 16:16:14.563585+0800 cache_tAnalysis[2857:57028] (null) - 0x0f
2021- 0627 - 16:16:14.563620+0800 cache_tAnalysis[2857:57028] smileToLife - 0xbab8f
2021- 0627 - 16:16:14.563648+0800 cache_tAnalysis[2857:57028] (null) - 0x0f
2021- 0627 - 16:16:14.563673+0800 cache_tAnalysis[2857:57028] (null) - 0x0f
2021- 0627 - 16:16:14.563705+0800 cache_tAnalysis[2857:57028] loveEveryone - 0xba88f
2021- 0627 - 16:16:14.563732+0800 cache_tAnalysis[2857:57028] Hello, World!
Program ended with exit code: 0
Copy the code

4.4 Analysis of operation results:

You don’t want to copy source debugginglldbThat automatically inserts the method.
The bottom layer is inserting when creating the method cacheendMarker, so the capacity of the remaining 3, insert finishedlikeFoodandenjoyLifeAfter the method, the capacity is up to 3/4, so in insertsmileToLifeThe method was expanded and the previous cache was cleared, so there were only four methods cached.

5. `cache_t`The flow chart

6. The metaclass`cache_t`

The metaclass cache_t cache class method, which works the same way, is not resolved accordingly.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Cache_t analysis of the structure of the iOS class

preface

1. `cache_t`parsing

1.1 `cache_t`Structure part source parsing

1.2 `cache_t`Partial member variable resolution

1.3 `cache_t`Analysis of some key functions

1.3.1 `cache_t::insert`Function analysis

1.3.2 `cache_fill_ratio`Function analysis

1.3.3 `reallocate`Function analysis

1.3.4 `allocateBuckets`Function analysis

Expansion policy Description:

1.3.5 `setBucketsAndMask`Function analysis

1.3.6 `collect_free`Function analysis

1.3.7 `cache_hash`Function analysis

1.3.8 `cache_next`Function analysis

2 `bucket_t`parsing

2.1 `bucket_t`Structure part source parsing

2.2 `bucket_t`Member variable resolution

2.3 `bucket_t`Analysis of some key functions

2.3.1 `sel`Function analysis

2.3.2 `encodeImp`Function analysis

2.3.3 `imp`Function analysis

2.3.4 `bucket_t::set`Function analysis

2.4 `imp`codec`lldb`Debug verification

3. Verify LLDB dynamic debugging`cache_t`structure

3.1 Sample Code

3.2 LLDB Debugging procedure

3.3 ANALYSIS of LLDB Debugging Results

3.4 `lldb`Automatic insert method validation

Verification method 1:

Verification method 2:

4. Counterfeit source debugging`cache_t`

4.1 Counterfeit source debugging advantages

4.2 Imitation process:

4.3 Example code:

4.4 Analysis of operation results:

5. `cache_t`The flow chart

6. The metaclass`cache_t`

Cache_t analysis of the structure of the iOS class

preface

1. cache_tparsing

1.1 cache_tStructure part source parsing

1.2 cache_tPartial member variable resolution

1.3 cache_tAnalysis of some key functions

1.3.1 cache_t::insertFunction analysis

1.3.2 cache_fill_ratioFunction analysis

1.3.3 reallocateFunction analysis

1.3.4 allocateBucketsFunction analysis

Expansion policy Description:

1.3.5 setBucketsAndMaskFunction analysis

1.3.6 collect_freeFunction analysis

1.3.7 cache_hashFunction analysis

1.3.8 cache_nextFunction analysis

2 bucket_tparsing

2.1 bucket_tStructure part source parsing

2.2 bucket_tMember variable resolution

2.3 bucket_tAnalysis of some key functions

2.3.1 selFunction analysis

2.3.2 encodeImpFunction analysis

2.3.3 impFunction analysis

2.3.4 bucket_t::setFunction analysis

2.4 impcodeclldbDebug verification

3. Verify LLDB dynamic debuggingcache_tstructure

3.1 Sample Code

3.2 LLDB Debugging procedure

3.3 ANALYSIS of LLDB Debugging Results

3.4 lldbAutomatic insert method validation

Verification method 1:

Verification method 2:

4. Counterfeit source debuggingcache_t

4.1 Counterfeit source debugging advantages

4.2 Imitation process:

4.3 Example code:

4.4 Analysis of operation results:

5. cache_tThe flow chart

6. The metaclasscache_t

Related Posts

I read those Metal and math books

A little summary of iOS reverse

Use CocoaHttpServer to build mobile phone local server

1. `cache_t`parsing

1.1 `cache_t`Structure part source parsing

1.2 `cache_t`Partial member variable resolution

1.3 `cache_t`Analysis of some key functions

1.3.1 `cache_t::insert`Function analysis

1.3.2 `cache_fill_ratio`Function analysis

1.3.3 `reallocate`Function analysis

1.3.4 `allocateBuckets`Function analysis

1.3.5 `setBucketsAndMask`Function analysis

1.3.6 `collect_free`Function analysis

1.3.7 `cache_hash`Function analysis

1.3.8 `cache_next`Function analysis

2 `bucket_t`parsing

2.1 `bucket_t`Structure part source parsing

2.2 `bucket_t`Member variable resolution

2.3 `bucket_t`Analysis of some key functions

2.3.1 `sel`Function analysis

2.3.2 `encodeImp`Function analysis

2.3.3 `imp`Function analysis

2.3.4 `bucket_t::set`Function analysis

2.4 `imp`codec`lldb`Debug verification

3. Verify LLDB dynamic debugging`cache_t`structure

3.4 `lldb`Automatic insert method validation

4. Counterfeit source debugging`cache_t`

5. `cache_t`The flow chart

6. The metaclass`cache_t`