OC Underlying Principles 05- Cache_t Exploration

Class structure

In OC basic principle 04- Class structure analysis, classes are mainly composed of isa, superclass, cache, bits.

This article will only explore cache_t.

Cache_t explore

Cache_t source

struct cache_t {
private:
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask;/ / 8
    union {
        struct {
            explicit_atomic<mask_t>    _maybeMask; / / 4
#if __LP64__
            uint16_t                   _flags; / / 2
#endif
            uint16_t                   _occupied; / / 2
        };
        explicit_atomic<preopt_cache_t *> _originalPreoptCache;/ / 8
    };

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    // _bucketsAndMaybeMask is a buckets_t pointer
    // _maybeMask is the buckets mask

    staticconstexpr uintptr_t bucketsMask = ~0ul; static_assert(! CONFIG_USE_PREOPT_CACHES,"preoptimized caches not supported");
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
    static constexpr uintptr_t maskShift = 48;
    static constexpr uintptr_t maxMask = ((uintptr_t)1< < (64 - maskShift)) - 1;
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << maskShift) - 1;
    
    static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers.");
#if CONFIG_USE_PREOPT_CACHES
    static constexpr uintptr_t preoptBucketsMarker = 1ul;
    static constexpr uintptr_t preoptBucketsMask = bucketsMask & ~preoptBucketsMarker;
#endif
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    // _bucketsAndMaybeMask is a buckets_t pointer in the low 48 bits
    // _maybeMask is unused, the mask is stored in the top 16 bits.

    // How much the mask is shifted by.
    static constexpr uintptr_t maskShift = 48;

    // Additional bits after the mask which must be zero. msgSend
    // takes advantage of these additional bits to construct the value
    // `mask << 4` from `_maskAndBuckets` in a single instruction.
    static constexpr uintptr_t maskZeroBits = 4;

    // The largest mask value we can store.
    static constexpr uintptr_t maxMask = ((uintptr_t)1< < (64 - maskShift)) - 1;
    
    // The mask applied to `_maskAndBuckets` to retrieve the buckets pointer.
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
    
    // Ensure we have enough bits for the buckets pointer.
    static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS,
            "Bucket field doesn't have enough bits for arbitrary pointers.");

#if CONFIG_USE_PREOPT_CACHES
    static constexpr uintptr_t preoptBucketsMarker = 1ul;
#if __has_feature(ptrauth_calls)
    / / 63.. 60: hash_mask_shift
    / / 59.. 55: hash_shift
    / / 54.. 1: buckets ptr + auth
    // 0: always 1
    static constexpr uintptr_t preoptBucketsMask = 0x007ffffffffffffe;
    static inline uintptr_t preoptBucketsHashParams(const preopt_cache_t *cache) {
        uintptr_t value = (uintptr_t)cache->shift << 55;
        // masks have 11 bits but can be 0, so we compute
        // the right shift for 0x7fff rather than 0xffff
        return value | ((objc::mask16ShiftBits(cache->mask) - 1) < <60);
    }
#else
    / / 63.. 53: hash_mask
    / / 52.. 48: hash_shift
    / / 47.. 1: buckets ptr
    // 0: always 1
    static constexpr uintptr_t preoptBucketsMask = 0x0000fffffffffffe;
    static inline uintptr_t preoptBucketsHashParams(const preopt_cache_t *cache) {
        return (uintptr_t)cache->hash_params << 48;
    }
#endif
#endif // CONFIG_USE_PREOPT_CACHES
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
    // _bucketsAndMaybeMask is a buckets_t pointer in the top 28 bits
    // _maybeMask is unused, the mask length is stored in the low 4 bits

    static constexpr uintptr_t maskBits = 4;
    static constexpr uintptr_t maskMask = (1 << maskBits) - 1;
    staticconstexpr uintptr_t bucketsMask = ~maskMask; static_assert(! CONFIG_USE_PREOPT_CACHES,"preoptimized caches not supported");
#else
#error Unknown cache mask storage type.
#endif

    bool isConstantEmptyCache() const;
    bool canBeFreed() const;
    mask_t mask() const;

#if CONFIG_USE_PREOPT_CACHES
    void initializeToPreoptCacheInDisguise(const preopt_cache_t *cache);
    const preopt_cache_t *disguised_preopt_cache() const;
#endif

    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);

    void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
    void collect_free(bucket_t *oldBuckets, mask_t oldCapacity);

    static bucket_t *emptyBuckets();
    static bucket_t *allocateBuckets(mask_t newCapacity);
    static bucket_t *emptyBucketsForCapacity(mask_t capacity, bool allocate = true);
    static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);
    void bad_cache(id receiver, SEL sel) __attribute__((noreturn, cold));

public:
    // The following four fields are public for objcdt's use only.
    // objcdt reaches into fields while the process is suspended
    // hence doesn't care for locks and pesky little details like this
    // and can safely use these.
    unsigned capacity() const;
    struct bucket_t *buckets() const;
    Class cls() const;

#if CONFIG_USE_PREOPT_CACHES
    const preopt_cache_t *preopt_cache() const;
#endif

    mask_t occupied() const;
    void initializeToEmpty();

#if CONFIG_USE_PREOPT_CACHES
    bool isConstantOptimizedCache(bool strict = false, uintptr_t empty_addr = (uintptr_t)&_objc_empty_cache) const;
    bool shouldFlush(SEL sel, IMP imp) const;
    bool isConstantOptimizedCacheWithInlinedSels() const;
    Class preoptFallbackClass() const;
    void maybeConvertToPreoptimized();
    void initializeToEmptyOrPreoptimizedInDisguise();
#else
    inline bool isConstantOptimizedCache(bool strict = false, uintptr_t empty_addr = 0) const { return false; }
    inline bool shouldFlush(SEL sel, IMP imp) const {
        return cache_getImp(cls(), sel) == imp;
    }
    inline bool isConstantOptimizedCacheWithInlinedSels() const { return false; }
    inline void initializeToEmptyOrPreoptimizedInDisguise() { initializeToEmpty(); }
#endif

    void insert(SEL sel, IMP imp, id receiver);
    void copyCacheNolock(objc_imp_cache_entry *buffer, int len);
    void destroy();
    void eraseNolock(const char *func);

    static void init();
    static void collectNolock(bool collectALot);
    static size_t bytesForCapacity(uint32_t cap);

#if __LP64__
    bool getBit(uint16_t flags) const {
        return _flags & flags;
    }
    void setBit(uint16_t set) {
        __c11_atomic_fetch_or((_Atomic(uint16_t) *)&_flags, set, __ATOMIC_RELAXED);
    }
    void clearBit(uint16_t clear) {
        __c11_atomic_fetch_and((_Atomic(uint16_t) *)&_flags, ~clear, __ATOMIC_RELAXED);
    }
#endif

#if FAST_CACHE_ALLOC_MASK
    bool hasFastInstanceSize(size_t extra) const
    {
        if (__builtin_constant_p(extra) && extra == 0) {
            return _flags & FAST_CACHE_ALLOC_MASK16;
        }
        return _flags & FAST_CACHE_ALLOC_MASK;
    }

    size_t fastInstanceSize(size_t extra) const
    {
        ASSERT(hasFastInstanceSize(extra));

        if (__builtin_constant_p(extra) && extra == 0) {
            return _flags & FAST_CACHE_ALLOC_MASK16;
        } else {
            size_t size = _flags & FAST_CACHE_ALLOC_MASK;
            // remove the FAST_CACHE_ALLOC_DELTA16 that was added
            // by setFastInstanceSize
            returnalign16(size + extra - FAST_CACHE_ALLOC_DELTA16); }}void setFastInstanceSize(size_t newSize)
    {
        // Set during realization or construction only. No locking needed.
        uint16_t newBits = _flags & ~FAST_CACHE_ALLOC_MASK;
        uint16_t sizeBits;

        // Adding FAST_CACHE_ALLOC_DELTA16 allows for FAST_CACHE_ALLOC_MASK16
        // to yield the proper 16byte aligned allocation size with a single mask
        sizeBits = word_align(newSize) + FAST_CACHE_ALLOC_DELTA16;
        sizeBits &= FAST_CACHE_ALLOC_MASK;
        if (newSize <= sizeBits) {
            newBits |= sizeBits;
        }
        _flags = newBits;
    }
#else
    bool hasFastInstanceSize(size_t extra) const {
        return false;
    }
    size_t fastInstanceSize(size_t extra) const {
        abort();
    }
    void setFastInstanceSize(size_t extra) {
        // nothing
    }
#endif
};
Copy the code

CACHE_MASK_STORAGE:
#define CACHE_MASK_STORAGE_OUTLINED 1
#define CACHE_MASK_STORAGE_HIGH_16 2
#define CACHE_MASK_STORAGE_LOW_4 3
#define CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS 4

#if defined(__arm64__) && __LP64__ // True machine &&64 bits
 #if TARGET_OS_OSX || TARGET_OS_SIMULATOR
 #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
 #else#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16 #endif #elif defined(__arm64__) && ! __LP64__ #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_LOW_4 #else
 #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED
#endif
Copy the code
Simulator 32-bit processor testing requires i386 architecture (iphone5,iphone5s and below; Simulator 64-bit processor testing requires x86_64 architecture (iphone6 and up); Real 64-bit processors require arm64 architecture (iphone6,iphone6p and up); MacOSX requires i386 architecture; Real 32-bit processors require armv7 architecture (iphone4 real /armv7); Real 32-bit processors require the armv7s architecture (ipnone5,iphone5s real /armv7s).

Cache_t source code is analyzed using the 64-bit processor architecture CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16.

Explicit_atomic simply wraps the generics atomically safe. For example explicit_atomic < uintptr_t > _bucketsAndMaybeMask; Uintptr_t _bucketsAndMaybeMask;

Cache_t consists of _buckets, _mask, _flags, _occupied;

Bucket_t = 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__
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif

public:
    inline SEL sel() const { return _sel.load(memory_order_relaxed); }
    inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const{... }}Copy the code

Bucket_t contains sel and IMP as follows:

Two cache exploration modes are available

Sample code:

//LGPerson.h
@property (nonatomic, copy) NSString *nickName;
@property (nonatomic, strong) NSString *name;

- (void)lgPersonInstanceMethod1;
- (void)lgPersonInstanceMethod2;
- (void)lgPersonInstanceMethod3;
- (void)lgPersonInstanceMethod4;
- (void)lgPersonInstanceMethod5;
+ (void)lgPersonClassMethod;

//LGPerson.m
- (void)lgPersonInstanceMethod1{
    NSLog(@"lgPersonInstanceMethod1");
}
- (void)lgPersonInstanceMethod2{
    NSLog(@"lgPersonInstanceMethod2");
}
- (void)lgPersonInstanceMethod3{
    NSLog(@"lgPersonInstanceMethod3");
}
- (void)lgPersonInstanceMethod4{
    NSLog(@"lgPersonInstanceMethod4");
}
- (void)lgPersonInstanceMethod5{
    NSLog(@"lgPersonInstanceMethod5");
}
+ (void)lgPersonClassMethod{
    NSLog(@"LGPerson Class Method");
}


/ / the main m calls
LGPerson *person = [LGPerson alloc];
Class pClass = [person class];
// person.nickName = @"nick";
[person lgPersonInstanceMethod1];
Copy the code

Cache exploration – Approach 1 through the source code environment`lldb`print

This is not that way to get throughMachOViewValidation:For multiple methods, two methods should be cached when the breakpoint runs through the second class method

Buckets is a collection type so you can print other methods in one of the following ways: PassThe pointer offset ： Or byArray offset modePrint:

Cache exploration – Approach 2 explores validation without objC source environment

Copy the key code of the source environment into the main file.

typedef uint32_t mask_t;  // x86_64 & arm64 asm are less efficient with 16-bits

struct lg_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct lg_cache_t {
    struct lg_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct lg_class_data_bits_t {
    uintptr_t bits;
};

struct lg_objc_class {
    Class ISA;
    Class superclass;
    struct lg_cache_t cache;             // formerly cache pointer and vtable
    struct lg_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        LGPerson *p  = [LGPerson alloc];
        Class pClass = [LGPerson class];  // objc_clas
        [p say1];
        [p say2];
        //[p say3];
        //[p say4];

        struct lg_objc_class *lg_pClass = (__bridge struct lg_objc_class *)(pClass);
        NSLog(@"%hu - %u",lg_pClass->cache._occupied,lg_pClass->cache._mask);
        for (mask_t i = 0; i<lg_pClass->cache._mask; i++) {
            // Prints the bucket
            struct lg_bucket_t bucket = lg_pClass->cache._buckets[i];
            NSLog(@"%@ - %p",NSStringFromSelector(bucket._sel),bucket._imp);
        }

        
        NSLog(@"Hello, World!");
    }
    return 0;
}

//LGPerson.h
@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;

//LGPerson.m
- (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__);
}
Copy the code

Print the following: when commented out[p say3]; [p say4];Print the following:Open comments and print the following:The following problems were found:

_occupiedand_maskWhat is the
As the number of methods increases,_occupiedand_maskIt’s going to be 2-3 -> 2-7
Why is it printed?cache._bucketsthebucketFor example, in 2-7, only say3 and say4 have function Pointers
The printedcache._bucketsSay3, say4, say3, say4, say3

Let’s explore why this is so.

Cache_t Underlying mechanism analysis

Clue: First, we start with the _mask property in cache_t and look for the function that causes the change in cache_t. We find incrementOccupied().

`incrementOccupied()`function

The specific implementation of this function is as follows:

void incrementOccupied(); / / Occupied since

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

Search the source for where to call this method:

Global searchincrementOccupied()Function, found only incache_ttheinsertThe method has a call:

`insert`methods

Insert method key code is as follows:

void cache_t::insert(SEL sel, IMP imp, id receiver){...// Use the cache as-is if until we exceed our expected fill ratio.
    / / the first step
    mask_t newOccupied = occupied() + 1;
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    / / the second step
    if (slowpath(isConstantEmptyCache())) { // Create and instantiate in rare cases
        // Cache is read-only. Replace it.
        if(! capacity) capacity = INIT_CACHE_SIZE; reallocate(oldCapacity, capacity,/* freeOld */false);
    }
    else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) {
        // Cache is less than 3/4 or 7/8 full. Use it as-is.
    }
#if CACHE_ALLOW_FULL_UTILIZATION
    else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) {
        // Allow 100% cache utilization for small buckets. Use it as-is.
    }
#endif
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);
    }

    / / the third step
    bucket_t *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.
    do {
        if (fastpath(b[i].sel() == 0)) {
            incrementOccupied();
            b[i].set<Atomic, Encoded>(b, 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)); bad_cache(receiver, (SEL)sel); #endif/ /! DEBUG_TASK_THREADS
}
Copy the code

insertMethod, understood ascache_tInsert, whilecacheIs stored insel-imp, so the cache works frominsertMethods Start analysis.

It is mainly divided into the following parts:

[Step 1]To calculateOut of the currentCache usage
[Step 2] According toCache usageDetermine the operation to be performed
[Step 3] For the need to storebucketAn internalImp and SEL assignments

Step one, according to`occupied`To calculate the current cache usage

Where, the first step is to calculate the current cache usage according to the value of occupied. If the attribute is not assigned and no method is called, the value of occupied is 0 and newOccupied is 1, as shown below:

mask_t newOccupied = occupied() + 1;
Copy the code

Regarding the calculation of cache usage, there are the following notes:

allocWhen applying for space, at this timeObject created, if called againinitMethod,occupiedWill also be+ 1
whenThere are property assignmentsIs called implicitlysetMethod,occupiedIt’s also going to increase, which isIf there are several attributes assigned, occupied will add several to the existing one
whenThere are method callsWhen,occupiedIt’s also going to increase, which isFor a few calls, it adds a few more to the occupied version

The second step is to determine the operation based on the cache usage

If it isFirst CreationIs enabled by default4A capacity

if (slowpath(isConstantEmptyCache())) { Occupied (); occupied(); occupied()
    // Cache is read-only. Replace it.
    if(! capacity) capacity = INIT_CACHE_SIZE;// During initialization, allocate 4 (1<<2 -- 100) capacities
    reallocate(oldCapacity, capacity, /* freeOld */false); // Create space
    // So far, the if process has operated on initialization
}
Copy the code

If the cache is occupiedLess than or equal to 3/4, no processing is done

else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { 
    // Cache is less than 3/4 full. Use it as-is.
}
Copy the code

If the cache is occupiedMore than three-quarters, you need to performTwice the capacityAs well asMake space again

else {// If it is 3/4 larger, it needs to be expanded (double capacity).
    // Algorithm: If 'capacity' is present, double the capacity. If 'capacity' is not present, initialize to 4
    capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  2*4 = 8
    if (capacity > MAX_CACHE_SIZE) {
        capacity = MAX_CACHE_SIZE;
    }
    // It was once there, but it is full and needs to be recombed
    reallocate(oldCapacity, capacity, true);
    // The memory capacity is expanded
}
Copy the code

We found that the RealLocate method is called when the first creation and cache usage exceeds 3/4, and we need to double the capacity and respace. Let’s look at the RealLocate method.

`reallocate`Space opening method

The main steps are as follows:

Step 1`allocateBuckets`methods

The allocateBuckets method applies to the system to open memory, that is, to open a bucket, which is only a temporary variable.

Step 2`setBucketsAndMask`methods

SetBucketsAndMask method: Stores the temporary bucket into the cache.

Step 3`cache_collect_free`methods

If there are old buckets, they need to clear the previous cachecache_collect_freeMethod, the source code implementation is as follows:The method mainly consists of the following steps:

_garbage_make_roomMethod: Create a garbage collection space
- If it isFor the first time,, you need toAllocating reclaimed space
- ifNot the first time, the memory segment is enlarged, i.eOriginal memory *2
- recordstorageThis time thebucket
garbage_refs[garbage_count++] = data; Store SEL-IMP in the back
Cache_collect Method: Garbage collection to clean up old buckets

The third step is to perform internal IMP and SEL assignments for the buckets to be stored

    bucket_t *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.
    do {
        if (fastpath(b[i].sel() == 0)) {// Sel is not stored
            incrementOccupied();// Increase the occupied size by 1
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());// Store sel-IMP
            return;
        }
        if (b[i].sel() == sel) {// The sel stored in the current hash subscript is equal to the sel to be inserted
            // 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));Copy the code

This section focuses on calculating the hash subscript of SEL-IMP storage based on the cache_hash method, or hash algorithm. If the sel stored in the current hash subscript is not equal to the sel to be inserted, the cache_next (hash collision) algorithm is used to re-hash the sel to obtain a new subscript and then compare the sel to store it.

If I hash the position of the subscriptNot stored selIs the subscript positionGet sel is equal to 0At this time willSel - imp storageGo in and take itoccupiedTake up the sizeAdd 1;
If the current hash subscript stores selIs equal to theThe sel to be inserted is returned directly.

The source code of the two hash algorithms involved is as follows:

cache_hash: Hash algorithm

    static inline mask_t cache_hash(SEL sel, mask_t mask) 
    {
        return (mask_t)(uintptr_t)sel & mask; // select sel & mask (mask = cap-1)
    }
Copy the code

cache_next: Hash collision algorithm

#if __arm__  ||  __x86_64__  ||  __i386__
// objc_msgSend has few registers available.
// Cache scan increments and wraps at special end-marking bucket.
#define CACHE_END_MARKER 1
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask; // add a new subscript to mask
}

#elif __arm64__
// objc_msgSend has lots of registers available.
// Cache scan decrements. No end marker needed.
#define CACHE_END_MARKER 0
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask; // if I is empty, I = mask, mask = cap-1, if not empty, I = -1, forward insert SEL-imp
}
Copy the code

That completes the basic analysis of cache_t, and we now have the answers to some of the previous questions.

Problem solving

What are _occupied and _mask
- _maskWhat is the
  - _maskRefers to theMask dataforThe hash algorithmorHash collision algorithmIn the calculationThe hash index, includingmaskIs equal to thecapacity - 1.
- _occupiedWhat is the
  - _occupiedRepresents the hash tablesel-imp 的Take up the sizeThe allocated memory is already storedsel-impOf theThe number of)
  - The method callOccupied
  - initCan lead to_occupiedchange becauseinitObject method as well
  - Property assignment and get, will also be called implicitly, resulting in_occupiedchange
- The maximum number of caches is 2 to the power of 15. The lower 48 bits of _maskAndBuckets are buckets’ addresses and the higher 16 bits are masks. Cache_t is stored in a hash table and uses linear detection to resolve hash collisions
_occupied and _mask will change as the number of methods increases
- Because in thecacheAt initialization, the space allocated is4As method calls increase, when storedSel - number of imp, i.e.,The sum of newOccupied + CACHE_END_MARKER (equal to 1) exceeds 3/4 of the total capacity, such as a4A, when_occupiedIs equal to the2When, you need to be rightcacheMemory forTwice the capacity.
Why is it printed?cache._bucketsthebucketFor example, in 2-7, only say3 and say4 have function Pointers
- The reason is that incapacityIt, will beAll the original memory is clearedAgain,To apply forthememoryThe result of.
The printedcache._bucketsSay3, say4, say3, say4, say3
- becausesel-impThe storage is throughThe hash algorithm computes the subscripts, its calculated subscript may have stored SEL, soThe hash subscript needs to be recalculated using a hash collision algorithmSo the subscripts are random, not fixed.

`cache_fill`methods

Global searchinsert(Method, found onlycache_fillMethod calls fit.Global searchcache_fillCsel-imp = sel-IMP = sel-IMP = sel-IMPaboutobjc_msgSendThis will be analyzed in the next article.

cacheThe analysis flow chart is as follows:The focus of this article is to analyze the principle of cache storagecache_tThe process of writing, i.einsertMethods.

The article lists

List of blog posts

reference

Analysis of cache principle in objc_class

OC Underlying Principles 05- Cache_t Exploration

Class structure

Cache_t explore

Cache_t source

Two cache exploration modes are available

Cache exploration – Approach 1 through the source code environmentlldbprint

Cache exploration – Approach 2 explores validation without objC source environment

Cache_t Underlying mechanism analysis

incrementOccupied()function

insertmethods

Step one, according tooccupiedTo calculate the current cache usage

The second step is to determine the operation based on the cache usage

reallocateSpace opening method

Step 1allocateBucketsmethods

Step 2setBucketsAndMaskmethods

Step 3cache_collect_freemethods