Environment: Xcode 11.5
Source: objc4-781
The last article explored the structure of the class, as follows:
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
...
}
Copy the codeWhere ISA ISA pointer to objc_class, superclass refers to the superclass, and bits stores some basic information about the current class. Today we’ll continue exploring the last variable in the objc_class structure, cache_t.
Cache_t profile
First, let’s look at the structure of Cache_t:
struct cache_t { #if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED explicit_atomic<struct bucket_t *> _buckets; Explicit_atomic <mask_t> _mask; #elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 explicit_atomic<uintptr_t> _maskAndBuckets; mask_t _mask_unused; Static Constexpr Uintptr_t Uintkshift = 12; static constexpr uintptr_t maskZeroBits = 4; static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1; static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1; . #endif #if __LP64__ uint16_t _flags; #endif uint16_t _occupied; // The number of methods in the cache}Copy the codeThere are some differences between the ARM and x86 architectures. The specific difference lies in that the Pointers of Mask and buckets are stored in one Uintptr_t data in THE ARM architecture and stored separately in the x86 architecture. At the same time, the ARM architecture also defines some masks and other data for data reading, that is, some constants in the above code.
Bucket_t has the following structure:
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; #endifCopy the codeBucket_t has two properties, key for the method identifier and _IMP for the method implementation.
Cache_t explore
Let’s explore this directly using LLDB.
@interface ZHYObject : NSObject
- (void)method1;
- (void)method2;
- (void)method3;
@end
Copy the codeint main(int argc, const char * argv[]) {
@autoreleasepool {
ZHYObject *object = [[ZHYObject alloc] init];
[object method1];
[object method2];
[object method3];
NSLog(@"%@",object);
}
return 0;
}
Copy the code- The breakpoint is made and printed before the instance method is called
(lldb) x/4gx pClass
0x1000023d0: 0x00000001000023a8 0x00000001003ef140
0x1000023e0: 0x00000001003e9450 0x0000801000000000
(lldb) p (cache_t*)0x1000023e0
(cache_t *) $1 = 0x00000001000023e0
(lldb) p *$1
(cache_t) $2 = {
_buckets = {
std::__1::atomic<bucket_t *> = 0x00000001003e9450 {
_sel = {
std::__1::atomic<objc_selector *> = 0x0000000000000000
}
_imp = {
std::__1::atomic<unsigned long> = 0
}
}
}
_mask = {
std::__1::atomic<unsigned int> = 0
}
_flags = 32784
_occupied = 0
}
Copy the codeCurrently in cache_t, there is no method cache; occupied is 0. Then take a step at the break point. Reprint cache_t
(lldb) p *$1
(cache_t) $3 = {
_buckets = {
std::__1::atomic<bucket_t *> = 0x00000001006263e0 {
_sel = {
std::__1::atomic<objc_selector *> = 0x00007fff7482ec60
}
_imp = {
std::__1::atomic<unsigned long> = 4046048
}
}
}
_mask = {
std::__1::atomic<unsigned int> = 3
}
_flags = 32784
_occupied = 1
}
(lldb) p $3.buckets()
(bucket_t *) $4 = 0x00000001006263e0
(lldb) p *($4)
(bucket_t) $5 = {
_sel = {
std::__1::atomic<objc_selector *> = 0x00007fff7482ec60
}
_imp = {
std::__1::atomic<unsigned long> = 4046048
}
}
(lldb) p $5.sel()
(SEL) $6 = "init"
(lldb) p *($4+1)
(bucket_t) $7 = {
_sel = {
std::__1::atomic<objc_selector *> = 0x0000000000000000
}
_imp = {
std::__1::atomic<unsigned long> = 0
}
}
Copy the codeThe comparison shows that:
_bucketsMemory address changed by0x00000001003e9450Turned out to be0x00000001006263e0_bucketsThere’s only one in the arraybucket_tTheta corresponds to thetainitmethods_maskby0Turned out to be3_occupiedby0Turned out to be1
Next step on the breakpoint and print
(lldb) p *$1 (cache_t) $8 = { _buckets = { std::__1::atomic<bucket_t *> = 0x00000001006263e0 { _sel = { std::__1::atomic<objc_selector *> = 0x00007fff7482ec60 } _imp = { std::__1::atomic<unsigned long> = 4046048 } } } _mask = { std::__1::atomic<unsigned int> = 3 } _flags = 32784 _occupied = 2 } (lldb) p *($4) (bucket_t) $9 = { _sel = { std::__1::atomic<objc_selector *> = 0x00007fff7482ec60 } _imp = { std::__1::atomic<unsigned long> = 4046048 } } (lldb) p $9.sel() (SEL) $10 = "init" (lldb) p *($4+1) (bucket_t) $11 = { _sel = { std::__1::atomic<objc_selector *> = 0x0000000100000e15 } _imp = { std::__1::atomic<unsigned long> = 11904 } } (lldb) p $11.sel() (SEL) $12 = "method1"Copy the codeThe comparison shows that:
_bucketsThe address hasn’t changed since the first time_maskIt hasn’t changed_occupiedTurned out to be2, consistent with the printed result,_bucketsThere are two methods in the array, alpha and beta_occupiedThe value of the same
The breakpoint continues to the next step and prints
(lldb) p *$1
(cache_t) $14 = {
_buckets = {
std::__1::atomic<bucket_t *> = 0x0000000101929660 {
_sel = {
std::__1::atomic<objc_selector *> = 0x0000000000000000
}
_imp = {
std::__1::atomic<unsigned long> = 0
}
}
}
_mask = {
std::__1::atomic<unsigned int> = 7
}
_flags = 32784
_occupied = 1
}
(lldb) p $14.buckets()
(bucket_t *) $20 = 0x0000000101929660
(lldb) p *$20
(bucket_t) $21 = {
_sel = {
std::__1::atomic<objc_selector *> = 0x0000000000000000
}
_imp = {
std::__1::atomic<unsigned long> = 0
}
}
(lldb) p *($20+1)
(bucket_t) $22 = {
_sel = {
std::__1::atomic<objc_selector *> = 0x0000000000000000
}
_imp = {
std::__1::atomic<unsigned long> = 0
}
}
(lldb) p *($20+2)
(bucket_t) $23 = {
_sel = {
std::__1::atomic<objc_selector *> = 0x0000000000000000
}
_imp = {
std::__1::atomic<unsigned long> = 0
}
}
(lldb) p *($20+3)
(bucket_t) $24 = {
_sel = {
std::__1::atomic<objc_selector *> = 0x0000000000000000
}
_imp = {
std::__1::atomic<unsigned long> = 0
}
}
(lldb) p *($20+4)
(bucket_t) $25 = {
_sel = {
std::__1::atomic<objc_selector *> = 0x0000000000000000
}
_imp = {
std::__1::atomic<unsigned long> = 0
}
}
(lldb) p *($20+5)
(bucket_t) $26 = {
_sel = {
std::__1::atomic<objc_selector *> = 0x0000000100000e1d
}
_imp = {
std::__1::atomic<unsigned long> = 11952
}
}
(lldb) p $26.sel()
(SEL) $27 = "method2"
Copy the codeThe comparison shows that:
_bucketsThe memory address has changed again_maskby3Turned out to be7_occupiedby3Turned out to be1method2The method is not stored in the first void, we searched several times before we found it
Based on the above exploration, several questions arise:
_bucketsWhen will the memory address of the_maskWhat is the meaning of “?_occupiedWhy did it become1Instead of getting smaller?_bucketsWhat are the rules for storing method locations in?
Cache_t underlying implementation
According to the LLDB exploration above, it can be found that every time _buckets changes, _mask will also change, and _mask will be 2 ^ n -1, and _occupied will change to 1. So let’s verify our findings with the relevant source code. Note the following lines in the objc_cache.mm comment:
* Cache writers (hold cacheUpdateLock while reading or writing; not PC-checked)
* cache_fill (acquires lock)
* cache_expand (only called from cache_fill)
* cache_create (only called from cache_expand)
* bcopy (only called from instrumented cache_expand)
* flush_caches (acquires lock)
* cache_flush (only called from cache_fill and flush_caches)
* cache_collect_free (only called from cache_expand and cache_flush)
Copy the codeWe start tracing the source code from cache_fill
void cache_fill(Class cls, SEL sel, IMP imp, id receiver) { runtimeLock.assertLocked(); #if ! DEBUG_TASK_THREADS // Never cache before +initialize is done if (cls->isInitialized()) { cache_t *cache = getCache(cls); #if CONFIG_USE_CACHE_LOCK mutex_locker_t lock(cacheUpdateLock); #endif cache->insert(cls, sel, imp, receiver); } #else _collecting_in_critical(); #endif }Copy the codeFirst check whether the class is initialized, then read the corresponding cache variable from the objC_class structure, and then perform insert.
insert
ALWAYS_INLINE void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver) { #if CONFIG_USE_CACHE_LOCK cacheUpdateLock.assertLocked(); #else runtimeLock.assertLocked(); #endif ASSERT(sel ! = 0 && cls->isInitialized()); // Use the cache as-is if it is less than 3/4 full mask_t newOccupied = occupied() + 1; unsigned oldCapacity = capacity(), capacity = oldCapacity; If (slowpath(isConstantEmptyCache())) {// If the Cache does not already exist, initialize it to 4, and reset the Cache // Cache is read-only. Replace it. If (! capacity) capacity = INIT_CACHE_SIZE; reallocate(oldCapacity, capacity, /* freeOld */false); } else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { // 4 3 + 1 bucket cache_t // Cache is less than 3/4 full. Use it as-is. } else { capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; 4 if (capacity > MAX_CACHE_SIZE) {capacity = MAX_CACHE_SIZE; } reallocate(oldCapacity, capacity, true); } bucket *b = buckets(); 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 because the // minimum size is 4 and we resized at 3/4 full. do { if (fastpath(b[i].sel() == 0)) { incrementOccupied(); b[i].set<Atomic, Encoded>(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)); cache_t::bad_cache(receiver, (SEL)sel, cls); }Copy the codeInsert is the core method for caching by CACHE_t. The main operations are as follows:
1. Determine whether to expand the capacity
The 'reallocate' method is called when the 'cache' is empty or the number of 'buckets' after being inserted is greater than three quarters of its original capacity. 'reallocate' is mainly responsible for '_buckets' reopening memory and' old _buckets' release.Copy the codeALWAYS_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) {
cache_collect_free(oldBuckets, oldCapacity);
}
}
Copy the codeReallocate does a few things:
- According to incoming
newCapacityCreate a newbucket - Will the new
bucketAssigned to the currentcache, and updatemaskThe value ofnewCapacity - 1 - If necessary, release the old ones
bucket - It’s important to note, because the initial capacity is zero
4And each expansion will be the old capacity2Times PI, so the new capacity has to be 2n.maskThe value is 2n– 1
2.selandimpPut in the specifiedbucketIn the
As mentioned earlier, methods stored in _buckets are not sequentially stored. What is the rule? The answer is also in insert. The idea for finding the corresponding bucket is as follows:
- According to the
cache_hashMethods to obtainselThe corresponding hashkey.
static inline mask_t cache_hash(SEL sel, mask_t mask)
{
return (mask_t)(uintptr_t)sel & mask;
}
Copy the codeIf the value of sel is 0, then the final value of sel is 0, then the final value of sel is 0
If the bucket->sel corresponding to position 2 is equal to the current sel, it is possible that other threads cache this method and return it directly.
Otherwise, a hash conflict has occurred, and you need to find a new hash value.
//__arm64__ Cache_next is implemented differently in different architectures and needs to be noted. static inline mask_t cache_next(mask_t i, mask_t mask) { return i ? i-1 : mask; }Copy the codeinarm64The schema resolves conflicts by looking one bit ahead, and if the first bucket array is still a conflict, starting at the last bit of the array.
bad_cacheLogic.
At this point, the process of caching the method ends, the core methodinsertThe flow chart is as follows:
