This chapter content

  1. Class cache structure, along with important members and methods
  2. The structure of bucket_t
  3. LLDB Indicates the method for verifying the cache
  4. Source code analysis insert method

The third member cache of the class

The nature and structure of the class are clear. Classes are essentially Pointers to objc_class * structs. And the members from top to bottom are:

  1. Class ISA, the ISA of a Class refers to its metaclass
  2. Class superClass, Class superClass
  3. Cache_t cache, the cache of the class. The cache is the method of execution
  4. Class_data_bits_t bits, where methods, protocols, attributes, member variables, etc. of a class are stored.

The structure of the cache

The name cache means cache, and the existence of cache also has a great connection with objc_msgSend, we can think of OC sending messages, forwarding messages, if it wants to improve the efficiency of sending and forwarding messages, it must have a cache, because there is a cache to send messages quickly, It will increase the rate of forwarding. So it is also necessary to study the class cache. The importance of buckets can be seen from their members and methods. What is buckets

Important members

Supplement: 3/4 = 0.75, which represents the load factor, because 0.75 is found to be the highest memory utilization in the whole algorithm and may lead to hash conflicts during capacity expansion, while 0.75 can effectively reduce hash conflicts

  1. Bucketsandmaybemask: represents Buckets and maybeMask. It does what ISA does for objects: store more information with less content.

  2. Union: You can see that __LP64__ represents running on systems like MAC OS X, so we just look at the structure

    1. The {_maybeMask structure represents the size of the container. It's occupied on a 3/4 basis, so it's occupied on a 3/4 basis; _occupied/_maybeMask on a 3/4 basis; _occupied represents the number of cache methodsCopy the code

Important method

From the top down, insert is the most important, because if we want to read a cached method, we need the method to be in the cache first, which means we need to insert first and then objc_msgSend.

  1. Mask_t mask() const, gets the value of maybeMask, which is the size of the container.

  2. Void incrementOccupied() – Improves occupied size by +1 each time.

  3. Void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask), store newBuckets in _bucketsAndMaybeMask, Store the new mask(container) in _maybeMask.

  4. Void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld), create a new bucket with newCapacity, and call method 3 to store the buckets. See if you need to release the old buckets according to freeOld. It actually calls method 7 internally

  5. Void collect_free(bucket_t * oldCapacity, mask_t oldCapacity)

  6. Static bucket_t *emptyBuckets() to clear the pointer

  7. Static BUCket_t *allocateBuckets(mask_t newCapacity) to create buckets

  8. Static BUCket_t *emptyBucketsForCapacity(mask_t capacity, bool allocate = true); static BUCket_t *emptyBucketsForCapacity(MASk_t capacity, bool allocate = true) If allocate is false, then nil is returned. If allocate is false, then nil is returned. It’s not particularly accurate, you can see the source code

—– Above 1-8 are private methods, 9 starts with a total of —-

  1. Struct bucket_t *buckets() const

  2. Mask_t occupied() const, gets _occupied, the number of methods in the cache

  3. Void insert(SEL SEL, IMP IMP, ID receiver) void insert(SEL SEL, IMP IMP, ID receiver)

Bucket_t structure

We already know the importance of buckets based on cache, but what are buckets? Bucket_t * is a pointer to a struct. it just points to an address in memory, but we’re not sure what it means. For example, void star is just a pointer to a memory address. But what we’re pulling out is a string of hexadecimal data. The reason why we always use Class without the asterisk to point to it is because Class is essentially just objc_class *. The bucket_t * in this article actually represents a hash list structure, which is unordered.

LLDB explores the methods of caching

Without Posting the source code here, just know that a class Person has an instance method called testMethod. And then we just need the break point Person *p = [Person alloc] on the next line. Note that this LLDB is being debugged in a source code project.

If we need to debug in a non-source environment, we can write the structure in our project, now that we know its memory distribution, we can directly cast it, and then we can print out its cache method

1. First look at the cache structure without calling methods

2. Then LLDB calls the method for viewing

And it turns out that the _maybeMask is 7 and the _occupied is 1, so that proves that the occupied method changes after we call it. Please look at the notes

Note: If the source code calls the method, the _occupied is 1 and the _maybeMask is 3. This is because when we call a method using LLDB, the system automatically calls three methods (), so _maybeMask is 7.

  1. No source call method results

  1. The result of the source call method

3. Check what methods are cached in cache

You can see that it actually caches the method at the fifth shift. It’s what I said in bucket_t that the hash list structure is unordered. In fact, the way it’s stored is based on the hash function, which is traceable

An inquiry into insert methods

Why do we do this?

  1. From this method we can get the number of cache methods stored _ocuupied
  2. We can find out when and how the method’s container size _maybeMask was expanded
  3. So every time we cache the method it will remove the old method at the 3/4 critical point, and then the new method will be inserted. (The reason for removing the old method is because Apple thinks the old method is less important when the new method comes in, and the newer the better)
  4. Objc_msgSend looks up faster only after the method is inserted into the cache

The source code

The key point is: container buckets storage, hash function to calculate the insertion position of the method,

Void cache_t::insert(SEL SEL, IMP IMP, ID receiver) {// Runtime add lock 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. // Use the cache as-is if until we exceed our expected fill ratio. X +1 mask_t newOccupied = occupied() +1; Unsigned oldCapacity = capacity(), capacity = oldCapacity; // Unsigned oldCapacity = capacity(), capacity = oldCapacity; If (slowPath (isConstantEmptyCache())) {// Cache is read-only. Replace it. Capacity = 4 if (! capacity) capacity = INIT_CACHE_SIZE; Reallocate (oldCapacity, capacity, /* freeOld */false) reallocate(oldCapacity, capacity, /* freeOld */false); } // When the number of methods cached is less than 3/4 of the number of containers opened. else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) { // Cache is less than 3/4 or 7/8 #if CACHE_ALLOW_FULL_UTILIZATION // If capacity<=8 && NewOccupied + (0 in some architectures and 1 in some) <= capacity 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 {// If capacity is 0, then the value is 4. Why is the final result 3? Capacity = capacity? capacity * 2 : INIT_CACHE_SIZE; If (capacity > MAX_CACHE_SIZE) {capacity = MAX_CACHE_SIZE; if (capacity > MAX_CACHE_SIZE) {capacity = MAX_CACHE_SIZE; } reallocate(oldCapacity, capacity, true);} Reallocate (oldCapacity, capacity, true); } // buckets(array of cache methods) 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 the method to be inserted is not in the cache if (fastpath(b[i].sel() == 0)) { // occupied + 1 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

Added the reallocate method

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, Bool freeOld) {// Get the old container bucket_t *oldBuckets = buckets(); // Create a new container with size newCapacity 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); // Store the buckets and maybeMask of the container, namely _bucketsAndMaybeMask and _maybeMask. SetBucketsAndMask (newBuckets, newCapacity - 1); If (freeOld) {collect_free(oldCapacity, oldCapacity); }}Copy the code

supplement

The reason why maybeMask is 7 when LLDB calls a method is that LLDB calls three system methods by default

  1. NSObject’s response to Selector method
  2. Class method of NSObject
  3. _objc_msgForward method