preface

Now that we have seen the contents of the objc_class structure and analyzed the capabilities of ISA and superclass, let’s take a look at the objc_class structure to start our cache exploration.

struct objc_class : objc_object {
    // Class ISA;
    // Class _Nonnull isa  OBJC_ISA_AVAILABILITY;
    Class superclass;
    cache_t cache;             // formerly cache pointer and vtable
    class_data_bits_t bits;  
}
Copy the code

Find the cache address

We can print the first address of the cache by p/x. We know that each pointer is 8 bytes, so isa and superclass are 8 bytes each, so we can find the first address of the cache by 16 bytes.

Cache_t structure source code

struct cache_t { private: explicit_atomic<uintptr_t> _bucketsAndMaybeMask; Struct {explicit_atomic<mask_t> _maybeMask; struct {explicit_atomic<mask_t> _maybeMask; #if __LP64__ uint16_t _flags; // Occupy 2 bytes #endif uint16_t _occupied; // 2 bytes}; explicit_atomic<preopt_cache_t *> _originalPreoptCache; // Pointer takes 8 bytes}; / / omit... Void incrementOccupied(); // occupied++ is called when bucket is inserted. Cache_t void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask); // buckets struct bucket_t *buckets() const; // Number of stored elements mask_t occupied() const; // Insert bucket void insert(SEL SEL, IMP IMP, ID receiver) into the cache; }Copy the code

_bucketsAndMaybeMask stores buckets and mask information in the setBucketsAndMask() method

Buckets: Like an array, memory is contiguous, storing cached methods

Mask: mask for method lookup and insertion

Occupied: Keeps track of the number of cached methods and calls incrementOccupied() +1 each time a new method is inserted

Insert method analysis

Take a look at the insert method source code

Void cache_t::insert(SEL SEL, IMP IMP, id receiver) {// 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) needs to release old storage information after capacity expansion. } bucket_t *b = buckets(); mask_t m = capacity - 1; mask_t begin = cache_hash(sel, m); mask_t i = begin; 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)); // Mask operation index bad_cache(receiver, (SEL) SEL); #endif // ! DEBUG_TASK_THREADS }Copy the code

Initialize create cache_t

if (! capacity) capacity = INIT_CACHE_SIZE; reallocate(oldCapacity, capacity, /* freeOld */false);Copy the code

Initializing capacity

Initialize capacity to 4 (1 << 2)

INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2) = 1 << 2

INIT_CACHE_SIZE_LOG2 = 2

The realLocate function is initialized

Reallocate implementation

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld) { bucket_t *oldBuckets = buckets(); bucket_t *newBuckets = allocateBuckets(newCapacity); setBucketsAndMask(newBuckets, newCapacity - 1); if (freeOld) { collect_free(oldBuckets, oldCapacity); }}Copy the code
  1. First get the old buckets;
  2. Create a new capacity buckets;
  3. Call setBucketsAndMask to associate buckets with mask.The value of mask is the capacity value -1
  4. Determine whether to release the old cache. The old cache needs to be released during capacity expansion
  5. Release the old cache

Capacity expansion with Collect_free frees old caches

Capacity to judge

Run the fastPATH (newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity) command to determine whether capacity expansion is required

NewOccupied: Cache number;

CACHE_END_MARKER: 1;

Cache_fill_ratio (capacity) : Capacity * 3/4;

That is, when the number of elements in the cache is three quarters of its capacity, the cache is expanded.

capacity

capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;

You can see that the capacity will be expanded to twice the original capacity.

Collect_free implementation

void cache_t::collect_free(bucket_t *data, mask_t capacity)
{
    _garbage_make_room ();
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    garbage_refs[garbage_count++] = data;
    cache_t::collectNolock(false);
}
Copy the code

Why does capacity expansion release old cache information

Cache_hash (sel, m) is used to store hash tables. If the capacity of the hash key and mask is calculated by decreasing 1, the capacity has changed and the value of mask has changed. Therefore, you need to clear all caches and re-cache methods.

Hash stores Key calculations

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)); // Index of the mask operationCopy the code
  1. To get buckets

bucket_t *b = buckets();

  1. The mask is calculated from the cache capacity

mask_t m = capacity - 1;

  1. Get the hash value of the method by sel and mask

mask_t begin = cache_hash(sel, m);

mask_t i = begin;

  1. Obtain the key using the hash value and mask

i = cache_next(i, m)

In essence, cache_next increments the hash value by 1 and then re-masks it until the condition is met and the loop ends

  1. fastpath(b[i].sel() == 0

Check whether the key value corresponding to buckets is empty. If so, insert the method to the corresponding position to end the loop. Otherwise, add hash value 1 to continue the mask operation

Code to view

Find the initial cache information first

Look at the cache information after calling the test method

To view cached method information, call SEL with bucket_t

inline SEL sel() const { return_sel.load(memory_order_relaxed); }

Call IMP with bucket_t to see the function pointer

inline IMP imp (UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls)