IOS Underlying Principles 09: Exploring underlying principles of cache_t

preface

This article will examine cache_t in a class structure.

The structure of cache_t

Cache_t source code.

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED//macOS, emulator
    // explicit_atomic displays atomicity. The purpose is to ensure the safety of threads when adding, deleting, or checking
    Struct bucket_t * _buckets;
    // buckets put sel IMP
    // buckets()
    explicit_atomic<struct bucket_t *> _buckets;
    explicit_atomic<mask_t> _mask;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 / / 64 - bit machine
    explicit_atomic<uintptr_t> _maskAndBuckets;// Write together for optimization purposes
    mask_t _mask_unused;
    
    // The following are masks, i.e., masks -- similar to isa masks, i.e., bitfields
    //.... is omitted
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 // Non-64-bit true
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;

    // The following are masks, i.e., masks -- similar to isa masks, i.e., bitfields
    //.... is omitted
#else
#error Unknown cache mask storage type.
#endif
    
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;

    // the method is omitted.....
}
Copy the code

As can be seen from the source code, there are different processing in macOS, 64-bit true and non-64-bit true environments.
CACHE_MASK_STORAGE_OUTLINEDMacOS, emulators
CACHE_MASK_STORAGE_HIGH_16A 64 – bit machine
CACHE_MASK_STORAGE_LOW_4Non – 64-bit true machine
explicit_atomicDisplay atomicity for thread safety.
In the real environment, mask and bucket are written together for optimization purposes.

Bucket_t source

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;
#endif

    // Compute the ptrauth signing modifier from &_imp, newSel, and cls.
    uintptr_t modifierForSEL(SEL newSel, Class cls) const {
        return (uintptr_t)&_imp ^ (uintptr_t)newSel ^ (uintptr_t)cls;
    }
Copy the code

bucket_tDivided into two versions,A: 和 The real machineThe difference is thatsel 和 impIn different order.
From the above source code, it is also clear thatcache_tThe cacheimpandsel, stored inbucket_tIn the.

Get _buckets

Now that we knowimpandselStored in the_buckets, so how to obtain?
Define a Person class that inherits NSobject.

@interface Person : NSObject{
    NSString *hobby;
}

@property (nonatomic.copy) NSString *name;

- (void)eat;
- (void)say;
+ (void)run;

@end

@implementation Person
- (void)eat{
    NSLog(@"eat something"); } - (void)say{
    NSLog(@"say hi");
}
+ (void)run{
    NSLog(@"run run");
}
@end
Copy the code

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

        Person *person = [Person alloc];
        Class pClass   = object_getClass(person);

        [person eat];
        [person say];
        [person say];
    }
    return 0;
}
Copy the code

in[person eat]Before the interruption point, through the LLDB debugging tool, view the memory structure of the person class, LLDB executionp/x pClassGets the first address.

(lldb) p/x pClass
(Class) $0 = 0x00000001000033a8 Person
Copy the code

In the previous article, we learned about the memory layout of the classisa,superclass,cache_t,class_data_bits_tArranged sequentially, whereisa 与 superclassRespectively take up8Two bytes, socache_tThe position of should be offset from the first address of the class16 bytesSo let’s take0x00000001000033a8The offset16Byte, i.e.,0x00000001000033b8The address.
performp (cache_t *)0x00000001000033b8To obtaincache_tThe first address of.

(lldb) p (cache_t *)0x00000001000033b8
(cache_t *) $1 = 0x00000001000033b8
Copy the code

performp *$1, print the cache

(lldb) p *$1
(cache_t) $2 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x000000010032f410 {
      _sel = {
        std::__1::atomic<objc_selector *> = (null)
      }
      _imp = {
        std::__1::atomic<unsigned long> = 0
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 0
  }
  _flags = 32804
  _occupied = 0
}
(lldb) 
Copy the code

No method is called at this point,_sel = null._imp = 0._occupied = 0.
Let’s make a break point at[person say]In the above[person eat]To perform the next stepstep over.
Continue to performp *$1.

(lldb) p *$1
(cache_t) $3 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x0000000100694ab0 {
      _sel = {
        std::__1::atomic<objc_selector *> = ""
      }
      _imp = {
        std::__1::atomic<unsigned long> = 10424
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 3
  }
  _flags = 32804
  _occupied = 1
}
Copy the code

At this time,_seland_impHas the value,_occupied = 1. But how_buckets“And lookedcache_tSource code, finally have a new discovery.

So it was very pleasant to executebuckets()To obtain,p $3.buckets().

(lldb) p $3.buckets()
(bucket_t *) $4 = 0x0000000100694ab0
Copy the code

performp *$4print_bucketsInformation.

(lldb) p *$4
(bucket_t) $5 = {
  _sel = {
    std::__1::atomic<objc_selector *> = ""
  }
  _imp = {
    std::__1::atomic<unsigned long> = 10424}}Copy the code

So how do you get it_seland_impYeah, that’s why I read it_bucketsSource code, seen in the source code, get_seland_impMethods.

performp $4.sel()To obtainsel

(lldb) p $5.sel()
(SEL) $6 = "eat"
Copy the code

performp $5.imp(pClass)To obtainimp

(lldb) p $5.imp(pClass)
(IMP) $7 = 0x0000000100001b10 (KCObjc`-[Person eat])
Copy the code

Get the _BUCKETS summary

1.cacheTo obtain, need to passpClassThe first address of the translation16Byte, i.e.,The first address + 0 x10To obtainThe address of the cache.
2,cache_tProvided in the structurebuckets()To obtain_buckets.
3,_bucketsIn the structure, throughsel()andimp(pClass)Respectively to obtainselandimp.
4. There is no cache when the method is not called. After the method is called, there is a cache in the cache, which is cached after the method is calledcacheIn the.

The structure diagram of cache_t

How to store cache?

incache_tThe incrementOccupied() function that causes changes is found in the source code.

void cache_t::incrementOccupied() 
{
    _occupied++;  / / occupied since
}
Copy the code

Global searchincrementOccupied()Function found to be called only in the INSERT method of cache_t

Global searchinsert(Function, foundcache_fillTo fit the call

Global searchcache_fillAfter the message is sent, the IMP is retrieved and then calledcache_fillMethod writes to the cache, i.eobjc_msgSend->cache_getImp->cache_fill

Insert source code analysis

Insert (), whose source code is implemented as follows

cache->insertI’ve done the function roughly3thing

1. Initialize the cache space

2. Determine whether the capacity needs to be expanded. If yes, expand the capacity by twice the original capacity, reallocate the space, and release the existing cache information

3. Insert the cache according to whether there is already a cache for this method in the hash table

1. Initialize the cache space

ifoccupied()To 0, andbucketsIf no cached content is displayed in4The storage space size isDefault initial value. 4if (! capacity) capacity = INIT_CACHE_SIZE)

    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2),
    // 1 << 2 = 4
Copy the code

callreallocate(oldCapacity, capacity, /* freeOld */false);Allocate space.

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

    ASSERT(newCapacity > 0);
    ASSERT((uintptr_t)(mask_t)(newCapacity- 1) == newCapacity- 1);
    
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    // Release old cached information
    if(freeOld) { cache_collect_free(oldBuckets, oldCapacity); }}Copy the code

callallocateBuckets

bucket_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(cache_t::bytesForCapacity(newCapacity), 1);
    
    bucket_t *end = cache_t::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>((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>((SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity);
    
    return newBuckets;
}

Copy the code

In the reallocate function, calloc of the allocateBuckets function applies for space of newCapacity to the system. SetBucketsAndMask is used to setBucketsAndMask, where mask is updated to the total capacity of the newly applied space -1 (capacity-1).

2. Determine whether there is enough space

If the space is insufficient, expand the space to twice the original size and reallocate the space

Release the stored cache and insert a new cache.

 // Under ARM64, if newOccupied <= 3/4 of the capacity, the storage space is sufficient and no additional processing is required
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    // If more than 3/4
    else {
        // Double the size of the space
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;  // The maximum value cannot exceed 1<< 16
        }
        reallocate(oldCapacity, capacity, true); // Reallocate space to store new data, erase existing cache
    }
Copy the code

3. Insert cache

 /** 3; dip; dip; dip; dip; dip; dip; If a hash conflict is encountered, cache_t looks for the next one until it returns to BEGIN and looks for all */
    
    // Get the hash table
    bucket_t *b = buckets();
    // Get the hash table size -1
    mask_t m = capacity - 1;
    // Use the cache_hash function [begin = sel & m] to calculate the index corresponding to the key value k
    // begin records the query start index
    mask_t begin = cache_hash(sel, m);
    // begin assigns the value to I to switch indexes
    mask_t i = begin;
    
    do {
        if (fastpath(b[i].sel() == 0)) {  // If no way to cache is found
            incrementOccupied(); // _occupied ++;
            b[i].set<Atomic, Encoded>(sel, imp, cls); // Cache instance methods
            return;
        }
        if (b[i].sel() == sel) {  // If you find a method that needs caching, do nothing and exit the loop
            
            return; }}while(fastpath((i = cache_next(i, m)) ! = begin));// When a hash collision occurs, cache_t looks for the next one until it returns to begin
    
    cache_t::bad_cache(receiver, (SEL)sel, cls);
Copy the code

Begin, as the initial query subscript of the hash table, is calculated from SEL & Mask

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}
Copy the code

do … The condition for the while loop is (I = cache_next(I, m)! = begin, which is not equal to the initial subscript value. Begin is used to iterate over all data in the hash table, while cache_next() is used for a second hash to resolve hash conflicts.

#define CACHE_END_MARKER 1
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
Copy the code

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.

IOS Underlying Principles 09: Exploring underlying principles of cache_t

preface

The structure of cache_t

Cache_t source code.

Bucket_t source

Get _buckets

Get the _BUCKETS summary

The structure diagram of cache_t

How to store cache?

Insert source code analysis

1. Initialize the cache space

2. Determine whether there is enough space

3. Insert cache

The flow chart of the insert

IOS Underlying Principles 09: Exploring underlying principles of cache_t

preface

The structure of cache_t

Cache_t source code.

Bucket_t source

Get _buckets

Get the _BUCKETS summary

The structure diagram of cache_t

How to store cache?

Insert source code analysis

1. Initialize the cache space

2. Determine whether there is enough space

3. Insert cache

The flow chart of the insert

Related Posts

Xcode compiles 10 times faster with this!

IOS obtains a unique device ID

Bytedance Flutter architecture practice