OC Underlying principle (6) : Analysis of cache_t

cache_tThe nature of

In order to make the method more responsive and efficient without having to go through the method every time, the cache_t structure appears during the class method call, which is known to look up the IMP(method pointer) in memory through SEL(method number). Cache_t stores the SEL and IMP of the invoked method and the receiver in the current class structure as bucket_T structures for subsequent method lookups.

Structure:

classDiagram
LGPerson --|> cache_t
bucket_t <|-- cache_t
class LGPerson{
isa
superclass
cache
bits
}
class cache_t{
_buckets
_mask
_flags
_occupied
}
class bucket_t{
_sel
_imp
}

Graph:

Cache_t structure

From the structure diagram, we can first explore the cache type cache_t. See the cache_t structure in the source objC4-818.2

Source code for cache_t:

struct cache_t { private: explicit_atomic<uintptr_t> _bucketsAndMaybeMask; // 8bytes union { struct { explicit_atomic<mask_t> _maybeMask; // 4bytes #if __LP64__ uint16_t _flags; // 2bytes #endif uint16_t _occupied; // 2bytes }; explicit_atomic<preopt_cache_t *> _originalPreoptCache; // 8bytes }; / * # if defined (__arm64__) && __LP64__ # if TARGET_OS_OSX | | TARGET_OS_SIMULATOR / / __arm64__ simulator # define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS #else // Real machine of __arm64__ #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16 #endif #elif defined(__arm64__) && ! __LP64__ // 32-bit real machine #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_LOW_4 #else //macOS emulator #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED #endif ****** Intermediate judgments between different architectures are used mainly to mask different types of masks and buckets */ public: void incrementOccupied(); void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask); void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld); unsigned capacity() const; struct bucket_t *buckets() const; Class cls() const; void insert(SEL sel, IMP imp, id receiver); // The following are methods that are basically other methods};Copy the code

Conclusion:

1. _bucketsAndMaybeMaskvariableuintptr_tTake up8 bytes (bytes)andisa_tIn thebitsSimilarly, it’s also aPointer typesIt holds the address
2. There’s one in the combinationThe structure of the bodyAnd aStructure pointer _originalPreoptCache
3. There are three member variables in the structure_maybeMask,_flags,_occupied.__LP64__Refers to theUnixandUnixSuch systems (LinuxandmacOS)
4. _originalPreoptCacheandThe structure of the bodyAre mutually exclusive,_originalPreoptCacheThe initial cache, now looking at caching in classes, this variable is rarely used
5. cache_tProvides common methods to obtain values, and to obtain them according to different architectural systemsmaskandbucketsThe mask

You see buckets() in cache_t, which is similar to the methods() provided in class_data_bits_t, which get values from methods.

buckets()Graph:

bucket_tThe structure of the body

Find the process by entering the bucket_t structure

The source code:

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 .... // The following is the method omitted};Copy the code

Conclusion:

1. bucket_tDistinguish between the real machine and the others, but the variables are unchanged_seland_impJust in a different order
2. bucket_tIt contains the following_seland_imp.cacheIt should cache the method

Cache_t overall structure

Structure:

ClassDiagram objc_class - | > cache_t real machine objc_class - | > cache_t simulator and macos cache_t simulator and macos - | > bucket_t not really cache_t really machine - | > Bucket_t really cache_t really machine - | > _maskAndBuckets cache_t really machine, | > cache_t mask and buckets in class objc_class {class ISA class Superclass cache_t Cache class_data_bits_t bits} Class cache_t emulator and macos{struct bucket_t *_buckets mask_t mask uint16_t Flags UintPtr_t _bucketsAndMaybeMask mask_t _maybeMask uint16_t _flags Uint16_T _occupied capactity() bucket_t *buckets() mask_t occupied() void incrementOccupied() void setBucketsAndMask() void Reallocate () void insert()} class bucket_t non-real machine {explicit_atomic<SEL>_sel explicit_atomic<uintptr_t> _IMP} class Bucket_t real computer {explicit_atomic<uintptr_t>_sel explicit_atomic<SEL> _IMP} class _maskAndBuckets { } mask and buckets{maskShift = 48 maskZeroBits = 4 maxMask = ((uintPtr_t)1 << (64 - maskShift)) - 1 static constexpr uintptr_t bucketsMask = ((uintptr_t)1<< (maskShift - maskZeroBits)) - 1 }

Graph:

Code breakpoint debugging

Create LGPerson class, customize some instance methods, create LGPerson instantiation object in main, and debug LLDB

Code:

#import <Foundation/Foundation.h>

@interface LGPerson : NSObject
@property (nonatomic, copy) NSString *name;
@property (nonatomic) int age;
@property (nonatomic, strong) NSString *hobby;
- (void)saySomething;
+ (void)sayHappy;
@end

@implementation LGPerson

- (instancetype)init{
    if (self = [super init]) {
        self.name = @"Cooci";
    }
    return self;
}
- (void)saySomething{
    NSLog(@"%s",__func__);
}
+ (void)sayHappy{
    NSLog(@"LGPerson say : %s",__func__);
}
@end

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

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

LLVM debugging:

(lldb) p/x pClass (Class) $0 = 0x00000001000084f0 LGPerson (lldb) p/x 0x00000001000084f0 + 0x10 (long) $1 = 0x0000000100008500 (lldb) p/x (cache_t *)$1 (cache_t *) $2 = 0x0000000100008500 (lldb) p *$2 (cache_t) $3 = { _bucketsAndMaybeMask = { std::__1::atomic<unsigned long> = { Value = 4298515312 } } = { = { _maybeMask = { std::__1::atomic<unsigned int> = { Value = 0 } } _flags = 32808 _occupied = 0 } _originalPreoptCache = { std::__1::atomic<preopt_cache_t *> = { Value = 0x0000802800000000 } } } } (lldb) p/x $3.buckets() (bucket_t *) $4 = 0x0000000100362370 (lldb) p *$4 (bucket_t) $5 = { _sel = { std::__1::atomic<objc_selector *> = (null) { Value = (null) }  } _imp = { std::__1::atomic<unsigned long> = { Value = 0 } } } (lldb)Copy the code

Graph:

Conclusion:

1. cacheThe address of the variable, requiredThe first address is offset by 16 bytesnamely0x10.cacheThe address of theThe first address+0x10
2. cache_tThe methods inbuckets()It points to the first address of a block of memory, which is the first onebucketThe address of the
3. p/x $3.buckets()[indx]Print the rest in memorybucketfound_selandimp
4. LGPersonObject is not calledObject methods.bucketsIn theThere is no cacheMethod data

Call the object method in LLDB, and [p sayHello] continues LLDB debugging

llvm:

(LLDB) p [p saySomething] // call saySomething method 2021-07-04 02:37:14.269170+0800 KCObjcBuild[26446:4843266] -[LGPerson saySomething] (lldb) p *$2 (cache_t) $6 = { _bucketsAndMaybeMask = { std::__1::atomic<unsigned long> = { Value = 4316269184}} = {= {_maybeMask = {STD ::__1::atomic<unsigned int> = {Value = 7}} _flags = 32808 _occupied = 1 } _originalPreoptCache = {STD ::__1::atomic<preopt_cache_t *> = {Value = 0x0001802800000007}}}} (LLDB) p/x $6.buckets() (bucket_t *) $7 = 0x0000000101450a80 (lldb) p *$7 (bucket_t) $8 = { _sel = { std::__1::atomic<objc_selector  *> = (null) { Value = (null) } } _imp = { std::__1::atomic<unsigned long> = { Value = 0 } } } (lldb) p *($7+1) (bucket_t) $9 = { _sel = { std::__1::atomic<objc_selector *> = (null) { Value = (null) } } _imp = { std::__1::atomic<unsigned long> = { Value = 0 } } } (lldb) p *($7+2) (bucket_t) $10 = { _sel = { std::__1::atomic<objc_selector *> = (null) { Value = (null) } } _imp = { std::__1::atomic<unsigned long> = { Value = 0 }  } } (lldb) p *($7+3) (bucket_t) $11 = { _sel = { std::__1::atomic<objc_selector *> = "" { Value = "" } } _imp = { STD ::__1::atomic<unsigned long> = {Value = 48416 // Until Value is normal}}} (LLDB) p $11.sel()// get sel(sel) $12 = "SaySomething" (LLDB) p $11. Imp (nil,pClass)// Get imp(IMP) $13 = 0x00000001000039d0 (KCObjcBuild '-[LGPerson saySomething])Copy the code

Conclusion:

1. callsaySomethingLater,_mayMaskandoccupiedThese two variables should be related to the cache
2. bucket_tStructure providessel()andimp(nil,pClass)methods
3. saySomethingmethodsselandimpThere,bucketIn,cacheIn the

Break away from source code environment analysiscache

The LLDB debugging from the previous example gives you a basic idea of the structure of cache_t. We can mimic the cache_t code structure so that we don’t need to pass LLDB in the source environment. If you need to call a method, just add code and run it again. This is the most familiar way.

Code:

LGPerson:

#import <Foundation/Foundation.h>
@interface LGPerson : NSObject
@property (nonatomic, copy) NSString *lgName;
@property (nonatomic, strong) NSString *nickName;

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

+ (void)sayHappy;

@end

@implementation LGPerson
- (void)say1{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say2{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say3{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say4{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say5{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say6{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say7{
    NSLog(@"LGPerson say : %s",__func__);
}

+ (void)sayHappy{
    NSLog(@"LGPerson say : %s",__func__);
}
@end

Copy the code

main:

#import <Foundation/Foundation.h> #import "LGPerson.h" #import <objc/runtime.h> typedef uint32_t mask_t; // x86_64 & arm64 asm are less efficient with 16-bits struct kc_bucket_t { SEL _sel; IMP _imp; }; struct kc_cache_t { struct kc_bucket_t *_bukets; // 8 mask_t _maybeMask; // 4 uint16_t _flags; // 2 uint16_t _occupied; / / 2}; struct kc_class_data_bits_t { uintptr_t bits; }; // cache class struct kc_objc_class { Class isa; // Cannot obtain Class superclass; struct kc_cache_t cache; // formerly cache pointer and vtable struct kc_class_data_bits_t bits; }; int main(int argc, const char * argv[]) { @autoreleasepool { LGPerson *p = [LGPerson alloc]; Class pClass = p.class; // objc_clas [p say1]; [p say2]; //[p say3]; //[p say4]; //[p say1]; //[p say2]; //[p say3]; //[pClass sayHappy]; struct kc_objc_class *kc_class = (__bridge struct kc_objc_class *)(pClass); NSLog(@"%hu - %u",kc_class->cache._occupied,kc_class->cache._maybeMask); // a: 1-3 -> 1- 7 // b: (null) - 0x0 // c: 2-7 + say4-0xb850 + no class method // d: NSObject for (mask_t I = 0; i<kc_class->cache._maybeMask; i++) { struct kc_bucket_t bucket = kc_class->cache._bukets[i]; NSLog(@"%@ - %pf",NSStringFromSelector(bucket._sel),bucket._imp); } NSLog(@"Hello, World!" ); } return 0; }Copy the code

llvm:

2021-07-04 13:27:58.629469+0800 003-cache_t -[LGPerson say1] 2021-07-04 13:28:08.029414+0800 003-cache_t -[LGPerson say2] 2021-07-04 13:28:08.029963+0800 003-cache_t Detached source environment Analysis [27782:4884791] 2-3 2021-07-04 13:28:08.030417+0800 003-cache_t Separate source code Environment Analysis [27782:4884791] SAY1-0xb858F 2021-07-04 13:28:08.030502+0800 Say2-0xb808f 2021-07-04 13:28:08.030545+0800 003-cache_t Source code Environment Analysis [27782:4884791] (null) - 0x0fCopy the code

Conclusion:

Since the Class ISA of objc_class inherits from objc_object, the custom structure kc_objc_class must be manually added with Class ISA, otherwise the code conversion will be incorrect

Uncomment say3 and Say4 in mainFunction;

Take another look at LLVM printing:

2021-07-04 13:47:14.016817+0800 003-cache_t From source Environment Analysis [28227:4896303] LGPerson Say: -[LGPerson say1] 2021-07-04 13:47:19.322219+0800 003-cache_t -[LGPerson say2] 2021-07-04 13:47:19.322786+0800 003-cache_t -[LGPerson say3] 2021-07-04 13:47:19.322873+0800 003-cache_t -[LGPerson say4] 2021-07-04 13:47:19.322941+0800 003-cache_t Detached source environment Analysis [28227:4896303] 2-7 2021-07-04 13:47:19.323424+0800 003-cache_t Detached source code Environment Analysis [28227:4896303] say4-0xb9b8f 2021-07-04 13:47:19.323499+0800 003-cache_t Source code Environment Analysis [28227:4896303] (NULL) - 0x0F 2021-07-04 13:47:19.323593+0800 003-cache_t Source code Environment Analysis [28227:4896303] say3 - 0xb9e8f 2021-07-04 13:47:19.323660+0800 003-cache_t Separated from source environment Analysis [28227:4896303] (NULL) - 0x0f 2021-07-04 13:47:19.323725+0800 003-cache_t Detached source environment Analysis [28217:4896303] (NULL) - 0x0f 2021-07-04 13:47:19.323784+0800 003-cache_t Source Environment Analysis [28227:4896303] (NULL) - 0x0f 2021-07-04 13:47:19.323845+0800 003-cache_t Source Environment Analysis [28227:4896303] (null) - 0x0fCopy the code

Conclusion:

1. _occupiedand_maybeMaskIs a role?
2. say1andsay2How did the method disappear?
3. cacheWhy are the locations stored out of order? Such assay4In the front. Why are the second and fourth empty?
4. So what we want to know from this example is_occupiedand_maybeMaskWhat is? You have to look at the source code and see where the value was assigned. Find out how the cache method is inserted intobuketIn the.

cache_tThe source code to explore

First findcache_tMethod cache entryinsert(SEL sel, IMP imp, id receiver), which has parametersselandimp; And there are method namesinsertTake a look at the concrete implementation of it becauseinsertThe code in the code is too much we step by step

Obj-cache. mm source code:

void cache_t::insert(SEL sel, IMP imp, id receiver) { runtimeLock.assertLocked(); // Never cache before +initialize is done if (slowpath(! cls()->isInitialized())) { return; } if (isConstantOptimizedCache()) { _objc_fatal("cache_t::insert() called with a preoptimized cache for %s", cls()->nameForLogging()); } #if DEBUG_TASK_THREADS return _collecting_in_critical(); #else #if CONFIG_USE_CACHE_LOCK mutex_locker_t lock(cacheUpdateLock); #endif ASSERT(sel ! = 0 && cls()->isInitialized()); // Use the cache as-is if until we exceed our expected fill ratio. mask_t newOccupied = occupied() + 1; // 1+1 occupied() Occupied = 0, newOccupied = 1 unsigned oldCapacity = capacity(), capacity = oldCapacity; If (slowPath (isConstantEmptyCache()))) {// Occupied () == 0; // Cache is read-only. Replace it. If (! capacity) capacity = INIT_CACHE_SIZE; Reallocate (oldCapacity, capacity, /* freeOld */false); // When capacity = 0, 1 << 2 -> 0100 = 4, capacity = 4 reallocate(oldCapacity, capacity, /* freeOld */false); // oldCapacity = 0, capacity = 4, freeOld = false } else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) { // newOccupied + 1 <= capacity * 3/4 // Cache is less than 3/4 or 7/8 full. Use it as-is. 4 * 3/4 = 3; 4 * 3/4 = 4; 4 * 3/4 = 4; The final function is: 'newOccupied = 3'; '3 + 1'; Else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) { // Allow 100% cache utilization for small buckets. Use it as-is. // Utilization_cache_size = 1 << 3 = 8) && (newOccupied + 1 <= capacity) } #endif else {// 4*2 = 8 The capacity exceeds the limit of 3/4 capacity = capacity? capacity * 2 : INIT_CACHE_SIZE; If (capacity > MAX_CACHE_SIZE) {// Determine that capacity > 2^(16-1) = 2^15 Capacity = MAX_CACHE_SIZE; the maximum value of the mask is 2^15; capacity = MAX_CACHE_SIZE; // If capacity = 2^15} Reallocate (oldCapacity, capacity, true); FreeOld = true; oldCapacity is reclaimed; bucket_t *b = buckets(); // the first address of the bucket is the first address of the memory mask_t m = capacity - 1; // 4-1=3 : mask = capacity - 1 mask_t begin = cache_hash(sel, m); Mask mask_t I = begin; // Select sel from sel and mask 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)) {if the current bucket is empty incrementOccupied(); // _occupied ++ : The occupied B [I]. Set <Atomic, Encoded>(b, sel, IMP, CLS ()); // Write sel and IMP to the bucket. 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); // If there is a hash conflict, the hash conflict is the method is different but the subscript is the same. // Bad cache #endif DEBUG_TASK_THREADS }Copy the code

Analysis of theinsert

Calculate the current capacity

insertCalculated capacity diagram:

Conclusion:

1. occupied()Getting the current capacity tells you how many are in the cachebucketthe
2. newOccupied = occupied() + 1Which indicates the number of entries you are in the cache
3. oldCapacityThe purpose is to free up old memory during capacity expansion

Open the capacity

Enter the expansion diagram for the first time:

Conclusion:

1. Only the first time the method is cached, the capacity is allocated by defaultcapacity = INIT_CACHE_SIZE 即capacity = 4isMemory size for 4 buckets
2. reallocate(oldCapacity, capacity, /* freeOld */false)Open up memory,freeOldThe variable controls whether old memory is freed

The reallocate method is explored

Code:

ALWAYS_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); // Set Buckets and Mash. Buckets store the first address of newBuckets. Mask = newCapacity; Mask = newCapacity; Mask = newCapacity; Mask = newCapacity; If (freeold) {collect_free(oldCapacity, oldCapacity); if (freeold) {collect_free(oldCapacity, oldCapacity); }}Copy the code

Conclusion:

The Reallocate method does three things: 1) allocateBuckets to open the memory; 2) setBucketsAndMask to set the values of mask and buckets; 3) collect_Free Whether to free the old memory, which is controlled by freeOld

allocateBucketsMethods to explore

AllocateBuckets source code:

size_t cache_t::bytesForCapacity(uint32_t cap) { return sizeof(bucket_t) * cap; Struct bucket_t * :endMarker(struct bucket_t * :endMarker); uint32_t cap) { return (bucket_t *)((uintptr_t)b + bytesForCapacity(cap)) - 1; //2. (first address + memory created) -1: } BUCket_t *cache_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(bytesForCapacity(newCapacity), 1); Bucket_t *end = 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>(newBuckets, (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>(newBuckets, (SEL)(uintPtr_t)1, (IMP)newBuckets, nil); #endif if (PrintCaches) recordNewCache(newCapacity); // Record the new cache return newBuckets; } #elseCopy the code

Conclusion:

The allocateBuckets method does two things:

1. calloc(bytesForCapacity(newCapacity), 1)Open upnewCapacity * bucket_tSize of memory
2. end->setStore the last location of the open memorysel = 1.Imp = the address of the first buket location

setBucketsAndMaskMethods to explore

The source code:

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED 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, # Ifdef __arm__ // Ensure other threads see buckets contents before buckets pointer mega_barrier(); / / to prevent multiple threads access _bucketsAndMaybeMask. Store (uintptr_t newBuckets, memory_order_relaxed); // ensure other threads see new buckets before new mask mega_barrier(); _maybeMask.store(newMask, memory_order_relaxed); _occupied = 0; # elif __x86_64__ | | i386 / / / / macOS and simulator ensure other threads see buckets contents before buckets pointer / / to write data _bucketsAndMaybeMask _bucketsAndMaybeMask. Store (uintptr_t newBuckets, memory_order_release); // ensure other threads see new buckets before new mask // ensure other threads see new buckets before new mask // Write data to _maybeMask. _maybemask.store (newMask, memory_order_release); _occupied = 0; #else #error Don't know how to do setBucketsAndMask on this architecture. #endif }Copy the code

Conclusion:

SetBucketsAndMask writes data to _bucketsAndMaybeMask and _maybeMask based on different architectural systems

collect_freeMethods to explore

Collect_free source code:

void cache_t::collect_free(bucket_t *data, mask_t capacity) { #if CONFIG_USE_CACHE_LOCK cacheUpdateLock.assertLocked(); #else runtimeLock.assertLocked(); #endif if (PrintCaches) recordDeadCache(capacity); _garbage_make_room (); Garbage_byte_size += cache_t::bytesForCapacity(capacity); Garbage_refs [garbage_count++] = data; Cache_t ::collectNolock(false); // Empty the data, reclaim the memory}Copy the code

Conclusion:

Collect_free clears data and reclaims memory

The capacity is less than 3/4

Graph:

Conclusion:

1. The amount of capacity occupied by methods that need to be cachedThe total capacity 3/4If yes, it goes straight to the cache process
2. When you look at apple’s design philosophy, you can see that there is a lot of leeway in what Apple does. One may be for future optimization or expansion, and the other may be for security, as is memory alignment

Capacity is full

Graph:

Conclusion:

1. Apple provides variables, very user-friendly, if you need to fill up the cache, the default is not to fill up
2. Personally, I suggest that you do not fill the storage, just follow the default. If the storage is full, there may be other problems, which is difficult to troubleshoot

Capacity is over 3/4

Graph:

Conclusion:

1. Capacity of more thanThree quarters of, the system will then proceedTwice the capacity, the maximum capacity to be expanded cannot exceedmasktheThe maximum 2 ^ 15
2. During capacity expansion, an important operation is performed to open up new memory and release and reclaim old memoryfreeOld = true

The cache method

Illustration:

Conclusion:

1. First of all getbucket()Point to open up this memoryThe first addressWhich is the first onebucketThe address,bucket()It’s not an array or a linked list. It’s just a blockContinuous memory
2. The hash functionAccording to the cacheselandmaskTo calculate theThe hash index. Why do you need itmask?maskWhat this actually does is it tells the system that you can only save the frontcapacity - 1In, for examplecapacity = 4, the cache method can only store the frontThree empty seats
3. Start caching. If there is no data at the current location, cache the method. If there is a method in this location and it is the same as your method, it is cachedreturn. If there isHash conflictWith the same subscript,selNo, it’s going to happen againhash, the conflict resolution continues to cache

incrementOccupied

The source code:

void cache_t::incrementOccupied() 
{
    _occupied++;
}

Copy the code

Conclusion:

The _occupied automatically increments 1, and _occupied indicates the number of cache methods already stored in memory

cache_hash 和 cache_next

Cache_hash source code:

static inline mask_t cache_hash(SEL sel, mask_t mask) { uintptr_t value = (uintptr_t)sel; #if CONFIG_USE_PREOPT_CACHES // real machine value ^= value >> 7; #endif return (mask_t)(value & mask); // do an and with mask}Copy the code

Source code for cache_next:

#if CACHE_END_MARKER //__arm__ || __x86_64__ || __i386__ static inline mask_t cache_next(mask_t i, mask_t mask) { return (i+1) & mask; } # static inline mask_t cache_next(mask_t I, mask_t mask) {return I? i-1 : mask; } #else #error unexpected configuration #endifCopy the code

Conclusion:

Cache_has mainly generates hash subscripts, and cache_NEXT mainly resolves hash conflicts

Cache write methodset

The source code:

Void bucket_t::set(bucket_t *base, SEL newSel, IMP newImp, Class cls) { ASSERT(_sel.load(memory_order_relaxed) == 0 || _sel.load(memory_order_relaxed) == newSel); // objc_msgSend uses sel and imp with no locks. // It is safe for objc_msgSend to see new imp but NULL sel // (It will get a cache miss but not dispatch to the wrong place.) // It is unsafe for objc_msgSend to see old imp and new sel. // Therefore we write new imp, wait a lot, Then write new sel. // UintPtr_t newIMP = (impEncoding == Encoded? encodeImp(base, newImp, newSel, cls) : (uintptr_t)newImp); If (atomicity == Atomic) {// decorate symbol Atomic _imp. Store (newIMP, memory_order_relaxed); if (_sel.load(memory_order_relaxed) ! = newSel) { #ifdef __arm__ mega_barrier(); _sel.store(newSel, memory_order_relaxed); #elif __x86_64__ || __i386__ _sel.store(newSel, memory_order_release); #else #error Don't know how to do bucket_t::set on this architecture. #endif } } else { _imp.store(newIMP, memory_order_relaxed); // Write _imp _sel.store(newSel, memory_order_relaxed); // Write _sel}}Copy the code

Conclusion:

The set writes sel and IMP to the bucket, starting the caching method

insertCalling process

Xcode turns off assembly debugging to explore how calling an instance method calls the insert method in cache. Put a breakpoint in the INSERT method and run the source code

Graph:

Conclusion:

The stack information shows the process of calling the INSERT method: _objc_msgSend_uncached –> lookUpImpOrForward –> log_and_fill_cache –> cache_t:: INSERT

The stack is only shown to _objC_msgsend_cached, but we call [p say1] which is the instance method and then we call cache_t:: INSERT. We now know part of the process _OBJC_MSgSend_cached to CACHE_T :: INSERT. The process of [p say1] to _objC_msgsend_cached is not clear. You can only open Xcode’s assembly debugging function to see the assembly flow

Assembly diagram:Conclusion:

1. [p say1]The underlying implementation isobjc_msgSendThe method, the method isMessage sending methodThis will be explained in the next section
2. callinsertMethod flow:[p say1]The underlying implementationobjc_msgSend –> _objc_msgSend_uncached –> lookUpImpOrForward –> log_and_fill_cache –> cache_t::insert

insertCall flow chart

Graph LR A[method] -.-> B(objc_msgSend) -.-> C(_objc_msgSend_uncached) -.-> D(lookUpImpOrForward) -.-> E(log_and_fill_cache)  -.-> cache_t::insert

Supplement:

Little knowledge:

1. _sel _IMP can be found in the previous section
2. Hash value is easy to add or delete, and then add
3. Arrays are looked up by index
4. Linked lists are good for array linking
5. The hashFunction:> > % subscript -> data
6. 8% 5 = 1 VS 8% 6 = 1
7. The capacity ofThree quarters of-> Load factor0.75Space utilization +Hash conflict-> The underlying list + Red and black treeFrequency is too much

bucktstructurellvmdebugging

Important :_bucketsAndMaybeMask stores the first bucket address

LLVM debugging:

2021-07-03 21:25:55.822979+0800 KCObjcBuild[21684:4692396] LGPerson say: -[LGPerson say1] KCObjcBuild was compiled with optimization - stepping may behave oddly; variables may not be available. (lldb) p/x LGPerson.class (Class) $0 = 0x0000000100008510 LGPerson (lldb) p (cache_t *)0x0000000100008520 (cache_t *) $1 = 0x0000000100008520 (lldb) p *$1 (cache_t) $2 = { _bucketsAndMaybeMask = { std::__1::atomic<unsigned long> = { Value = 4301421904 } } = { = { _maybeMask = { std::__1::atomic<unsigned int> = { Value = 3 } } _flags = 32808 _occupied = 1 } _originalPreoptCache = { std::__1::atomic<preopt_cache_t *> = { Value = 0x0001802800000003 } } } } (lldb) p $2.buckets() (bucket_t *) $3 = 0x0000000100627d50 (lldb) p *$3 (bucket_t) $4 = { _sel = { std::__1::atomic<objc_selector *> = (null) { Value = (null) } } _imp = { std::__1::atomic<unsigned long> = { Value = 0 } } } (lldb) p $3[1] (bucket_t) $5 = { _sel = { std::__1::atomic<objc_selector *> = "" { Value = "" } } _imp =  { std::__1::atomic<unsigned long> = { Value = 48912 } } } (lldb) p $5.sel() (SEL) $6 = "say1" (lldb) p $3+1 (bucket_t *) $7 = 0x0000000100627d60 (lldb) p $7->sel() (SEL) $8 = "say1" (lldb) p $2._bucketsAndMaybeMask (explicit_atomic<unsigned long>) $9 = { std::__1::atomic<unsigned long> = { Value = 4301421904 } } (lldb) p/x 4301421904  (long) $10 = 0x0000000100627d50 (lldb)Copy the code

Conclusion:

buckets = _bucketsAndMaybeMask $3
Copy the code

bucketMaskPay attention to the point

1. Pay attention to the pointbucketMaskPay attention to the platformx86-64,ArmV64Such as the address of the small end
2. Big endaddressFrom left to right
3. The small endaddressFrom right to left

For example:

lldb) x p
0x100661c70: 11 85 00 00 01 80 1d 01 00 00 00 00 00 00 00 00  ................
0x100661c80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
(lldb) 
Copy the code

Conclusion:

Select the first eight bits as the big endian of the address: 0x1185000001801D01 Little endian: 0x011D800100008511Copy the code