IOS explores cache_T analysis

Welcome to the iOS Exploration series.

• IOS explores the alloc process
• IOS explores memory alignment &malloc source code
• IOS explores ISA initialization & pointing analysis
• IOS exploration class structure analysis
• IOS explores cache_T analysis
• IOS explores the nature of methods and the method finding process
• IOS explores dynamic method resolution and message forwarding mechanisms
• IOS explores the dyLD loading process briefly
• The loading process of iOS explore classes
• IOS explores the loading process of classification and class extension
• IOS explores isa interview question analysis
• IOS Explore Runtime interview question analysis
• IOS explores KVC principles and customization
• IOS explores KVO principles and customizations
• IOS explores the principle of multithreading
• IOS explores multi-threaded GCD applications
• IOS explores multithreaded GCD underlying analysis
• IOS explores NSOperation for multithreading
• IOS explores multi-threaded interview question analysis
• IOS Explore the locks in iOS
• IOS explores the full range of blocks to read

Writing in the front

The class structure was covered in detail in the last article, but cache_t cache remains uncovered. This article will examine Cache_t from the source level

Cache_t

1. Cache_t structure

Here is the underlying structure of the class

struct objc_class : objc_object {
    // Class ISA;
    Class superclass;
    cache_t cache;             // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
    
    class_rw_t *data() { 
        returnbits.data(); }... }Copy the code

Cache_t has the following structure

struct cache_t {
    struct bucket_t* _buckets;
    mask_t _mask;
    mask_t_occupied; . };Copy the code

As mentioned in previous articles, we can see from the structure of cache_t that it consists of two uint32_t struct Pointers of _mask and _occupied and 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__
    MethodCacheIMP _imp;
    cache_key_t _key;
#else
    cache_key_t _key;
    MethodCacheIMP _imp;
#endif

public:
    inline cache_key_t key(a) const { return _key; }
    inline IMP imp(a) const { return (IMP)_imp; }
    inline void setKey(cache_key_t newKey) { _key = newKey; }
    inline void setImp(IMP newImp) { _imp = newImp; }

    void set(cache_key_t newKey, IMP newImp);
};
Copy the code

From bucket_t’s properties and methods, you can see that it is associated with IMP — bucket_t is actually a bucket that holds the IMP method implementation and its key

In cache_T, _buckets, _mask, and _occupied are represented by their names: “occupied”; “occupied”; “occupied”; “occupied”

2. LLDB debugging

Prepare the code in objC source

#import <objc/runtime.h>

@interface FXPerson : NSObject
- (void)doFirst;
- (void)doSecond;
- (void)doThird;
@end

@implementation FXPerson
- (void)doFirst {}
- (void)doSecond {}
- (void)doThird {}
@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        FXPerson *p = [[FXPerson alloc] init];
        Class cls = object_getClass(p);
        
        [p doFirst];
        [p doSecond];
        [p doThird];
    }
    return 0;
}
Copy the code

_buckets is an imp method barrels, that we are in a method call a breakpoint (article said that class isa pointer of 8 bytes, superclass pointer of 8 bytes, as long as to get the class first address + 16 bytes can get cache_t address)

_mask is 3, _occupied is 1, and we continue to print _buckets

Print multiple $3’s and only find one [NSObject init] cached

[p doSecond]; One line (I re run the project here)

[p doThird]; Line, get the following data:

breakpoint	_occupied	The _buckets contains methods
[p doFirst]	1	-[NSObject init]
[p doSecond]	2	-[NSObject init], -[FXPerson doFirst]
[p doThird]	3	-[FXPerson doFirst], -[FXPerson doSecond]

According to the above data, _buckets is the bucket with methods; _occupied is the number of methods in the bucket

Wait, someone here must be wondering, how come FXPerson is calling the alloc method and there is no cache – as mentioned in the last article, the alloc method is a class method and exists in the FXPerson metaclass

Just when you think everything is going well, something happens — break point goes to the next line

_mask and _occupied have both changed dramatically, so what’s going on at the bottom? Why was bucket[0] empty when it was printed earlier?

Dive into cache_t

Find an entry point

Given that the value of _mask is increased, we find mask_t mask() in cache_t, which returns only _mask itself

mask_t cache_t::mask() 
{
    return _mask; 
}
Copy the code

We continue to search for the mask() method, and find that there is a corresponding operation of mask in the Capacity method, but the purpose of operation is not very clear

mask_t cache_t::capacity() 
{
    return mask() ? mask()+1 : 0; 
}
Copy the code

Continuing the search for the Capacity () method, you see a meaningful call to the Capacity method in the expand method

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    uint32_t oldCapacity = capacity();
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;

    if ((uint32_t) (mask_t)newCapacity ! = newCapacity) {// mask overflow - can't grow further
        // fixme this wastes one bit of mask
        newCapacity = oldCapacity;
    }

    reallocate(oldCapacity, newCapacity);
}
Copy the code

Expand method should be a capacity expansion method, moving up to cache_FILL_NOLock

static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
    cacheUpdateLock.assertLocked();

    // Never cache before +initialize is done
    if(! cls->isInitialized())return;

    // Make sure the entry wasn't added to the cache by some other thread 
    // before we grabbed the cacheUpdateLock.
    if (cache_getImp(cls, sel)) return;

    cache_t *cache = getCache(cls);
    cache_key_t key = getKey(sel);

    // Use the cache as-is if it is less than 3/4 full
    mask_t newOccupied = cache->occupied() + 1;
    mask_t capacity = cache->capacity();
    if (cache->isConstantEmptyCache()) {
        // Cache is read-only. Replace it.cache->reallocate(capacity, capacity ? : INIT_CACHE_SIZE); }else if (newOccupied <= capacity / 4 * 3) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        // Cache is too full. Expand it.
        cache->expand();
    }

    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot because the 
    // minimum size is 4 and we resized at 3/4 full.
    bucket_t *bucket = cache->find(key, receiver);
    if (bucket->key() == 0) cache->incrementOccupied();
    bucket->set(key, imp);
}
Copy the code

Adding a breakpoint in the function call stack verifies that we are looking in the right direction

1.cache_fill_nolock

The cache_FILL_NOLock method is complex, and I’ll take a step-by-step look at it here

1) if (! cls->isInitialized()) return;

Class whether to initialize the object, no return

(2) if (cache_getImp (CLS, sel)) return;

CLS and SEL are passed in, and imp is returned if found in the cache, not the next step

(3) cache_t * cache = getCache (CLS);

Call getCache to get the CLS cache object

(4) cache_key_t key = getKey (sel);

Get the cached key with getKey — forcing SEL to be cache_KEY_t

⑤mask_t new_occupied = cache->occupied();

NewOccupied; newOccupied; occupied; newOccupied; occupied; occupied; occupied; occupied; occupied; occupied; occupied; occupied; occupied; occupied; occupied; occupied; occupied

6 mask_t capacity = cache – > capacity ();

Read the current cache capacity

⑥ Check cache usage

if (cache->isConstantEmptyCache()) {
    // Cache is read-only. Replace it.cache->reallocate(capacity, capacity ? : INIT_CACHE_SIZE); }else if (newOccupied <= capacity / 4 * 3) {
    // Cache is less than 3/4 full. Use it as-is.
}
else {
    // Cache is too full. Expand it.
    cache->expand();
}
Copy the code

• If the cache is empty, reapply memory and overwrite the previous cache
• If the new cache takes up size< =Three quarters of the cache capacity, the cache process can be carried out
• If the cache is not empty and the cache usage exceeds three-fourths of its capacity, expand the cache capacity

⑦bucket_t *bucket = cache->find(key, receiver);

Bucket_t is found in the cache using the key

⑧if (bucket->key() == 0) incrementOccupied();

If the key of the bucket is 0, it is _occupied++

Pet-name ruby bucket – > set (key, imp);

Put keys and IMPs into buckets in pairs

Conclusion:

Cache_fill_nolock finds the class’s cache cache first and overwrites it if it is empty. If the occupied part is larger than three quarters of the cache capacity, expand the occupied part and then load the occupied part into the bucket with the corresponding key value. Otherwise, the bucket is directly loaded into the bucket with the corresponding key value

After analyzing the cache_FILL_NOLock main flow, you can extend it in a few ways

2.cache_t::reallocate

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    bool freeOld = canBeFreed();

    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) {
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false); }}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.
    // fixme instead put the end mark inline when +1 is malloc-inefficient
    bucket_t *newBuckets = (bucket_t *)
        calloc(cache_t::bytesForCapacity(newCapacity), 1);

    bucket_t *end = cache_t::endMarker(newBuckets, newCapacity);

#if __arm__
    // End marker's key is 1 and imp points BEFORE the first bucket.
    // This saves an instruction in objc_msgSend.
    end->setKey((cache_key_t) (uintptr_t)1);
    end->setImp((IMP)(newBuckets - 1));
#else
    // End marker's key is 1 and imp points to the first bucket.
    end->setKey((cache_key_t) (uintptr_t)1);
    end->setImp((IMP)newBuckets);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity);

    return newBuckets;
}

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.

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

    _buckets = newBuckets;
    
    // ensure other threads see new buckets before new mask
    mega_barrier();
    
    _mask = newMask;
    _occupied = 0;
}
Copy the code

• First determine whether it can be released (cache is empty take negative value) and save
• oldBucketsGet the currentbucket
• Pass in a new cache capacityallocateBucketsInitialize thebucket_tAnd stored in thenewBuckets
• setBucketsAndMaskActions done: With the newly createdbucketSave,mask=newcapcity-1.occupiedZero (because there is no method cache yet)
• If the cache is not empty (needs to be freed), the original is freedbucket,capacity

Why use cache_Collect_free to erase memories rather than read/write, memory copy? First, it is not safe to read and write again. Second, erasure speed is fast

3.cache_t::expand

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    uint32_t oldCapacity = capacity();
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;

    if ((uint32_t) (mask_t)newCapacity ! = newCapacity) {// mask overflow - can't grow further
        // fixme this wastes one bit of mask
        newCapacity = oldCapacity;
    }

    reallocate(oldCapacity, newCapacity);
}

enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2)
};

mask_t cache_t::capacity() 
{
    return mask() ? mask()+1 : 0; 
}
Copy the code

• oldCapacityThe value ofmask+1
• inoldCapacityIn the presence of,newCapacitytakeoldCapacityTwice; Otherwise takeINIT_CACHE_SIZE
• Here,INIT_CACHE_SIZEforBinary 100= >Decimal four
• Create and overwrite the original cachereallocate

4.cache_t::find

Cache_t ::find: Searches for the corresponding bucket

bucket_t * cache_t::find(cache_key_t k, id receiver) { assert(k ! = 0); bucket_t *b = buckets(); mask_t m = mask(); mask_t begin = cache_hash(k, m); mask_t i = begin;do {
        if (b[i].key() == 0  ||  b[i].key() == k) {
            return&b[i]; }}while((i = cache_next(i, m)) ! = begin); // hack Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache)); cache_t::bad_cache(receiver, (SEL)k, cls); }Copy the code

• throughbuckets()Method to get the currentcache_tRun all cache bucketsbucket
• throughmask()Method to get the currentcache_tThe value of the cache capacity minus onemask_t
• key & maskCalculates the starting index
• beginAssigned toi, used to switch indexes
• indo-whileI’m going to loop through the whole thingbucket_tIf thekey = 0, indicating that no method has been cached at index Ibucket_t, used to abort cached queries; If I take it outbucket_tthekey = k“Is displayed, the query is successfulbucket_t
• throughcache_nextreturni-1Update the index to query each element in the hash table (equivalent to going in a loop)
• If it can’t find a proof of a cache problem, returnbad_cache

5. The LRU algorithm

LRU algorithm is the Least Recently Used strategy — the core idea of this strategy is to first eliminate the Least Recently Used content, and this algorithm is also Used in the method cache

• Before capacity expansion, the instance method chooses a seat
• After expansion, the new instance method finds the least recently used location and sits down and clears the previous bucket

Cache_t query point

1. The role of the mask

• maskAs acache_tProperty exists, which represents the value of the cache capacity minus one
• maskforbucketIs mainly used in the cache lookup of the hash algorithm

2. The change of capacity

Capacity changes mainly when the cache->expand() is expanded. When the cache is three quarters full, the capacity is doubled to avoid hash conflicts

3. Why is the expansion done at 3/4

In data structures such as hashes, there is a concept used to indicate how many empty Spaces there are called the load factor – the larger the load factor, the fewer free Spaces there are, the more conflicts there are, and the performance of the hash table deteriorates

When the load factor is 3/4, the space utilization is relatively high, and considerable Hash conflicts are avoided, which improves the space efficiency

Why is the default load factor for reading HashMap 0.75?

4. Whether the method cache is in order

static inline mask_t cache_hash(cache_key_t key, mask_t mask) 
{
    return (mask_t)(key & mask);
}
Copy the code

The method cache is unordered because the cache subscript is computed using a hash algorithm — the subscript value depends on the key and mask values

5. Relationship between bucket and Mask, capacity, SEL, and IMP

• classclsHave attributescache_t.cache_tIn thebucketsThere are multiplebucket— Stores method implementationsimpAnd method numberselThe key value of the strong conversioncache_key_t
• maskforbucketIs mainly used in the cache lookup of the hash algorithm
• capacityYou can getcache_tIn thebucketThe number of

The main purpose of caching is to allow the compiler to execute the logic of sending messages faster through a series of policies

Write in the back

There’s not much to read about cache_t, but it’s pretty convoluted. Read the source code for a better understanding. The next article will look at objc_msgsend, which, as a cache_fill_NOLock predisposition method, will be programmatically helpful in understanding cache_t