IOS Low-level learning - Cache_T analysis of classes

This is the 6th day of my participation in the August More Text Challenge

In the chapter of class principle analysis, we have learned about the structure of class and analyzed the bits structure, and also mentioned cache. Today, let’s take a closer look at cache

Cache data structure

cacheThat’s the cache, the cache of the class. How do you cache it? Take a look at it with the questioncache_tData structure ofthroughlldbBreakpoint debugging, first address translation16 bytesnamely0x10You can getcacht_t Discovery and source codecache_tIs structurally consistent. So what are the member variables in the structurecache_tWhat’s the point?

First of all, we know that the operation on cache is add, delete, change, check. See if there are any other key methods or operations in the cache_t structure. The INSERT method is found in the public: method of cache_t.

void insert(SEL sel, IMP imp, id receiver);
Copy the code

insertAs the name impliesinsert, then enterinsertmethods insertIn the method, yesbucketOperation, continue to enterbucket_t bucket_tThere are some familiar onesIMPandSEL, the obvious caching method inbucket_tIn the

Finally, the following structure diagram is obtained:

LLDB analyzes the cache bottom layer

It was analyzed abovecacheAnd finally find the cachebucket_tMedium, then pass nowlldbDebug and verifyFirst getcache_tIn the_bucketsAndMaybeMaskIn the access to_bucketsAndMaybeMaskIn theValueWhen can not get. And then we hadcache_tFind the following method in the structure

struct bucket_t *buckets() const;
Copy the code

To obtaincache_tIn thebuckets()Find what we want_seland_imp. But none of these values are herenullis0It just has no value. Because the current method has not executed so no cache, modify the code to call the method after debuggingThe results ofbucketsIt still doesn’t have a value, butmaskandoccupiedThere is a change in, indicating that there should be cache. whybucketsOr not?

You can see the definition abovebucketsIs a structure pointer that prints directlybuckets()Get the first address, need to usebuckets()[index]Address offset obtain otherbucket And then finally I find something that has value at subscript 2bucketThrough thebucket_ttheselMethod prints the name of the method that was just called.

Analysis of the underlying principle of cache

We know that cache has to be written in before it can be read. We’ve just seen an insert method. So let’s start with this method

void insert(SEL sel, IMP imp, id receiver);
Copy the code

The arguments passed to the INSERT method are SEL, IMP, and receiver, respectively. Source code analysis:

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    ...
    
    // Use the cache as-is if until we exceed our expected fill ratio.
    mask_t newOccupied = occupied() + 1;// Prepare for the first time; newOccupied = 1
    unsigned oldCapacity = capacity(), capacity = oldCapacity;// _maybeMask + 1, the first input is 0
    if (slowpath(isConstantEmptyCache())) { // Empty cache, first entry
        // Cache is read-only. Replace it.
        if(! capacity) capacity = INIT_CACHE_SIZE;// The default value is 4
        reallocate(oldCapacity, capacity, /* freeOld */false);// Create capacity
    }
    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 the cache capacity is less than or equal to 3/4 or 7/8 of capacity (different architectures), do nothing and continue
    }
#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.
        // If capacity <= 8 and newOccupied + 1/0 <= capacity, 100% of the cache is allowed
    }
#endif
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;// The value of capacity is doubled. Otherwise, the value is 4
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);// Create new memory and free up old space
    }

    bucket_t *b = buckets();// Get buckets() first address
    mask_t m = capacity - 1;// mask = capacity - 1
    mask_t begin = cache_hash(sel, m);// Get the hash subscript
    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)) { / / the bucket is empty
            incrementOccupied(); // Occupied + 1
            b[i].set<Atomic, Encoded>(b, sel, imp, cls()); // Put SEL and IMP into bucket
            return;
        }
        if (b[i].sel() == sel) { // Bucket already exists and will not be processed
            // 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));// Prevent hash collisions. Hash again. Does not equal the subscript begin. }Copy the code

We created newOccupied first. Occupied; occupied; occupied; occupied; occupied; occupied; occupied; occupied; occupied

mask_t cache_t::occupied() const
{
    return _occupied;
}
Copy the code

OldCapacity and capacity are _maybeMask + 1 or 0:

unsigned cache_t::capacity() const
{
    return mask() ? mask()+1 : 0; 
}

mask_t cache_t::mask() const
{
    return _maybeMask.load(memory_order_relaxed);
}
Copy the code

reallocateMethods:

ALWAYS_INLINE
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = buckets();/ / get oldBuckets
    bucket_t *newBuckets = allocateBuckets(newCapacity);// Get newBuckets

    // 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 to newBuckets and Mask to newcapacity-1
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        // Free the old memory, i.e. clear the previous cachecollect_free(oldBuckets, oldCapacity); }}Copy the code

allocateBucketsOpen up memory
setBucketsAndMaskSet up thebucketsandmask
collect_freeDetermine whether to release old memory (during capacity expansion)

allocateBucketsMethods:

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);// Set up a new bucket

    bucket_t *end = endMarker(newBuckets, newCapacity);// Take the last one from your new buckets

#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.
    // sel = 1, imp= the first address of the newBuckets
    end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity);

    return newBuckets;
}
Copy the code

callocCreate a memory
end->setStore the last location of open memorysel = 1.imp = The address of the first buket location

setBucketsAndMaskMethods:

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, then buckets.

#ifdef __arm__
    // ensure other threads see buckets contents before buckets pointer
    mega_barrier();

    _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
    // ensure other threads see buckets contents before buckets pointer
    // _bucketsAndMaybeMask stores newBuckets as an address pointer
    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_release);

    // ensure other threads see new buckets before new mask
    // _maybeMask is saved to newMask
    _maybeMask.store(newMask, memory_order_release);
    _occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}
Copy the code

_bucketsAndMaybeMask.store()Store data to _bucketsAndMaybeMask
_maybeMask.store()Store data to _maybeMask

Cache_t Flowchart

The overall flow of cache_T (borrow from kc teacher 😁)

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

IOS Low-level learning – Cache_T analysis of classes

Cache data structure

LLDB analyzes the cache bottom layer

Analysis of the underlying principle of cache

Cache_t Flowchart

IOS Low-level learning – Cache_T analysis of classes

Cache data structure

LLDB analyzes the cache bottom layer

Analysis of the underlying principle of cache

Cache_t Flowchart

Related Posts

Swift- Advanced 03: Value type & reference type

RxSwift learning – Operator of an Observable

IOS fundamentals – Memory management theory