Study in harmony! Not anxious not impatient!! I am your old friend Xiao Qinglong
Today we’ll explore the cache structure in objc_class, using command+ standalone to enter the cache_t structure:
// The structure of objc_class is 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. };// The cache_t structure is as follows
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; }; . };Copy the codeAs you can see, its main structure is _bucketsAndMaybeMask and union. Doesn’t seem to be structurally obvious either? It’s just that cache is literally called cache, and it’s not clear whether the properties or methods are cached. Let’s print LLDB first:
Doesn’t seem to show any cache from the picture either? However, we can analyze that since it is a cache, we must have read and write functions. We can look inside the source struct cache_t structure to see if there is any method for reading and writing.
void insert(SEL sel, IMP imp, id receiver);
Copy the codeLet’s go to Insert:
void cache_t::insert(SEL sel, IMP imp, id receiver)
{
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)) {
// If the slot is empty, insert sel, IMP, and return
incrementOccupied();
b[i].set<Atomic, Encoded>(b, sel, imp, cls());
return;
}
// return if the match is already cached
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
}
/** buckets() is used to store buckets. You can also use buckets to store buckets. You can also use buckets to store buckets. Here is a do... While loop, that means we're going through sel and IMP, and when we find sel and IMP, we don't have to insert, we just return. The do comparison is b[I].sel() == sel, which means sel is read by the sel() method. * /
Copy the codeNext, we refer to the way LLDB is printed in do:
So we print sel, next we want to print IMP, we find 3 names with IMP:
struct bucket_t {
...
uintptr_t encodeImp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, IMP newImp, UNUSED_WITHOUT_PTRAUTH SEL newSel, Class cls) const{... } inline IMP rawImp(MAYBE_UNUSED_ISA objc_class *cls)const{... } inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls)const {...}
...
/** select * from imp; encodeImp; rawImp; At present, we don't know which one is, how to do, can only try one by one, LLDB play */
};
Copy the codeNext LLDB prints these three:
The above is through the LLDB method of debugging, and rely on the source environment, once you want to see SEL, IMP in your own project is not feasible. So if I have to read it in my own project, is there any way I can print it? OK, if you can see here, you must have a certain understanding of the structure of class (if you haven’t, please turn over my previous article). So why don’t we just copy the system and create our own objc_class structure? Just do it
Customize the – – – – – – – – – – – – objc_class structure
Because we mainly analyze buckets
struct cache_t {
...
public:
struct bucket_t *buckets() const; . };Copy the codeCommand + standalone into “buckets” :
struct bucket_t *cache_t::buckets() const
{
uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
return (bucket_t *)(addr & bucketsMask);
}
Copy the codeAs you can see, buckets are loaded by _bucketsAndMaybeMask, so you can customize a cache_t structure by replacing _bucketsAndMaybeMask with “struct bucket_t *”. So the final custom structure looks like this:
typedef uint32_t mask_t; // x86_64 & arm64 asm are less efficient with 16-bits
/// Customize ssj_bucket_t to replace bucket_t of the system
// Note the sequence of _sel and _IMP
struct ssj_bucket_t {
SEL _sel;
IMP _imp;//uintptr_t
};
/// Customize ssj_cache_t to replace the system cache_t
// Because the current operating system supports LP64, the union is not mutually incompatible. You can delete the code below by pointing out the uint16_t _flags
///struct (struct, struct, struct, struct, struct, struct)
struct ssj_cache_t {
struct ssj_bucket_t *_buckets;
mask_t _maybeMask;/// You can see the internal type, which is uint32_t
uint16_t _flags;
uint16_t _occupied;// The number of methods currently cached. How many positions have been used in the array
};
/// Customize ssj_class_data_bits_t to replace class_data_bits_t of the system
struct ssj_class_data_bits_t {
//friend objc_class; /// This line can also be removed, not our concern
uintptr_t bits;
};
/// Customize ssj_objc_class to replace objc_class in the system
struct ssj_objc_class {
Class ISA;/// If you do not open it, the cache will be incorrectly fetched and the output will be incorrect
Class superclass;
struct ssj_cache_t cache; // formerly cache pointer and vtable
struct ssj_class_data_bits_t bits; // class_rw_t * plus custom rr/alloc flags
};
Copy the codeNext, let’s print:
int main(int argc, char * argv[]) {
Student *stu = [Student alloc];
Class stuClass = stu.class;
[stu run];// Instance method
struct ssj_objc_class *ssjClass = (__bridge struct ssj_objc_class *)(stuClass);
NSLog(@"-->%hu \n",ssjClass->cache._occupied);
NSLog(@"-->%hu \n",ssjClass->cache._flags);
NSLog(@"-->%u \n",ssjClass->cache._maybeMask);
for (mask_t i = 0; i< ssjClass->cache._maybeMask; i++) { struct ssj_bucket_t bucket = ssjClass->cache._buckets[i]; NSLog(@"sel->%@ imp->%pf",NSStringFromSelector(bucket._sel),bucket._imp); }... };Copy the codePrint result:
Let’s call a few more methods:
int main(int argc, char * argv[]) {
Student *stu = [Student alloc];
Class stuClass = stu.class;
[stu run];// Instance method
[stu sleep];// Instance method
[stu dump];// Instance method
[stuClass eat];/ / class methods
struct ssj_objc_class *ssjClass = (__bridge struct ssj_objc_class *)(stuClass);
NSLog(@"-->%hu \n",ssjClass->cache._occupied);
NSLog(@"-->%hu \n",ssjClass->cache._flags);
NSLog(@"-->%u \n",ssjClass->cache._maybeMask);
for (mask_t i = 0; i< ssjClass->cache._maybeMask; i++) { struct ssj_bucket_t bucket = ssjClass->cache._buckets[i]; NSLog(@"sel->%@ imp->%pf",NSStringFromSelector(bucket._sel),bucket._imp); }... };Copy the codePrint result:
_maybeMaskThe print from the original3Turned out to be7And some methods are not printed out. Why? To explore this, we first need to know that all of the above printing operations are bucketsreadWe can start by looking inside howinsertBucket data.
Go to the cache_t structure and search for”insert“To find:
void insert(SEL sel, IMP imp, id receiver);
Copy the codeInsert:
void cache_t::insert(SEL sel, IMP imp, id receiver){...// Use the cache as-is if until we exceed our expected fill ratio.
; // Occupied +1, the number of occupied methods
mask_t newOccupied = occupied() + 1;
unsigned oldCapacity = capacity(), capacity = oldCapacity;
/// On the first insert, the Cache is empty and the first if block is entered
if (slowpath(isConstantEmptyCache())) {
// Cache is read-only. Replace it.
if(! capacity) capacity = INIT_CACHE_SIZE;//capacity = 4
/// Set the _bucketsAndMaybeMask and _maybeMask, as well as the previous buckets
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 the sum on the left is smaller than the sum on the right, then the occupied value will enter the block: newOccupied + 1; CACHE_END_MARKER is constant 1; Capacity = _maybeMask + 1 Return value: Capacity * 3/4; If (1+1) +1 <= (3 +1) *3/4 = 3) else if (1+1) +1 <= (3 +1) *3/4 = 3) If (2+1) +1 <= (3 +1) *3/4 = 4) else if (2+1) +1 <= (3 +1) *3/4 * /
}
#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 {
/** The third insert will enter here: double capacity */
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
/** After the following reallocate, _maybeMask becomes 7. This is why the console printed before, _maybeMask printed 7; Note that reallocate's last parameter, true, indicates that you need to clear all the oldBuckets, because at the bottom, capacity expansion is actually opening up new memory, and the translation of arrays is performance expensive, so you don't add the oldBuckets, you just add the new buckets. * /
reallocate(oldCapacity, capacity, true);
}
/// Get the current buckets
bucket_t *b = buckets();
mask_t m = capacity - 1;// This is why =3 or 7
/// get a hash address
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 {
/// Enter the statement block if sel is null
if (fastpath(b[i].sel() == 0)) {
// The occupied value is 1
incrementOccupied();
/// bind sel and IMP
b[i].set<Atomic, Encoded>(b, sel, imp, cls());
return;
}
// if b[I].sel is not null, return sel directly
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 codeCache_t structure:
oid cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
// Get the address of Buckets
bucket_t *oldBuckets = buckets();
/// Open newCapacity number of Spacesbucket_t *newBuckets = allocateBuckets(newCapacity); ./// Set _bucketsAndMaybeMask and _maybeMask, where _maybeMask = newCapacity - 1
setBucketsAndMask(newBuckets, newCapacity - 1);
/// Do you need to release the previous buckets
if(freeOld) { collect_free(oldBuckets, oldCapacity); }}Copy the codeSetBucketsAndMask method:
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
#ifdef __arm__
...
/ / / _bucketsAndMaybeMask assignment_bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_relaxed); ./ / / _maybeMask assignment
_maybeMask.store(newMask, memory_order_relaxed);
// the occupied is 0 because sel and IMP are unbound
_occupied = 0;
#elif __x86_64__ || i386
/ / / _bucketsAndMaybeMask assignment
_bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_release);
/ / / _maybeMask assignment
_maybeMask.store(newMask, memory_order_release);
The occupied method is occupied; /// the _occupied method is occupied
_occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}
Copy the codeCollect_free method:
// The memory of bucket_t has been garbage collected
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 codeDiagram of cache and Buckets – – – – – – – – – – – –
More on – – – – – – – – – – – – (20216 30)
See here, do you have any questions? Anyway, I have a few questions:
- Buckets [I] is an array? Buckets [I] is an array?
- What does the string of numbers in the value of _bucketsAndMaybeMask represent when printing the cache_T structure?
- In bucket insert, consider 3/4 expansion, so why if 3/4, not 1/2? What good would it do?
With these questions in mind, let’s explore and open the OBJC source code for LLDB debugging:
struct bucket_t *cache_t::buckets() const
{
uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
return (bucket_t *)(addr & bucketsMask);
}
// _bucketsAndMaybeMask is a buckets_t pointer
// _maybeMask is the buckets mask
static constexpr uintptr_t bucketsMask = ~0ul;
Copy the codeWe can conclude that _bucketsAndMaybeMask records the address of Buckets, and that buckets() returns a pointer to bucket_t.
Let’s move on to the bucket structure:
struct bucket_t {... }Copy the codeWe see that bucket_t is a structure, so why can it fetch buckets in an array-like manner? There is a concept of “memory offsetting”, where arrays and buckets are accessed by offsetting the first address by a certain size. For the concept and argument of memory offsets, for the memory offsets argument in terms of arrays, see my previous article isa analysis and other explorations (above), search for “memory offsets”. Next, let’s verify that the same is true for bucket access:
The next step is to answer the third question, 3/4 expansion because the load factor is 0.75 when the utilization is higher, can effectively avoid hash conflicts.
Cache – – – – – – – – – – – -insert Further analysis
Due to the length of this article, the rest of the cache content will be put in another article: iOS low-level analysis and the like exploration – Cache insert, objc_msgSend
The code has been uploaded to Baidu web disk:
Objc4 818.2 source: link: pan.baidu.com/s/1v09V2YGj… Password: y8mz Demo links: link: pan.baidu.com/s/1WRE2VpMP… Password: 9 y8s