OC Low-level exploration (8) : cache_t

The role of the cache is easy to understand is the cache, the cache are familiar, just for next time to quickly read performance, analyzed the bits, before we can see in the class structure cache_t, caching, we explore the next

Data structure for cache_T

Member variables

struct cache_t {
private:
    // explicit_atomic
      
        define type to allow conversion, uintptr_t = unsigned long
      
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask;  / / 8
    // Member variables are mutually exclusive
    union {
        struct {
            // Uint16_t: uint32_t
            / / mask
            explicit_atomic<mask_t>    _maybeMask; / / 4
#if __LP64__ // The architecture is 64-bit
            / / tag
            uint16_t                   _flags; / / 2
#endif
            // Occupied number
            uint16_t                   _occupied; / / 2
        };
        // Pointer, raw rule cache
        explicit_atomic<preopt_cache_t *> _originalPreoptCache; / / 8}; . . }Copy the code

Constant in real machine architecture

    / / real machine
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    
    // _bucketsAndMaybeMask is a buckets_t pointer in the low 48 bits
    // _bucketsAndMaybeMask is the lower 48 bits of the buckets_t pointer
    
    // _maybeMask is unused, the mask is stored in the top 16 bits.
    // _maybeMask Is not used. The mask is 16 bits high

    // How much the mask is shifted by.
    // How much the mask needs to be moved
    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.
    // The mask must have 4 extra bits, which msgSend uses to build the value
    // _maskAndBuckets' mask << 4 '(the mask is moved 4 bits to the left) is in an instruction
    static constexpr uintptr_t maskZeroBits = 4;
    
    // The largest mask value we can store.
    // The maximum number of masks that can be stored 1 << 64-48-1
    static constexpr uintptr_t maxMask = ((uintptr_t)1< < (64 - maskShift)) - 1;
    
    // The mask applied to `_maskAndBuckets` to retrieve the buckets pointer.
    // bucketsMask is used for '_maskAndBuckets' to retrieve the mask of the buckets pointer
    // 1 << 48-4-1
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
    
    // Ensure we have enough bits for the buckets pointer.
    // Make sure we have enough bits for buckets.
    // MACH_VM_MAX_ADDRESS 0x10 0000 0000 = 1 << 36
    // bucketsMask = 1 << 43
    static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS,
            "Bucket field doesn't have enough bits for arbitrary pointers.");
          
 #if CONFIG_USE_PREOPT_CACHES // The real machine is 1
    // Buckets mark
    static constexpr uintptr_t preoptBucketsMarker = 1ul;
    
#if __has_feature(ptrauth_calls)  // A12 above is 1, arme64e

struct preopt_cache_t {
    int32_t  fallback_class_offset; / / 4
    union {
        struct {
            uint16_t shift       :  5; 
            uint16_t mask        : 11; 
        };
        uint16_t hash_params; 
    };
    uint16_t occupied    : 14; 
    uint16_t has_inlines :  1;
    uint16_t bit_one     :  1;
    preopt_cache_entry_t entries[];

    inline int capacity(a) const {
        return mask + 1; }};/ / 63.. 60: hash_mask_shift
/ / 59.. 55: hash_shift
/ / 54.. 1: buckets ptr + auth
// 0: always 1

0x007ffffffffffe = 0x007ffffffffe = 0x007ffffffffe
static constexpr uintptr_t preoptBucketsMask = 0x007ffffffffffffe;
// Buckets hash parameter
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
    // The mask has 11 bits, but may be 0, so we calculate the right shift 0x7fff instead of 0xFFFF
    return value | ((objc::mask16ShiftBits(cache->mask) - 1) < <60);
}
#else / / A12

/ / 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;
}
Copy the code

It can be seen thatcache_twithbucketsHas much to do with

struct bucket_t *buckets(a) const;

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
Copy the code

bucketsDeposit isselwithimp, but different architectures are stored in different locations

Function (incomplete)

bool isConstantEmptyCache() const;

bool cache_t::isConstantEmptyCache(a) const
{
    return
        occupied() == 0  &&
        buckets() == emptyBucketsForCapacity(capacity(), false);
}

mask_t cache_t::occupied(a) const
{
    return _occupied;
}

Copy the code

Whether the cache is empty_occupied == 0
maskAndBuckets >> maskShift (48)If there is a value

bool canBeFreed() const;

bool cache_t::canBeFreed() const { return ! isConstantEmptyCache() && ! isConstantOptimizedCache(); }Copy the code

Whether it can be released
The cache is not empty and is not a priority cache.

mask_t mask() const;

A:mask_t cache_t::mask(a) const
{
 // maskAndBuckets
 // maskShift = 48
    uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return maskAndBuckets >> maskShift;
}
Copy the code

maskAndBucketsThat isbucketsThe first address
maskShift = 48
That isbucketsThe first addressMoves to the right of 48

initializeToPreoptCacheInDisguise

void cache_t::initializeToPreoptCacheInDisguise(const preopt_cache_t *cache)
{
    // preopt_cache_t::bit_one is 1 which sets the top bit
    // And is never set on any valid selector // Is not set on a valid selector

    uintptr_t value = (uintptr_t)cache + sizeof(preopt_cache_t) -
            (bucket_t::offsetOfSel() + sizeof(SEL));

    _originalPreoptCache.store(nullptr.std::memory_order_relaxed);
    setBucketsAndMask((bucket_t *)value, 0);
    _occupied = cache->occupied;
}
 * +----------------+----------------+
 * |      IMP       |       SEL      | << a bucket_t* + -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- -- -- -... *preopt_cache_t >>|               1|... * + -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- -- -- -...Copy the code

Place the shared cache tag on sel

void incrementOccupied();

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

Occupied quantity ++

Insert cache insert(SEL SEL, IMP IMP, ID receiver)

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    / / the mutex
    runtimeLock.assertLocked();

    // Whether the class has been initialized
    // Never cache before +initialize is done
    if(slowpath(! cls()->isInitialized())) {return;
    }
    
    // Whether the cache is shared
    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

    // If sel exists and the class is initializedASSERT(sel ! =0 && cls()->isInitialized());

    // Use the cache as-is if until we exceed our expected fill ratio.
    // Use the cache to know that the fill rate is exceeded
    // Number of new methods == _occupied + 1
    mask_t newOccupied = occupied() + 1; // _occupied + 1
    /* mask_t cache_t::mask() const { uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed); return maskAndBuckets >> maskShift; } * /
    // capacity() = mask() ? mask()+1 : 0;
    
    // Get the capacity
    unsigned oldCapacity = capacity(), capacity = oldCapacity; //
    if (slowpath(isConstantEmptyCache())) {
        // If empty, initialize buckets again, INIT_CACHE_SIZE = 4
        // The capacity is 4
        // Cache is read-only. Replace it.
        if(! capacity) capacity = INIT_CACHE_SIZE; reallocate(oldCapacity, capacity,/* freeOld */false);
    }
    // Start newOccupied = 1 + 0 <= 2 * 7/8
    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 {
        // Double the capacity
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        // Clear the old cache and create a new cache
        reallocate(oldCapacity, capacity, true);
    }

    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    /*static inline mask_t cache_hash(SEL sel, mask_t mask) { uintptr_t value = (uintptr_t)sel; #if CONFIG_USE_PREOPT_CACHES value ^= value >> 7; #endif return (mask_t)(value & mask); } * /
    // Hash algorithm to calculate the initial position
    // (sel ^ (sel >> 7)) & 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.
    // Find the first unused position to insert
    do {
     // Check that sel exists
        if (fastpath(b[i].sel() == 0)) {
            // 存在 _occupied++
            // Save SEL and IMP to bucket
            // 
            // enum Atomicity { Atomic = true, NotAtomic = false };
            // enum IMPEncoding { Encoded = true, Raw = false };
            incrementOccupied();
            // Save SEL and IMP to bucket
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());
            return;
        }
        // If the sel in the current seat is the sel that is being cached, return
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }
     // If the current I seat has been cached, and is not the sel to be cached, then find the next seat
    // i ? i-1 : mask; Go ahead and find the next seat, and if you find the first seat, put it in m's seat, which is capacity minus 1
    // And the position cannot be the first position, if so, exit the loop
    } while(fastpath((i = cache_next(i, m)) ! = begin)); bad_cache(receiver, (SEL)sel);#endif / /! DEBUG_TASK_THREADS
}
Copy the code

classInitialize or not
Shared cache or not
selIt’s not zero, and it checks againclassInitialize or not
newOccupied = occupied + 1, the occupied quantity increases by 1
Get the size of the capacity
Is the cache empty, is the capacity empty,
If it’s empty capacitycapacity = 4To open up memory again according to capacity
If not null judgmentnewOccupied + 1 <= capacity * 3 / 4
trueIs not processed
false,Capacity = capacity? capacity * 2 : 4The biggestcapacity = 1 << 16.Empty the old cache and create a new cache space
Take out thebuckets, assignmentmask = capacity - 1
Using the hash function to determine where to start,begin = sel ^ (sel >> 7) & mask
Check whether the begin location is cachedbuckets[i]The bucket in the coarse
Check whether the current cache is the SEL to be cached, if so return
Cache_next looks up for the next slice of cachei = i ? i - 1 : mask, find the bit 0, then cache the position of mask, and cycle in turn
If not, it is an error cache

Conclusion:

_bucketsAndMaybeMask 是 bucketsPointer to
cache_tIs the same toobucketsThe cachesel 和 imp
selandimpIt’s one to one
The cache will initially have a capacity of4Contiguous memory space
Then through thesel ^= sel << 7 & maskThe hash function, let’s figure out the original onekeyTo store the correspondingimp
If thekeyIf there is a value, passkey - 1Let’s figure out the next onekey.
whenkey - 1 = 0,Key = mask = Capacity -1As akey

OC Low-level exploration (8) : cache_t

Data structure for cache_T

Member variables

Function (incomplete)

bool isConstantEmptyCache() const;

bool canBeFreed() const;

mask_t mask() const;

initializeToPreoptCacheInDisguise

void incrementOccupied();

Insert cache insert(SEL SEL, IMP IMP, ID receiver)

Related Posts

Write an XCode Source Extension from scratch

Ios-underlying principle 16: Dyld is associated with objC

Swift Progression: A summary of usage scenarios for traits/mixins/ protocol extensions