Environment: Xcode 11.5

Source: objc4-781

The last article explored the structure of the class, as follows:

struct objc_class : objc_object {
    // 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

Where ISA ISA pointer to objc_class, superclass refers to the superclass, and bits stores some basic information about the current class. Today we’ll continue exploring the last variable in the objc_class structure, cache_t.

Cache_t profile

First, let’s look at the structure of Cache_t:

struct cache_t { #if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED explicit_atomic<struct bucket_t *> _buckets; Explicit_atomic <mask_t> _mask; #elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 explicit_atomic<uintptr_t> _maskAndBuckets; mask_t _mask_unused; Static Constexpr Uintptr_t Uintkshift = 12; static constexpr uintptr_t maskZeroBits = 4; static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1; static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1; . #endif #if __LP64__ uint16_t _flags; #endif uint16_t _occupied; // The number of methods in the cache}Copy the code

There are some differences between the ARM and x86 architectures. The specific difference lies in that the Pointers of Mask and buckets are stored in one Uintptr_t data in THE ARM architecture and stored separately in the x86 architecture. At the same time, the ARM architecture also defines some masks and other data for data reading, that is, some constants in the above code.

Bucket_t has the following 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; #endifCopy the code

Bucket_t has two properties, key for the method identifier and _IMP for the method implementation.

Cache_t explore

Let’s explore this directly using LLDB.

@interface ZHYObject : NSObject

- (void)method1;
- (void)method2;
- (void)method3;

@end
Copy the code

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        ZHYObject *object = [[ZHYObject alloc] init];
        [object method1];
        [object method2];
        [object method3];
        NSLog(@"%@",object);
    }
    return 0;
}
Copy the code

The breakpoint is made and printed before the instance method is called

(lldb) x/4gx pClass
0x1000023d0: 0x00000001000023a8 0x00000001003ef140
0x1000023e0: 0x00000001003e9450 0x0000801000000000
(lldb) p (cache_t*)0x1000023e0
(cache_t *) $1 = 0x00000001000023e0
(lldb) p *$1
(cache_t) $2 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x00000001003e9450 {
      _sel = {
        std::__1::atomic<objc_selector *> = 0x0000000000000000
      }
      _imp = {
        std::__1::atomic<unsigned long> = 0
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 0
  }
  _flags = 32784
  _occupied = 0
}
Copy the code

Currently in cache_t, there is no method cache; occupied is 0. Then take a step at the break point. Reprint cache_t

(lldb) p *$1
(cache_t) $3 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x00000001006263e0 {
      _sel = {
        std::__1::atomic<objc_selector *> = 0x00007fff7482ec60
      }
      _imp = {
        std::__1::atomic<unsigned long> = 4046048
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 3
  }
  _flags = 32784
  _occupied = 1
}
(lldb) p $3.buckets()
(bucket_t *) $4 = 0x00000001006263e0
(lldb) p *($4)
(bucket_t) $5 = {
  _sel = {
    std::__1::atomic<objc_selector *> = 0x00007fff7482ec60
  }
  _imp = {
    std::__1::atomic<unsigned long> = 4046048
  }
}
(lldb) p $5.sel()
(SEL) $6 = "init"
(lldb) p *($4+1)
(bucket_t) $7 = {
  _sel = {
    std::__1::atomic<objc_selector *> = 0x0000000000000000
  }
  _imp = {
    std::__1::atomic<unsigned long> = 0
  }
}
Copy the code

The comparison shows that:

_bucketsMemory address changed by0x00000001003e9450Turned out to be0x00000001006263e0
_bucketsThere’s only one in the arraybucket_tTheta corresponds to thetainitmethods
_maskby0Turned out to be3
_occupiedby0Turned out to be1

Next step on the breakpoint and print

(lldb) p *$1 (cache_t) $8 = { _buckets = { std::__1::atomic<bucket_t *> = 0x00000001006263e0 { _sel = { std::__1::atomic<objc_selector *> = 0x00007fff7482ec60 } _imp = { std::__1::atomic<unsigned long> = 4046048 } } } _mask = { std::__1::atomic<unsigned int> = 3 } _flags = 32784 _occupied = 2 } (lldb) p *($4) (bucket_t) $9 = { _sel = { std::__1::atomic<objc_selector *> = 0x00007fff7482ec60 } _imp = { std::__1::atomic<unsigned long> = 4046048 } } (lldb) p  $9.sel() (SEL) $10 = "init" (lldb) p *($4+1) (bucket_t) $11 = { _sel = { std::__1::atomic<objc_selector *> = 0x0000000100000e15 } _imp = { std::__1::atomic<unsigned long> = 11904 } } (lldb) p $11.sel() (SEL) $12 = "method1"Copy the code

The comparison shows that:

_bucketsThe address hasn’t changed since the first time
_maskIt hasn’t changed
_occupiedTurned out to be2, consistent with the printed result,_bucketsThere are two methods in the array, alpha and beta_occupiedThe value of the same

The breakpoint continues to the next step and prints

(lldb) p *$1
(cache_t) $14 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x0000000101929660 {
      _sel = {
        std::__1::atomic<objc_selector *> = 0x0000000000000000
      }
      _imp = {
        std::__1::atomic<unsigned long> = 0
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 7
  }
  _flags = 32784
  _occupied = 1
}
(lldb) p $14.buckets()
(bucket_t *) $20 = 0x0000000101929660
(lldb) p *$20
(bucket_t) $21 = {
  _sel = {
    std::__1::atomic<objc_selector *> = 0x0000000000000000
  }
  _imp = {
    std::__1::atomic<unsigned long> = 0
  }
}
(lldb) p *($20+1)
(bucket_t) $22 = {
  _sel = {
    std::__1::atomic<objc_selector *> = 0x0000000000000000
  }
  _imp = {
    std::__1::atomic<unsigned long> = 0
  }
}
(lldb) p *($20+2)
(bucket_t) $23 = {
  _sel = {
    std::__1::atomic<objc_selector *> = 0x0000000000000000
  }
  _imp = {
    std::__1::atomic<unsigned long> = 0
  }
}
(lldb) p *($20+3)
(bucket_t) $24 = {
  _sel = {
    std::__1::atomic<objc_selector *> = 0x0000000000000000
  }
  _imp = {
    std::__1::atomic<unsigned long> = 0
  }
}
(lldb) p *($20+4)
(bucket_t) $25 = {
  _sel = {
    std::__1::atomic<objc_selector *> = 0x0000000000000000
  }
  _imp = {
    std::__1::atomic<unsigned long> = 0
  }
}
(lldb) p *($20+5)
(bucket_t) $26 = {
  _sel = {
    std::__1::atomic<objc_selector *> = 0x0000000100000e1d
  }
  _imp = {
    std::__1::atomic<unsigned long> = 11952
  }
}
(lldb) p $26.sel()
(SEL) $27 = "method2"
Copy the code

The comparison shows that:

_bucketsThe memory address has changed again
_maskby3Turned out to be7
_occupiedby3Turned out to be1
method2The method is not stored in the first void, we searched several times before we found it

Based on the above exploration, several questions arise:

_bucketsWhen will the memory address of the
_maskWhat is the meaning of “?
_occupiedWhy did it become1Instead of getting smaller?
_bucketsWhat are the rules for storing method locations in?

Cache_t underlying implementation

According to the LLDB exploration above, it can be found that every time _buckets changes, _mask will also change, and _mask will be 2 ^ n -1, and _occupied will change to 1. So let’s verify our findings with the relevant source code. Note the following lines in the objc_cache.mm comment:

 * Cache writers (hold cacheUpdateLock while reading or writing; not PC-checked)
 * cache_fill         (acquires lock)
 * cache_expand       (only called from cache_fill)
 * cache_create       (only called from cache_expand)
 * bcopy               (only called from instrumented cache_expand)
 * flush_caches        (acquires lock)
 * cache_flush        (only called from cache_fill and flush_caches)
 * cache_collect_free (only called from cache_expand and cache_flush)
Copy the code

We start tracing the source code from cache_fill

void cache_fill(Class cls, SEL sel, IMP imp, id receiver) { runtimeLock.assertLocked(); #if ! DEBUG_TASK_THREADS // Never cache before +initialize is done if (cls->isInitialized()) { cache_t *cache = getCache(cls);  #if CONFIG_USE_CACHE_LOCK mutex_locker_t lock(cacheUpdateLock); #endif cache->insert(cls, sel, imp, receiver); } #else _collecting_in_critical(); #endif }Copy the code

First check whether the class is initialized, then read the corresponding cache variable from the objC_class structure, and then perform insert.

insert

ALWAYS_INLINE void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver) { #if CONFIG_USE_CACHE_LOCK cacheUpdateLock.assertLocked(); #else runtimeLock.assertLocked(); #endif ASSERT(sel ! = 0 && cls->isInitialized()); // Use the cache as-is if it is less than 3/4 full mask_t newOccupied = occupied() + 1; unsigned oldCapacity = capacity(), capacity = oldCapacity; If (slowpath(isConstantEmptyCache())) {// If the Cache does not already exist, initialize it to 4, and reset the Cache // Cache is read-only. Replace it. If (! capacity) capacity = INIT_CACHE_SIZE; reallocate(oldCapacity, capacity, /* freeOld */false); } else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { // 4 3 + 1 bucket cache_t // Cache is less than 3/4 full. Use it as-is. } else { capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; 4 if (capacity > MAX_CACHE_SIZE) {capacity = MAX_CACHE_SIZE; } reallocate(oldCapacity, capacity, true); } bucket *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 because the // minimum size is 4 and we resized at 3/4 full. do { if (fastpath(b[i].sel() == 0)) { incrementOccupied(); b[i].set<Atomic, Encoded>(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)); cache_t::bad_cache(receiver, (SEL)sel, cls); }Copy the code

Insert is the core method for caching by CACHE_t. The main operations are as follows:

1. Determine whether to expand the capacity

The 'reallocate' method is called when the 'cache' is empty or the number of 'buckets' after being inserted is greater than three quarters of its original capacity. 'reallocate' is mainly responsible for '_buckets' reopening memory and' old _buckets' release.Copy the code

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) {
        cache_collect_free(oldBuckets, oldCapacity);
    }
}
Copy the code

Reallocate does a few things:

According to incomingnewCapacityCreate a newbucket
Will the newbucketAssigned to the currentcache, and updatemaskThe value ofnewCapacity - 1
If necessary, release the old onesbucket
It’s important to note, because the initial capacity is zero4And each expansion will be the old capacity2Times PI, so the new capacity has to be 2ⁿ.maskThe value is 2ⁿ– 1

2.`sel`and`imp`Put in the specified`bucket`In the

As mentioned earlier, methods stored in _buckets are not sequentially stored. What is the rule? The answer is also in insert. The idea for finding the corresponding bucket is as follows:

According to thecache_hashMethods to obtainselThe corresponding hashkey.

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}
Copy the code

If the value of sel is 0, then the final value of sel is 0, then the final value of sel is 0

If the bucket->sel corresponding to position 2 is equal to the current sel, it is possible that other threads cache this method and return it directly.

Otherwise, a hash conflict has occurred, and you need to find a new hash value.

//__arm64__ Cache_next is implemented differently in different architectures and needs to be noted. static inline mask_t cache_next(mask_t i, mask_t mask) { return i ? i-1 : mask; }Copy the code

inarm64The schema resolves conflicts by looking one bit ahead, and if the first bucket array is still a conflict, starting at the last bit of the array. When the search returns to the original starting point, the current exception occurs and executesbad_cacheLogic.

At this point, the process of caching the method ends, the core methodinsertThe flow chart is as follows:

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.

Class structure analysis -Cache_t

Cache_t profile

Cache_t explore

Cache_t underlying implementation

insert

1. Determine whether to expand the capacity

2.`sel`and`imp`Put in the specified`bucket`In the

Class structure analysis -Cache_t

Cache_t profile

Cache_t explore

Cache_t underlying implementation

insert

1. Determine whether to expand the capacity

2.selandimpPut in the specifiedbucketIn the

Related Posts

IOS shell build with xcodeBuild +curl… Jane the book –

IOS OC method of resolution and message forwarding principle

Question sharing at the bottom level of iOS (with planning and positioning of iOS engineer)

2.`sel`and`imp`Put in the specified`bucket`In the