Cache data structure

1. Analyze cache through source code

We have seen the structure of classes and analyzed bits in the article “The underlying structure of OC Low-level Exploration and so on.”

Now let’s analyze the cache, which is literally a cache!

Is stillObjc source,The breakpoint, by memory translation0x10,cache:

_maybeMask = 0; _occupied = 0; _occupied = 0;

struct cache_t { private: explicit_atomic<uintptr_t> _bucketsAndMaybeMask; union { struct { explicit_atomic<mask_t> _maybeMask; #if __LP64__ uint16_t _flags; #endif uint16_t _occupied; }; explicit_atomic<preopt_cache_t *> _originalPreoptCache; }; // omit methods, global variables, etc., methods in the method area, global variables in the global area do not occupy structure storage}Copy the code

__LP64__ refers to Unix and UniX-like systems (Linux, Mac OS X, etc.).

But with so many member variables in cache_t, which one is actually the cache?

Caching is nothing more than adding, deleting, modifying, and searching methods for related methods!

We’ve found the insert method in the cache_t structure, which is clearly the insert method:

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

Insert ();

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

B [I] = set; b[I] = set;

bucket_t *b = buckets();
Copy the code

Enter the bucket_t 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; #endif // omit method etc}Copy the code

Bucket_t has IMP and SEL member variables.

SEL: pointer to a class member method, but different from the function pointer in C, the function pointer directly stores the address of the method, but SEL is only the method number.

IMP: a function pointer that holds the address of the method

Which member variable is bucket_t going to be in?

Obviously in _bucketsAndMaybeMask!

2. Graph summary

Then we can get a graph like this:

2. Cache underlying LLDB analysis

Next we print _bucketsAndMaybeMask:

(lldb) p $2._bucketsAndMaybeMask (explicit_atomic<unsigned long>) $3 = { std::__1::atomic<unsigned long> = { Value = 4436931456}}Copy the code

Find a Value inside, continue printing Value:

(lldb) p $3.Value
error: <user expression 4>:1:4: no member named 'Value' in 'explicit_atomic<unsigned long>'
$3.Value
~~ ^
Copy the code

What if I can’t get the data?

Find way!

Inside the cache_t structure you’ll find:

struct bucket_t *buckets() const;
Copy the code

Then call buckets() :

(lldb) p $2.buckets() (bucket_t *) $4 = 0x0000000108763380 (lldb) p *$4 (bucket_t) $5 = { _sel = { std::__1::atomic<objc_selector *> = (null) { Value = (null) } } _imp = { std::__1::atomic<unsigned long> = { Value = 0 } }}Copy the code

This prints out our _sel and _IMP!

But no value!

There is no cache because the object has no method to use!

Use methods before you get them:

We have values this time, and _maybeMask in cache_t has a value of 3 and _occupied has a value of 1, which is similar to the number of methods we have, but SEL and the name of the method we got are different!

Now go to bucket_t and find the corresponding method:

inline SEL sel() const { return _sel.load(memory_order_relaxed); } inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const { uintptr_t imp = _imp.load(memory_order_relaxed); if (! imp) return nil; #if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH SEL sel = _sel.load(memory_order_relaxed); return (IMP) ptrauth_auth_and_resign((const void *)imp, ptrauth_key_process_dependent_code, modifierForSEL(base, sel, cls), ptrauth_key_function_pointer, 0); #elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR return (IMP)(imp ^ (uintptr_t)cls); #elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE return (IMP)imp; #else #error Unknown method cache IMP encoding. #endif }Copy the code

SEL and IMP can be found the corresponding access method!

Continue printing:

(lldb) p $4.sel()
(SEL) $5 = "printName"
Copy the code

Imp: bucket_t: bucket_t: bucket_t: bucket_t: bucket_t

Pass nil to try:

(lldb) p $4.imp(nil, pClass)
(IMP) $6 = 0x0000000100003d70 (HObjectBuild`-[HPerson printName])
Copy the code

We successfully printed the method we used printName!

Break away from the source code analysis cache

1, custom source code structure

What if there is no source code? How do we debug?

You just need to define the relevant structure!

To start a new project, define the objc_class structure and rename it:

struct h_objc_class {
   	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 code

Cache_t and class_datA_bits_t could not be found. Proceed with customizing the cache_t structure:

struct h_cache_t { explicit_atomic<uintptr_t> _bucketsAndMaybeMask; union { struct { explicit_atomic<mask_t> _maybeMask; #if __LP64__ uint16_t _flags; #endif uint16_t _occupied; }; explicit_atomic<preopt_cache_t *> _originalPreoptCache; }; };Copy the code

Then it turns out that explicit_atomic is unknown, so we just delete it.

Mask_t also do not know, go to source view:

#if __LP64__
typedef uint32_t mask_t;  // x86_64 & arm64 asm are less efficient with 16-bits
#else
typedef uint16_t mask_t;
#endif
Copy the code

So just bring mask_T too!

Delete _originalPreoptCache and remove the structure: originalPreoptCache

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

struct h_cache_t {
    uintptr_t _bucketsAndMaybeMask;
    
    mask_t    _maybeMask;
#if __LP64__
    uint16_t  _flags;
#endif
    uint16_t  _occupied;
};
Copy the code

Class_data_bits_t:

struct h_class_data_bits_t {
    friend objc_class;

    // Values are the FAST_ flags above.
    uintptr_t bits;
};
Copy the code

Then the friend class is not needed:

struct h_class_data_bits_t {
    // Values are the FAST_ flags above.
    uintptr_t bits;
};
Copy the code

Finally, adjust the h_objc_class structure:

struct h_objc_class {
   	Class isa;
    Class superclass;
    struct h_cache_t cache;             // formerly cache pointer and vtable
    struct h_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};
Copy the code

This completes our custom objc_class structure!

Finally, we need the bucket_t structure, as we did above:

struct h_bucket_t {
    // 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__
    uintptr_t _imp;
    SEL _sel;
#else
    SEL _sel;
    uintptr_t _imp;
#endif
};
Copy the code

Uintptr_t = uintPTR_t

struct h_bucket_t {
    // 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__
    IMP _imp;
    SEL _sel;
#else
    SEL _sel;
    IMP _imp;
#endif
};
Copy the code

So the structure of the custom source code is basically complete!

2, debugging,

To force a class into a custom h_objc_class structure:

struct h_objc_class * pClass = (__bridge struct h_objc_class *)(p.class);
Copy the code

Print the values of the member variables that we felt were similar to the number of methods:

Print 1 and 3, same as before with LLDB!

Next, I need to find bucket_t in _bucketsAndMaybeMask!

Let’s look at buckets() method:

struct bucket_t *cache_t::buckets() const
{
    uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return (bucket_t *)(addr & bucketsMask);
}
Copy the code

Addr = _bucketsAndMaybeMask = _bucketsAndMaybeMask

Bucketsandmaybemask = bucketsMask; bucketsMask = bucket_t;

So we can simply replace _bucketsAndMaybeMask with the pointer to the bucket_t structure:

struct h_cache_t {
    struct h_bucket_t * _buckets;
    
    mask_t    _maybeMask;
#if __LP64__
    uint16_t  _flags;
#endif
    uint16_t  _occupied;
};
Copy the code

So you don’t need buckets() anymore! You can skip a lot of tedious steps!

Then get the bucket_t structure:

Successfully printed out the method we used!

But what if you have multiple method caches? How do I get it?

The buckets() method obviously returns multiple buckets! But the source code returns Pointers, so can we use pointer offsets to get other buckets?

Assuming _occupied in cache_t stores the number of methods, the for loop prints:

It turns out that the method we used is not completely printed!

Let’s try _maybeMask:

This time we successfully printed out all the methods we used!

3, summarize

This completely out of the source code, and successful debugging, and do not need LLDB debugging, easy to modify, simple and clear!

If you can’t debug the downloaded source code for some reason, try this method!

And when you need a small sample, you can also try this method!

Analysis of the underlying principle of cache

1, problem,

Just now we only called two methods, but we printed an empty method to print it out completely!

So if we have3A solution?

First, you’ll notice that “Occupied” has changed to 1, “maybeMask” to 7, and only the last method is printed! And lots of null!

If you haveClass method?

It seems that the class method is not in the cache!

If it’s calledinitMethod?

It turns out that init is in cache, but we didn’t override init. Why is that?

2. Low-level analysis

① Organize your thoughts

Start with _bucketsAndMaybeMask!

explicit_atomic<uintptr_t> _bucketsAndMaybeMask;
Copy the code

Obviously _bucketsAndMaybeMask stores Buckets and MaybeMask.

But its value is only 1, how is it stored?

From buckets() we can infer that _bucketsAndMaybeMask is just like ISA in that it also stores information on the bucket! Fetch information on the & operation!

So how do you test that?

Find the entry point first! A cache is a cache.

So start exploring by writing!

② Look at the overall situation

Reexplore the insert method in the cache_t structure:

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

Insert (SEL), IMP (address), IMP (receiver)

Enter the INSERT overview:

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; unsigned oldCapacity = capacity(), capacity = oldCapacity; if (slowpath(isConstantEmptyCache())) { // 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); } 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

③ First execution

1. Look at two assignments:

// Use the cache as-is if until we exceed our expected fill ratio.
    mask_t newOccupied = occupied() + 1;
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
Copy the code

We create newOccupied, the number of caches used, and look at the occupied() method:

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

Occupied!

Let’s look at the capacity() method:

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

Where oldCapacity and capacity are both the value of _maybeMask + 1 or 0!

2, look at the judgment logic:

If it is the first time to cache, enter the empty cache judgment:

if (slowpath(isConstantEmptyCache())) { // Cache is read-only. Replace it. if (! capacity) capacity = INIT_CACHE_SIZE; reallocate(oldCapacity, capacity, /* freeOld */false); }Copy the code

Slowpath: most likely will not be executed

Fastpath: It is most likely to be executed

Capacity is assigned to INIT_CACHE_SIZE and INIT_CACHE_SIZE is entered:

/* Initial cache bucket count. INIT_CACHE_SIZE must be a power of two. */ enum { #if CACHE_END_MARKER || (__arm64__ && ! __LP64__) // When we have a cache end marker it fills a bucket slot, so having a // initial cache size of 2 buckets would not be efficient when one of the // slots is always filled with the  end marker. So start with a cache size // 4 buckets. INIT_CACHE_SIZE_LOG2 = 2, #else // Allow an initial bucket size of 2 buckets, since a large number of // classes, especially metaclasses, have very few imps, and we support // the ability to fill 100% of the cache before resizing. INIT_CACHE_SIZE_LOG2 = 1, #endif INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2), MAX_CACHE_SIZE_LOG2 = 16, MAX_CACHE_SIZE = (1 << MAX_CACHE_SIZE_LOG2), FULL_UTILIZATION_CACHE_SIZE_LOG2 = 3, FULL_UTILIZATION_CACHE_SIZE = (1 << FULL_UTILIZATION_CACHE_SIZE_LOG2), };Copy the code

INIT_CACHE_SIZE = 1; capacity = 4;

Looking at the RealLocate method:

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);

    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        collect_free(oldBuckets, oldCapacity);
    }
}
Copy the code

Get the old buckets, create the new buckets, and set the BucketsAndMask!

AllocateBuckets method:

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);

    return newBuckets;
}
Copy the code

Here is the calloc method, that is, open up memory, look at bytesForCapacity method:

size_t cache_t::bytesForCapacity(uint32_t cap)
{
    return sizeof(bucket_t) * cap;
}
Copy the code

Because newCapacity is 4, bucket_t contains SEL and IMP, so 4 * 16 = 64 bytes of memory!

While looking at end, the endMarker method is called:

bucket_t *cache_t::endMarker(struct bucket_t *b, uint32_t cap)
{
    return (bucket_t *)((uintptr_t)b + bytesForCapacity(cap)) - 1;
}
Copy the code

Here is the memory address of the last 16 bytes opened by memory translation!

Insert a 1 at end and the starting address of the new Buckets!

Enter the setBucketsAndMask method:

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.store((uintptr_t)newBuckets, memory_order_release); // ensure other threads see new buckets before new mask _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 translates newBuckets into a pointer address and then _maybeMask translates newMask into newcapacity-1. NewCapacity is 4, so _maybeMask is 3.

This is why _maybeMask is 3 when there is only 1 caching method!

At the same time, there is no method in newBuckets, so _dip is 0!

3. Insert Buckets:

bucket_t *b = buckets(); Mask_t m = capacity - 1; //4 - 1 = 3 mask_t begin = cache_hash(sel, m); Mask_t I = begin; //---- here is the cache_hash method ---- // Class points to cache.sel is key. Cache buckets store SEL+IMP. // Caches are never built in the dyld shared cache. 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); }Copy the code

Then find the vacancy to insert:

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

Go to do and look at the first if, which is to take sel from the bucket_t that you just created, and check if sel has a value, because most of the cases that you just created have no value! Enter the first if!

IncrementOccupied ()

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

She’s occupied with final exams. So make sure _occupied is the number of method caches!

Then we call bucket_t’s set method and pass in b, SEL, IMP, CLS:

template<Atomicity atomicity, IMPEncoding impEncoding>
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) {
        _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);
        _sel.store(newSel, memory_order_relaxed);
    }
}
Copy the code

First, create newIMP and determine if you need to code!

If no encoding is used, the IMP that is passed in is assigned directly.

EncodeImp if required:

// Sign newImp, with &_imp, newSel, and cls as modifiers. uintptr_t encodeImp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, IMP newImp, UNUSED_WITHOUT_PTRAUTH SEL newSel, Class cls) const { if (! newImp) return 0; #if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH return (uintptr_t) ptrauth_auth_and_resign(newImp, ptrauth_key_function_pointer, 0, ptrauth_key_process_dependent_code, modifierForSEL(base, newSel, cls)); #elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR return (uintptr_t)newImp ^ (uintptr_t)cls; #elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE return (uintptr_t)newImp; #else #error Unknown method cache IMP encoding. #endif }Copy the code

The essence of coding is to xor imp and class!

Determine if atomic operation after coding is complete!

If yes, determine whether the current IMP and the new IMP, not the same before storage!

Not directly stored!

The second if is to determine if the sel in bucket_t is the same as the current sel.

Enter the while!

Let’s start with the cache_next method:

#if CACHE_END_MARKER
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
#elif __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}
#else
#error unexpected configuration
#endif
Copy the code

The hash address is still computed! Find a space before you execute the do statement!

④ Execute again

Back to the judgment at the beginning:

// Use the cache as-is if until we exceed our expected fill ratio. mask_t newOccupied = occupied() + 1; unsigned oldCapacity = capacity(), capacity = oldCapacity; if (slowpath(isConstantEmptyCache())) { // 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 following cache_fill_ratio method ---- // Historical fill ratio of 75% (since the new objc Runtime was introduced). Static inline mask_t cache_fill_ratio(mask_t capacity) { return capacity * 3 / 4; }Copy the code

On the second run, newOccupied is _occupied + 1 = 2, and capacity is _maybeMask + 1 = 4.

newOccupied + CACHE_END_MARKER = 2 + 1 = 3;
cache_fill_ratio(capacity) = cache_fill_ratio(4) = 3;
Copy the code

Go to the second if and go straight to the code!

So the second time, just insert a new method into bucket_t as you did the first time!

⑤ Execute the third time

For the third time, newOccupied is _occupied + 1 = 3, and capacity is _maybeMask + 1 = 4.

newOccupied + CACHE_END_MARKER = 3 + 1 = 4;
cache_fill_ratio(capacity) = cache_fill_ratio(4) = 3;
Copy the code

In the normal case, go to the last else and execute the RealLocate method!

capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; //2 * 4 = 8 if (capacity > MAX_CACHE_SIZE) { capacity = MAX_CACHE_SIZE; } reallocate(oldCapacity, capacity, true);Copy the code

Inside the RealLocate method, create a new bucket_t! Release the old bucket_t because the argument is passed true:

/*********************************************************************** * cache_t::collect_free. Add the specified malloc'd memory to the list * of them to free at some later point. * size is used for the collection threshold. It does not have to be * precisely the block's size. * Cache locks: cacheUpdateLock must be held by the caller. **********************************************************************/ 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); }Copy the code

Here called the system garbage stack method to continue to free memory!

And the setBucketsAndMask method assigns _occupied to 0 and _maybeMask to 7!

So when we execute the three methods, _occupied is 1 and _maybeMask is 7.

Because old methods are released, only new methods are saved! So there’s a lot of null!

Why free up the old method and not move it to the new memory space? Because open memory is not in the original memory location expansion, but to open up new memory space! Moving an old method to a new memory space can be a performance drain, so releasing it is the most efficient!

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.

Cache_t analysis like OC low-level exploration

Cache data structure

1. Analyze cache through source code

2. Graph summary

2. Cache underlying LLDB analysis

Break away from the source code analysis cache

1, custom source code structure

2, debugging,

3, summarize

Analysis of the underlying principle of cache

1, problem,

2. Low-level analysis

① Organize your thoughts

② Look at the overall situation

③ First execution

④ Execute again

⑤ Execute the third time

Five, figure combing

Cache_t analysis like OC low-level exploration

Cache data structure

1. Analyze cache through source code

2. Graph summary

2. Cache underlying LLDB analysis

Break away from the source code analysis cache

1, custom source code structure

2, debugging,

3, summarize

Analysis of the underlying principle of cache

1, problem,

2. Low-level analysis

① Organize your thoughts

② Look at the overall situation

③ First execution

④ Execute again

⑤ Execute the third time

Five, figure combing

Related Posts

ResponderChain+Strategy+MVVM to implement an elegant TableView

Day 4: Rediscover sound

Full review | five trill engineer reveal trill iOS based technology (attached PPT and playback video)