IOS low-level exploration Cache_t

Data structure for Cache_t

1. Download objC818’s debuggable source code

2. Add the following code to main.m:

#import <Foundation/Foundation.h>
@interface ABPerson : NSObject

@end
@implementation ABPerson

@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        Class pClass = [ABPerson class];
        NSLog(@"% @",pClass);
    }
    return 0;
}
Copy the code

3. Use LLDB to debug the Cache_t data structure

p/x pClassGets the first address of the class object
p/x 0x0000000100008498 + 0x10First address offset16Get a bytecache_t
p (cache_t *)0x00000001000084a8printcache_taddress
p *$2To viewcache_tstructure

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
    };
Copy the code

You can see that the printed structure corresponds to the structure of cache_t in the objC source code.

void cache_t::insert(SEL sel, IMP imp, id receiver)
{omit some codebucket_t *b = buckets(a);mask_t m = capacity - 1; 
    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)) {
            incrementOccupied(a); 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));bad_cache(receiver, (SEL)sel);
#endif / /! DEBUG_TASK_THREADS
}
Copy the code

The insert method in cache_t wraps SEL and IMP in bucket_t.

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;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endifOmit some code}Copy the code

Bucket_t wraps SEL and IMP.

Cache_tData structure diagram of

Storage of LLDB authentication methods

Modify main.m file code:

@interface ABPerson : NSObject
-(void)saySomething;
@end
@implementation ABPerson
-(void)saySomething
{
    NSLog(@"saySomething");
}
@end

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

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

p/x pClassGets the first address of the class object
p/x 0x00000001000084b8 + 0x10First address offset16Get a bytecache_t
p (cache_t *)0x00000001000084c8printcache_taddress
p *$2To viewcache_tstructure
p [p saySomething]Call the method once to make it cached
p $3.buckets()[4] Memory is shifted by 4 units to get the value
p $4.imp(nil,pClass)printimp

Small-scale sampling

1. Define ab_objc_class by referring to the objc_class structure

struct objc_class :Objc_object {omit some code// Class ISA;
    Class superclass;
    cache_t cache;             // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flagsOmit some code}Copy the code

struct ab_objc_class {
    Class isa;
    Class superclass;
    struct ab_cache_t cache;            
    struct ab_class_data_bits_t bits;
};
Copy the code

2. Define ab_cache_t by referring to cache_t

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}; Omit some code}Copy the code

typedef uint32_t mask_t;
struct ab_cache_t {
    struct ab_bucket_t* _bukets; / / 8
    mask_t    _maybeMask; / / 4
    uint16_t  _flags;  / / 2
    uint16_t  _occupied; / / 2
};
Copy the code

3. Define ab_class_data_bits_t by referring to class_data_bits_t

struct class_data_bits_t {
    friend objc_class;

    // Values are the FAST_ flags above.
    uintptr_tbits; Omit some code}Copy the code

struct ab_class_data_bits_t {
    uintptr_t bits;
};
Copy the code

4. Define ab_bucket_t by referring to bucket_t

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;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endifOmit some codeCopy the code

struct ab_bucket_t {
    SEL _sel;
    IMP _imp;
};
Copy the code

Test the definition of the class ABPerson

@interface ABPerson : NSObject

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

@end
Copy the code

@implementation ABPerson
- (void)say1{
    NSLog(@"ABPerson say : %s",__func__);
}
- (void)say2{
    NSLog(@"ABPerson say : %s",__func__);
}
- (void)say3{
    NSLog(@"ABPerson say : %s",__func__);
}
- (void)say4{
    NSLog(@"ABPerson say : %s",__func__);
}
- (void)say5{
    NSLog(@"ABPerson say : %s",__func__);
}
- (void)say6{
    NSLog(@"ABPerson say : %s",__func__);
}
- (void)say7{
    NSLog(@"ABPerson say : %s",__func__);
}
+ (void)sayHappy{
    NSLog(@"ABPerson say : %s",__func__);
}
@end
Copy the code

Test as output:

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        ABPerson *p  = [ABPerson alloc];
        Class pClass = p.class;
        [p say1];
        [p say2];
        [p say3];
        [pClass sayHappy];
        struct ab_objc_class *ab_class = (__bridge struct ab_objc_class *)(pClass);
        NSLog(@"%hu - %u",ab_class->cache._occupied,ab_class->cache._maybeMask);
        
        for (mask_t i = 0; i<ab_class->cache._maybeMask; i++) {
            struct ab_bucket_t bucket = ab_class->cache._bukets[i];
            NSLog(@"%@ - %pf".NSStringFromSelector(bucket._sel),bucket._imp);
        }
        
        NSLog(@"Hello, World!");
    }
    return 0;
}
Copy the code

No errors were reported, and the output was normal (the output results will be analyzed later, which will be skipped here), indicating that small-scale sampling is feasible.

Insert source code analysis

void insert(SEL sel, IMP imp, id receiver);
Copy the code

void cache_t::insert(SEL sel, IMP imp, id receiver)
{omit some codemask_t newOccupied = occupied() + 1; / / 1 + 1
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    // The cache is empty for the first time
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        // INIT_CACHE_SIZE_LOG2 = 2,
        //INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2),
        // Move 1 two Spaces to the left to create 4, INIT_CACHE_SIZE= 4
        if(! capacity) capacity = INIT_CACHE_SIZE;// Initialize the capacity to 4
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    //cache_fill_ratio:capacity * 3 / 4; If less than or equal to 3/4 of the current volume, insert data normally
    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 it is larger than 3/4 of the current capacity, double the capacity: 4*2 = 8
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        // Allocate memory
        reallocate(oldCapacity, capacity, true);
    }

    bucket_t *b = buckets(a);// Capacity The initial capacity is 4
    mask_t m = capacity - 1; // 4-1=3 8-1 = 7
    // Use cache_hash to get the hash address
    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 {
         // SEL joins for the first time
        if (fastpath(b[i].sel() = =0)) {
            incrementOccupied(a);//occupied++;
            //bucket inserts SEL and IMP
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());
            return;
        }
        // Skip sel if it already exists
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }
        //cache_next: (i+1) & mask
    } while (fastpath((i = cache_next(i, m)) ! = begin));bad_cache(receiver, (SEL)sel);
#endif / /! DEBUG_TASK_THREADS
}

Copy the code

ALWAYS_INLINE
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = buckets(a);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);
   // Store the newBuckets pointer
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
    // Reclaim old memory
        collect_free(oldBuckets, oldCapacity); }}Copy the code

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
#ifdef __arm__
    mega_barrier(a);// Store the newBuckets pointer
    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_relaxed);
    mega_barrier(a);// Store the newMask value
    _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

Say1, say2, say3; cache._occupied = 1; cache._maybeMask = 7; Method stores are also not sequentially stored. Now drop one and just call say1, say2:

The outputcache._occupied = 2.cache._maybeMask = 3.

According to the principle of the above analysis:

The initial capacity is4.mask = capacity - 1So forcache._maybeMask = 3, currently called2So…cache._occupied = 2
call3After several methods:newOccupied = occupied() + 1, i.e.,newOccupied = 3

NewOccupied + CACHE_END_MARKER = 3 + 1 = 4 > Capacity * 3/4 = 3,

Capacity = 2 * 4 = 8, mask = capacity – 1

Cache. _maybeMask = 8-1; cache._maybeMask = 8-1; Because hash table storage is not pure from scratch.

Finally, the insert analysis chart is attached:

Data structure for Cache_t

Storage of LLDB authentication methods

Small-scale sampling

Insert source code analysis

Related Posts

Achieve underwater continuous drop effect in iOS

Basic study of iOS Class source code

Swift5 Alamofire5.0 secondary encapsulation