In the previous article, objc_msgSend Quick Lookup, I explored the nature of function calls, namely message sending: objc_msgSend, and explored the flow of objc_msgSend quick method lookup (i.e., cache lookup) in assembly code. In the fast method lookup process, if the cache hits, the corresponding method is executed; If MissLabelDynamic is not hit, a slow method lookup process is entered, i.e. the lookUpImpOrForward method in C/C++ code is executed.

1. Explore slow search

In addition to reading assembly code, a debug approach can be used to explore the entry lookUpImpOrForward method of a slow method lookup. Set debug to display the assembly running process, as shown in the following figure:

In the example code [user sayHello8]; Set a breakpoint at and execute the program. The stack appears as follows:

Method calls are essentially sending a message, objc_msgSend. Press CTRL at the breakpoint and click Step into to enter the objc_msgSend process.

Process analysis:

The process is too long to understand and is consistent with the assembly process in objc_msg_arm64.s. Some clues can be found in some key points. For example, the mask 0x7FFFFFFFF8, which is familiar, is actually the ISA_Mask value in the X86_64 environment.

#   elif __x86_64__
#   define ISA_MASK        0x00007ffffffffff8ULL
Copy the code

It is not difficult to understand that the mask operation of the ISA pointer is used to obtain the class object, and then a series of operations are performed on the object. If the cache does not hit, the assembly function _objc_msg_Send_uncached is used. Set the breakpoint here, and after the program runs out, press CTRL and click Step into to enter the _objc_msg_Send_uncached process. See below:

LookUpImpOrForward at objc-runtimenew. mm:6394.

2. Method search, exploration and thinking

In a simple case, Son inherits from Father. The Son class has only method declarations, but no method implementations. The Father class declares and implements methods.

@interface Father : NSObject
-(void)sayHello;
+(void)sayNB;
@end
@implementation Father

-(void)sayHello{
    NSLog(@"sayHello %s", __func__);
}
+(void)sayNB{
    NSLog(@"sayNB %s", __func__);
}
@end

@interface Son : Father
-(void)say666;
-(void)sayHello;
+(void)sayNB;
@end
@implementation Son
-(void)say666{
    NSLog(@"say666 %s", __func__);
}
@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        Son *son = [[Son alloc] init];
        [son say666];
        [son sayHello];
        [Son sayNB];
    }
    return 0;
}
Copy the code

The operation structure is shown in the following figure:

Run result:

Calling object methodssay666,sayHello, calling a class methodsayNBNo error was reported, and the parent class was successfully calledFatherIs implemented in.
sonObject methods are stored inSonIn the class,sonobjectisaPoint to theSonClass,SonclasssuperclassPoint to theFatherClass objects.
SonClass methods are stored inSonYuan class,SonclassisaPoint to theSonMetaclasses,SonThe metaclasssuperclassPoint to theFatherThe metaclass.
SonClasses andFatherClass has the above2Layer relationship, thatObject method sayHelloandClass methods sayNBIt must be because of this relationship that the method implementation is successfully found, so that the program does not report errors.

Or is it? Continue to explore the source code.

3. Slow search and exploration

Search globally for the lookUpImpOrForward method in the objC Runtime source libobjc.a. dylib. Look for a method implementation of lookUpImpOrForward in objc_runtime_new.mm. The code is as follows:

Objc_msgSend quick cache lookup (cache_t) // 2 -- Miss, LookUpImpOrForward Slow lookup NEVER_INLINE IMP lookUpImpOrForward(ID INST, SEL SEL, Class CLS, int behavior) { // forward_imp const IMP forward_imp = (IMP)_objc_msgForward_impcache; IMP imp = nil; Class curClass; runtimeLock.assertUnlocked(); if (slowpath(! cls->isInitialized())) { behavior |= LOOKUP_NOCACHE; } // Lock to ensure thread-safe reading runtimelock.lock (); CheckIsKnownClass (CLS) : checkIsKnownClass(CLS); / / determine whether the class implementation, if not, need to realize the CLS = realizeAndInitializeIfNeeded_locked (inst, CLS, behaviors & LOOKUP_INITIALIZE); // runtimeLock may have been dropped but is now locked again runtimeLock.assertLocked(); curClass = cls; Unsigned attempts = unreasonableClassCount();; { if (curClass->cache.isConstantOptimizedCache(/* strict */true)) { #if CONFIG_USE_PREOPT_CACHES imp = cache_getImp(curClass, sel); if (imp) goto done_unlock; curClass = curClass->cache.preoptFallbackClass(); #endif} else {// curClass method list. // Look for methods in the current class method list (binary search algorithm), return if found, Method meth = getMethodNoSuper_nolock(curClass, sel); if (meth) { imp = meth->imp(false); goto done; } // If the superclass is not found, the superclass finds the superclass or the supermetaclass. If the superclass is nil, If (slowPath ((curClass = curClass->getSuperclass()) == nil)) {// No implementation found, // Use forward_imp; // Use forward_imp; // Use forward_imp; // Use forward_imp; break; } } // Halt if there is a cycle in the superclass chain. if (slowpath(--attempts == 0)) { _objc_fatal("Memory corruption  in class list."); } // Superclass finds the Superclass and looks in the Superclass cache. // Superclass finds the Superclass and looks in the Superclass cache. // Superclass finds the Superclass cache. // Superclass cache. imp = cache_getImp(curClass, sel); if (slowpath(imp == forward_imp)) { break; } if (fastpath(imp)) { // Found the method in a superclass. Cache it in this class. goto done; } } // No implementation found. Try method resolver once. if (slowpath(behavior & LOOKUP_RESOLVER)) { behavior ^= LOOKUP_RESOLVER; return resolveMethod_locked(inst, sel, cls, behavior); } done: if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) { #if CONFIG_USE_PREOPT_CACHES while (cls->cache.isConstantOptimizedCache(/* strict */true)) { cls = cls->cache.preoptFallbackClass(); } #endif log_and_fill_cache(cls, imp, sel, inst, curClass); } done_unlock: runtimeLock.unlock(); if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) { return nil; } return imp; }Copy the code

1. Source code process analysis

Initialize forward_IMP.

Determine whether the current class is an approved class, that is, a loaded class. Then the bidirectional link list relationship of class and parent class is established, and the inheritance chain of class is determined. At this time, the purpose is to determine the parent class chain and facilitate the subsequent cycle.

CheckIsKnownClass (CLS) : checkIsKnownClass(CLS); / / determine whether the class implementation, if not, need to realize the CLS = realizeAndInitializeIfNeeded_locked (inst, CLS, behaviors & LOOKUP_INITIALIZE); // runtimeLock may have been dropped but is now locked again runtimeLock.assertLocked(); curClass = cls;Copy the code

Unsigned attempts = unreasonableClassCount();;) , current curClass, which can be a class or metaclass, but ultimately calls object methods.
First, look in the list of methods of the current class, using binary search.
```
// curClass method list. // Look for methods in the current class method list (binary search algorithm), if found, return, Method meth = getMethodNoSuper_nolock(curClass, sel); if (meth) { imp = meth->imp(false); goto done; }Copy the code
```
If the method is found in the method list, jump to DONE and insert the method into the cache, the buckets in cache_T, and return IMP, i.e. Step 8. If no method is found in the method list, go to Step 5.

Find a superclass or metaclass based on superclass and assign a value to curClass.

// If the superclass is not found, superclass finds the superclass or metaclass. If the superclass is nil, If (slowPath ((curClass = curClass->getSuperclass()) == nil)) {// No implementation found, // Use forward_imp; // Use forward_imp; // Use forward_imp; // Use forward_imp; break; }Copy the code

If the superclass is nil, NSObject has been found, forward_IMP is assigned by default, and you break out of the loop and go to Step 7. If the superclass is not nil, go to Step 6.

Perform a cache lookup (assembly flow) on the current class. If the cache is still not found, IMP = nil and continue the loop to Step 3. If the IMP is found, jump to DONE and insert the method into the cache, the buckets in cache_T, in Step 8.

// Superclass finds the Superclass and finds the Superclass in the cache. // Superclass finds the Superclass in the cache. // Superclass finds the Superclass in the cache. // Superclass cache. imp = cache_getImp(curClass, sel); if (slowpath(imp == forward_imp)) { // Found a forward:: entry in a superclass. // Stop searching, but don't cache yet; call method // resolver for this class first. break; } if (fastpath(imp)) { // Found the method in a superclass. Cache it in this class. goto done; }Copy the code

The dynamic method resolution process can be understood as giving a second chance to remedy.

if (slowpath(behavior & LOOKUP_RESOLVER)) {
    behavior ^= LOOKUP_RESOLVER;
    return resolveMethod_locked(inst, sel, cls, behavior);
}
Copy the code

The search succeeds, and the IMP SEL is inserted into the cache. Which is in buckets in cache_T. Prepare for the next quick lookup directly from the cache.

 done:
    if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
#if CONFIG_USE_PREOPT_CACHES
        while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
            cls = cls->cache.preoptFallbackClass();
        }
#endif
        log_and_fill_cache(cls, imp, sel, inst, curClass);
    }
Copy the code

Return imp and the process ends.

Summary: The source code implementation does verify the conjecture in part 2, and indeed finds methods all the way up through the superclass of the class.

The source code is easy to understand and consistent with our assumptions, but need to verify the debug trace! Still the above case for tracking debugging!

2. This class has implemented methods

The object method say666 is implemented in the Son class. The code is run and traced to the slow method search process. After binary search, the corresponding object method is successfully obtained from the method list. At this point, curClass is the CLS class passed in, that is, the Son class, has not found the superclass. See below:

After finding the method in the method list, jump to Done. Insert the method into the method cache, which is cache_t, to form a closed loop!

Finally, cache::insert is called, and a closed loop is formed! The next time the same method is called, a quick method lookup is done directly from the cache. That’s what I explored in my last article, Quick Method Lookup.

If a cache_T expansion occurs in this process, you need to repeat the above process: fast method lookup, no lookup, slow method lookup, insert cache!

3. There are implementations in the parent class

The object method sayHello, which is not implemented in the Son class, is implemented in the parent class Father. Run the code, trace to the slow method lookup process, binary search looks for the method from the method list, and the method returns null. See below:

In this case, curClass is set to Father. In this case, cache_getImp is used to look for the corresponding method in the superclass cache. See below:

When no method is found in the parent class cache, the for loop continues, looking through the list of methods in the current class curClass (Father) and finding the method successfully. See below:

When the method is found, jump to done. Insert the method into the method cache, which is cache_t.

4. Class methods

The sayNB class method is invoked to enter the slow method search process. In this case, the curClass is the Son metaclass, and no meth is found in the metaclass. See below:

The corresponding method was not found in the Son metaclass. The superclass was used to find the Father metaclass, and the corresponding method implementation was found in the parent metaclass.

When the method is found, jump to done. Insert the method into the method cache, which is cache_t. At the same time, the process can be explained that there are no class methods at the bottom, all are object methods. Classes are objects of metaclass!

5. Cache_getImp analysis

Cache_getImp looks for method implementations from the method cache. What is the process for cache_getImp? The assembly implementation is found in objc_msg_arm64.s, see the source code below:

	STATIC_ENTRY _cache_getImp

	GetClassFromIsa_p16 p0, 0
	CacheLookup GETIMP, _cache_getImp, LGetImpMissDynamic, LGetImpMissConstant

LGetImpMissDynamic:
	mov	p0, #0
	ret

LGetImpMissConstant:
	mov	p0, p2
	ret

	END_ENTRY _cache_getImp
Copy the code

Eventually the macro CacheLookup is called, but with different arguments. If no corresponding cache method is found, LGetImpMissDynamic is returned, which is empty 0x0, instead of doing a slow method lookup!

4. Detailed binary search

Binary Search, also known as Binary Search, is a highly efficient Search method. However, the split search requires that the linear table must have a sequential storage structure and that the elements in the table are arranged in keyword order. The source code is as follows:

/********************************************************************** * search_method_list_inline **********************************************************************/ template<class getNameFunc> ALWAYS_INLINE static  method_t * findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName) { ASSERT(list); auto first = list->begin(); auto base = first; decltype(first) probe; uintptr_t keyValue = (uintptr_t)key; uint32_t count; // base = low, count = Max, probe = middle for (count = list->count; count ! = 0; Count >>= 1) {// probe = base + (count >> 1); // Obtain the sel name of the location uintPtr_t probeValue = (uintPtr_t)getName(probe); // If the keyvalue of the probe is equal to the probeValue of the probe, If (keyValue == probeValue) {// 'probe' is a match. // Rewind looking for the *first* occurrence of this Value. // This is required for correct category overrides. // This is required for correct category overrides. While (uintptr_t)getName((probe-1)) {probe--; } return &*probe; If (keyValue > probeValue) {base = probe + 1; if (keyValue > probeValue) {base = probe + 1; count--; } } return nil; }Copy the code

Case study:

Consider method_list_t [0 x10, 0 x20, 0 x30, 0 x40, 0 x50, 0 x60, 0 x70, 0 x80] number of 8 orderly array.

Now we need to find method 0x30, and the process is as follows:
- The initial value:Base = 0x10, count = 8;
- A loop:0x50 = 0x30; 0x50 = 0x30; Left search;
- Loop 2:Base = 0x10, count = 4; Probe = 0x30, found!
Find method 0x60, the process is as follows:
- The initial value:Base = 0x10, count = 8;
- A loop:0x50 = 0x60; 0x50 = 0x60; Search on the right;
- Loop 2:Base = 0x60, count = 3; Probe = 0x70, not found;
- Cycle 3:Base = 0x60, count = 1; Probe = 0x60, find;

5. Understanding method lookup

Each object has a pointer isa to its own class. Through this pointer, an object can find its class, and therefore all of its parent classes.

When sending a message to an object, the objc_msgSend method finds the object’s class based on the object’s ISA pointer and then looks for selectors in the class’s Dispatch table. If it can’t find a selector, objc_msgSend finds the parent class through a pointer to the parent class, looks for a selector in the parent class’s Dispatch table, and so on up to NSObject. Once the selector is found, the objc_msgSend method calls the implementation based on the memory address of the schedule. In this way, the actual implementation of the message and method is bound at the execution stage.

To ensure the efficiency of message sending and execution, the system caches the memory addresses of all selectors and used methods. Each class has a separate cache containing its own selectors as well as those inherited from its parent class. Before looking up the Dispatch table, the message-sending system first checks the cache of the Receiver object.

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.

IOS Low-level learning — objc_msgSend slow lookup

1. Explore slow search

2. Method search, exploration and thinking

3. Slow search and exploration

1. Source code process analysis

2. This class has implemented methods

3. There are implementations in the parent class

4. Class methods

5. Cache_getImp analysis

4. Detailed binary search

5. Understanding method lookup

IOS Low-level learning — objc_msgSend slow lookup

1. Explore slow search

2. Method search, exploration and thinking

3. Slow search and exploration

1. Source code process analysis

2. This class has implemented methods

3. There are implementations in the parent class

4. Class methods

5. Cache_getImp analysis

4. Detailed binary search

5. Understanding method lookup

Related Posts

IOS design pattern analysis of MVC, MVP, MVVM

IOS underlying system: BSD layer details

Imitation Taobao logistics interface