IOS Underlying -cache_t Process analysis

Welcome to the iOS Basics series (suggested in order)

IOS low-level – Alloc and init explore

IOS Bottom – Isa for everything

IOS low-level – Analysis of the nature of classes

IOS Underlying – cache_t Process analysis

IOS Low-level – Method lookup process analysis

IOS bottom layer – Analysis of message forwarding process

IOS Low-level – How does Dyld load app

IOS low-level – class load analysis

IOS low-level – Load analysis of categories

In this paper,

This article aims to understand the process leading up to method lookups through source code analysis of cache_T related issues, such as caching policies, dynamic scaling, and so on. Because of its close association with the objc_msgSend process, and because sending messages is the essence of the iOS method, it’s important to understand Cache_t.

Cache_t que

1. Cache_t structure

We took a look at the cache_t structure in the last iOS Underlying class Nature analysis. The underlying structure is as follows:

struct objc_class : objc_object { // Class ISA; Class superclass; cache_t cache; class_data_bits_t bits; . }Copy the code

Cache_t is in objc_class

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

Its own structure consists of three properties:

• bucketsIt’s a method bucket that holds the method implementationimp, numbered according to the methodselThe generatedkey
• maskIs the expansion factor, and at the same timekeyCalculate together to findbucket_tHash index of
• occupiedIs the capacity currently occupied

2. LLDB debugging

Create a new CJPerson class in the objC source code, customize four methods, and call them externally

CJPerson * person = [[CJPerson alloc]init];
Class cls1 = object_getClass(person);
   
[person firstAction];
Class cls2 = object_getClass(person);
    
[person secondAction];
Class cls3 = object_getClass(person);

[person thirdAction];
Class cls4 = object_getClass(person);
 
[person fourthAction];
Class cls5 = object_getClass(person);
Copy the code

Output the following CLS before each method call, in cls1’s case, at the break point at [Person firstAction] x/4gxprintcls1The first four bits of the memory address becausecache_tThe first two propertiesisaandsuperclassA total of 16 bytes, socache_tThe address ofisaIs offset 16 bytes, that is, the address marked in the figure, strong output this addresscls1thecache_tAnd so on, output the restcls

The final results of CLS are as follows: Occupied +1 each time; however, the final results of CLS4 are not consistent with this rule, and the mask value has also changed. It seems that only look at the print result is no way to see who is at fault, or to take a look at the source code.

Cache_t source

1. Find an entry point

Although starting with the source code is a good idea, but so much source code, where to look from. Think about it, but let’s do some researchcache_t.There are 28 related results, and one by one that’s a lot of searching. Think about it, sincecache_tIs a structure, then the system should initialize it, then operate on it, then try to searchcache_t *.With only four relevant results, the pressure was instantly reduced, and there was no problem looking at each one.

Article 1. The first

cache_t *getCache(Class cls) 
{
    assert(cls);
    return &cls->cache;
}
Copy the code

This is just a get method. Exclude

Article 2. The second

void cache_t::bad_cache(id receiver, SEL sel, Class isa) { // Log in separate steps in case the logging itself causes a crash. _objc_inform_now_and_on_crash ("Method cache corrupted. This may be a message to an " "invalid object, or a memory error somewhere else."); cache_t *cache = &isa->cache; _objc_inform_now_and_on_crash ("%s %p, SEL %p, isa %p, cache %p, buckets %p, " "mask 0x%x, occupied 0x%x", receiver ? "receiver" : "unused", receiver, sel, isa, cache, cache->_buckets, cache->_mask, cache->_occupied); . }Copy the code

This is in the bad_cache method, and judging from the name and implementation, it is not hard to tell that this is a warning and crash message when the cache is bad

Article 3. The third

static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver) { cacheUpdateLock.assertLocked(); if (! cls->isInitialized()) return; if (cache_getImp(cls, sel)) return; cache_t *cache = getCache(cls); . }Copy the code

This is in the cache_fill_NOLock method, the name of which stands for cache fill, which feels like it, but is not certain

Article 4. The fourth

void cache_erase_nolock(Class cls) { cacheUpdateLock.assertLocked(); cache_t *cache = getCache(cls); . }Copy the code

This is in the cache_erase_nolock method, whose name stands for cache erase

In summary, the third option is the most likely, but you need to verify that the result is executed after the [person firstAction] call is broken at the point within each method

The breakpoint tocache_fill_nolockIn, you can verify that the method is executed for caching when the method is called.

2. Cache_fill_nolock parsing

Having confirmed that this is the way to perform caching on method invocation, it is necessary to take a closer look at its implementation.

static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver) { cacheUpdateLock.assertLocked(); 1) if (! cls->isInitialized()) return; ② if (cache_getImp(CLS, sel)) return; ③ cache_t *cache = getCache(CLS); ④ cache_key_t key = getKey(sel); ⑤ mask_t new_occupied = cache->occupied(); ⑥ mask_t capacity = cache->capacity(); ⑦ If (cache->isConstantEmptyCache()) {⑧ Cache ->reallocate(capacity, capacity? : INIT_CACHE_SIZE); ⑨} else if (newOccupied <= capacity / 4 * 3) {⑩} else {cache->expand(); Bucket = cache->find(key, receiver); Infinitely (bucket->key() == 0) incrementOccupied(); ⑬ bucket - > set (key, imp); ⑭}Copy the code

(1) Cache lock (2) Determine whether the class is initialized, if not, directly return (3) determine whether SEL has been cached by CLS. If it has been cached, there is no need to go through the following cache process. Direct return (4) through the CLS for cache_t memory address (5) by strong sel metempsychosis into key 6 to obtain the value of the occupancy of the current occupied + 1 in the cache, ⑨ If the bucket capacity is 0 and the bucket capacity is empty, the bucket capacity is 0 and the bucket capacity is empty. However, if the new capacity of Buckets and masks is less than or equal to three quarters of the total capacity, or if the new capacity is more than three quarters of the total capacity, the next step is to expand the capacity by using key as a hash subscript to find the corresponding bucket passing by. What do you want to do with a OCCUPIED cache? If we do not find a occupied cache, we need to cache the occupied keys and IMPsCopy the code

Conclusion:

Cache_fill_nolock Obtains the cache of a class. If the cache is empty, a cache is created. If the cache already exists, the capacity is expanded if the capacity is greater than three quarters of its capacity. Once this is done, the key and IMP are placed in the bucket, and the bucket is placed in the cache.

Understand the main process of cache, in the inside of the more important methods, such as reallocate and expand to do further analysis

a.reallocate(mask_t oldCapacity, mask_t newCapacity)

INIT_CACHE_SIZE definition

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

implementation

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity) { ... setBucketsAndMask(newBuckets, newCapacity - 1); if (freeOld) { cache_collect_free(oldBuckets, oldCapacity); cache_collect(false); }}Copy the code

As you can see, when capacity is empty on the first call, 4 is passed, setBucketsAndMask is added, _BUCKETS is regenerated, and the old bucket oldBuckets is discarded to empty the old cache

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    mega_barrier();
    _buckets = newBuckets;
    mega_barrier();
    _mask = newMask;
    _occupied = 0;
}
Copy the code

After processing, _mask = 4-1 = 3, _occupied = 0. Mask = newCapacity -1, newCapacity = 2^n(minimum initialization is 4, n is capacity expansion times +2), so mask = 2^ n-1, LLDB debugging is worth to verify

b.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) { newCapacity = oldCapacity; } reallocate(oldCapacity, newCapacity); }Copy the code

Obtain oldCapacity.

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

OldCapacity = 4, newCapacity = oldCapacity * 2 = 8, and realLocate is added to realLocate to allocate buckets and masks

c.find(cache_key_t k, id receiver)

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

Use the cache_hash function [begin = k & m] to calculate the index value begin corresponding to the key value K, which is used to record the start index. The value of BEGIN is assigned to I, which is used to switch the index. If the key of bucket_t is k, the query succeeds and the bucket_t is returned. If key = 0, no method has been cached at index I, and bucket_t is returned to abort the cached query. If bucket_t is not found, or bucket_t is empty, then the loop ends, indicating that the search failed. Call the bad_cache method to throw an exception.

Cache_t partial problem summary

1. Does class cache_t cache any methods?

Of the classcache_tOnly object methods are cached; class methods are cached in metaclasses

2. Why does method number SEL need to be strongly converted to key?

The method number SEL is a string and is not passed as efficiently underneath as a key of type long

3. What does mask do?

maskAs one of the parameters to judge expansion, it can be called expansion factor. At the same timemaskandkeyCo-generated hash table used for lookupbucket_t. Here,maskandisa_maskThe functions of masks are different and need to be distinguished.

4. Is method cache in order?

Method cachedbucket_tIt’s based on the hash table, where you find an empty seat and you sit down and occupy it, there’s no order

5. Why is the expansion 3/4?

HashMapWhen the load factor of is equal to 0.75, the space utilization rate is relatively high, and considerable Hash conflicts are avoided, which makes the height of the underlying linked list or red-black tree relatively low, and improves the space efficiency.

6. The relationship between bucket and mask, capacity, SEL and IMP

• bucketWithin theimpandselThe generatedkey
• bucketIs through thekeyandmaskIn search of
• bucketThe amount depends oncapacity

7. Why do I need to discard all caches after capacity expansion?

In a sense, the cache is discarded after expansion, and the next call to recache makes the cache meaningless. In fact, there are many methods in the general class, if the expansion, but also need to save the original method, newbucket_tNeed to get from the oldbucket_tTo get all the methods and put them in one by one, which is itself a time-consuming activity. The purpose of method caching is to make the message sending process faster, and Apple also makes method lookup go through the assembly process for faster, all for the sake of one word — fast. Discarding the original cache after capacity expansion was designed for this purpose, and this design, in a sense, fitsLRUCaching policies, recently cached methods also have higher utilization, and older cached methods have lower utilization.

Write in the last

That’s part of my understanding of cache_t, which is an entry point for sending messages. The next chapter, objc_msgSend, gives you a broader understanding of Cache_t. Stay tuned.