preface
In objc_msgSend& Fast method Lookup, we explored the quick lookup process of objc_msgSend and analyzed its assembly code, which is mainly used to quickly find if there is a method in the cache. If there is, it will call directly. But we’re left with the question of what happens if we don’t find it. Today we’re going to explore what Apple does if a quick search fails.
objc_msgSend_uncached
\MissLabelDynamicThis argument, this argument is actually what we callCacheLookupFunction__objc_msgSend_uncachedThis way, then we search for him globally
TailCallFunctionPointer
Simple lines of assembly code with only two methods, one called methodTable – ookup and one called TailCallFunctionPointer. Since it is the return value of the method that is most important, start from behind and search globally for TailCallFunctionPointer
.macro TailCallFunctionPointer
// $0 = function pointer value
br $0
.endmacro
Copy the codeVery simple code that goes back and jumps to the $0 position to execute, which is essentially the function returned.
MethodTableLookup
In that case, x17 will just have to be assigned to the method table and continue exploring it
.macro MethodTableLookup
SAVE_REGS MSGSEND
// lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
// receiver and selector already in x0 and x1
//** assigns x16 to x2, our Class object **
mov x2, x16
//** assigns 3 to x3**
mov x3, #3
bl _lookUpImpOrForward
//** assigns x0 to x17**
mov x17, x0
RESTORE_REGS MSGSEND
.endmacro
Copy the code_lookUpImpOrForward
In this method, we can easily find the place to assign x17, which is x0, so what is x0? Look for the answer in _lookUpImpOrForward because x0 is its return value.
_Get rid of it. Go straight to searchlookUpImpOrForwardTake a look at
objc-runtime-new.mmFind the implementation of this method, and its return value, is the IMP we are looking for.
conclusion
Let’s take a quick look at objc_msgSend_uncached processes
- will
MethodTableLookupMethod return valuex17throughTailCallFunctionPointerReturn back MethodTableLookupMethod, through_lookUpImpOrForwardMethod findIMPAnd then assign tox17
So why is the fast method written in assembly, and why is the lookUpImpOrForward method lookup flow written in C/C++? The answer is
- Assembly code, closer to machine language, more efficient execution. The purpose of searching in the cache is also to be more efficient, so assembly is more suitable for the fast method searching process.
- Assembly code is relatively difficult to understand and more secure than C/C++
- Arguments in assembly are more dynamic, unlike C/C++ where methods must have arguments or they cannot be called
LookUpImpOrForward process
After exploring objc_msgSend_uncached, we take a look at what lookUpImpOrForward actually does.
NEVER_INLINE
//**behavior = 3 LOOKUP_INITIALIZE|LOOKUP_RESOLVER**
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
//** dynamic method resolution initialization **
const IMP forward_imp = (IMP)_objc_msgForward_impcache;
IMP imp = nil;
Class curClass;
runtimeLock.assertUnlocked(a);//** Checks whether the class is initialized, if not **
/ / * * the behaviors = LOOKUP_INITIALIZE | LOOKUP_RESOLVER | LOOKUP_NOCACHE * *
if (slowpath(! cls->isInitialized())) {
behavior |= LOOKUP_NOCACHE;
}
runtimeLock.lock(a);//** Determines whether to register class **
checkIsKnownClass(cls);
//** The parent, metaclass of the initial class, the parent, metaclass of the already parent class, etc., until the root class and the root class are initialized **
cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
runtimeLock.assertLocked(a); curClass = cls;//** enter a loop
for (unsigned attempts = unreasonableClassCount();;) {
//** to check whether there is a shared cache, usually the system function method can call **
if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
#if CONFIG_USE_PREOPT_CACHES
//** The '_cache_getImp' assembly code is also called, and finally 'CacheLookup' is called to find the shared cache **
//** Because it is possible that while you are calling, another thread has already written to the cache, so you can call ** directly
imp = cache_getImp(curClass, sel);
//** Jump directly to done_unlock**
if (imp) goto done_unlock;
//** is marked as not using the shared cache, and then on the next loop, the else process continues to look for **
curClass = curClass->cache.preoptFallbackClass(a);#endif
} else {
//** get the list of methods of the current class, use binary search Method to find sel Method**
Method meth = getMethodNoSuper_nolock(curClass, sel);
if (meth) {
// select * from sel imp**
imp = meth->imp(false);
/** * done**
goto done;
}
//** assigns curClass to its parent and determines if it equals nil**
if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
// if ** is equal to nil, the dynamic method resolution is directly entered, i.e., ** is not found
imp = forward_imp;
break; }}if (slowpath(--attempts == 0)) {
_objc_fatal("Memory corruption in class list.");
}
// Superclass cache.
** Use the cache_getImp quick method lookup process to find if the method exists in the parent's cache **
imp = cache_getImp(curClass, sel);
if (slowpath(imp == forward_imp)) {
//** if the parent class returns forward_IMP, stop the search and jump **
break;
}
/** done** if found in the parent class cache
if (fastpath(imp)) {
goto done;
}
//** this is the end of the loop, which means that if no method is found in the parent's cache, the loop will continue, starting from the beginning **
//** Because curClass already refers to the parent class, loop again to find the list of methods of the parent class **
}
/ / * * this time of the incoming behaviors for LOOKUP_INITIALIZE | LOOKUP_RESOLVER * *
//**条件成立，会进入，然后重置behavior为LOOKUP_INITIALIZE**
//** does not enter ** when called again
if (slowpath(behavior & LOOKUP_RESOLVER)) {
behavior ^= LOOKUP_RESOLVER;
//** dynamic method resolution process **
return resolveMethod_locked(inst, sel, cls, behavior);
}
done:
//** The uninitialized class contains LOOKUP_NOCACHE in the condition above, so it will not enter, otherwise it will enter **
if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
#if CONFIG_USE_PREOPT_CACHES
while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
cls = cls->cache.preoptFallbackClass(a); }#endif
//** inserts the found method into the cache of the current class **
//** the next call will find ** directly in quick method lookup
log_and_fill_cache(cls, imp, sel, inst, curClass);
}
done_unlock:
runtimeLock.unlock(a);//** dynamic method resolution completed, still no method, return nil**
if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
return nil;
}
//** returns the found IMP **
return imp;
}
Copy the codeLookUpImpOrForward process in text
Because this process is to go through the loop to find the whole method list, the overall speed is much slower than the fast search process, so we call the method of slow search distance, we use the text to summarize, the whole slow search process
- In the first place to judge
classIf no, an error will be reported - According to the
Isa a chainandIsa inheritance chainTo initialize the parent class, the metaclass of the current class, until the root class and the root class are initialized - Go into a loop
- Check whether to use the shared cache. If yes, check whether the method exists in the shared cache. If yes, jump out of the loop directly
done - Gets the list of methods of the current class without using the shared cache
methodlist, use the dichotomy search method to find whether there is such a method, find out of the loop, godone - If not found, the current class is assigned to
The parent classAnd determine whether it isnilIf it is empty, it jumps out of the loop without a parent class - through
Fast method lookupTo findThe parent classWhether the method exists in the cache of - If the
The parent classFind a method in the cache, determine whether it is a dynamic method resolution method, if it is out, otherwise out of the loopdone - When looking for the
classtheThe parent class, until the root class can not find the method, the end of the endless loop - If the dynamic method resolution process has not been performed, the system will give another chance to invoke the dynamic method resolution process
- If the method is eventually found, it is written to the cache for quick lookup next time
The flow chart of lookUpImpOrForward
Binary search method search method
One of the things that we missed out on in the above process is how do we find the methods that we need in methodList, and we mentioned binary lookup, so let’s see, how does that work
static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
runtimeLock.assertLocked(a);ASSERT(cls->isRealized());
//** Gets the list of methods in the current class **
auto const methods = cls->data() - >methods(a);//** loop current method list, we know two-dimensional, this is loop first layer **
for (auto mlists = methods.beginLists(),
end = methods.endLists(a); mlists ! = end; ++mlists) {//** get the first address of each element to find if there is sel** that meets the condition
method_t *m = search_method_list_inline(*mlists, sel);
// Return ** when ** is found
if (m) return m;
}
return nil;
}
Copy the codeIt is obvious that this method is the first layer, analytical methodlist core search method is search_method_list_inline, and this method is nested inside the layers, we directly findMethodInSortedMethodList look at the core of the method
ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)
{
ASSERT(list);
//** gets the first element of the list **
auto first = list->begin(a);//** set base to first**
auto base = first;
// initialize probe with type first **
decltype(first) probe;
//** convert sel we are looking for to address **
Since our methodList is already sorted, we can simply use binary lookup **
uintptr_t keyValue = (uintptr_t)key;
uint32_t count;
//**count is the number of nodes in the list **
//**count >> = 1 is the same as count = count / 2**
//** suppose our count = 8**
// the method we need to find is in the 5th **
//** first loop :count = 8,base = 0**
//** second loop: execute count>>=1,count = 3,base = 5**
//** third loop: execute count>>=1,count =1, base = 5**
for(count = list->count; count ! =0; count >>= 1) {
//** assigns the intermediate value probe,**
// first loop :probe = 0 + 8 >> 1 =4**
//** second loop :probe = 5 + 3 >> 1 =6**
//** third loop :probe =5 + 1 >> 1 =5**
probe = base + (count >> 1);
//** Obtain the address of the element corresponding to the probe value, because it has been sorted, it can be compared **
uintptr_t probeValue = (uintptr_t)getName(probe);
//** if the two values are equal, then probeValue is the method we are looking for **
//** first loop :5! = 8 * *
//** second loop :5! = 6 * *
//** loop 3: == 5, find **
if (keyValue == probeValue) {
//** class overrides, classes have methods with the same name **
//** if there is a classification method, we will get the classification method, multiple classification depends on the compilation order **
while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
probe--;
}
//** returns the address of buket **
return &*probe;
}
//** If the target key is greater than the intermediate key, base = intermediate +1, total Count minus 1**
/ / * * the first cycle: 5 > 4, base = 4 + 1 = 5, the count = 8 - = 7 * *
//** second loop :5 < 6, base = 5, count = 3**
if (keyValue > probeValue) {
base = probe + 1;
count--;
}
//** loop ** again
}
return nil;
}
Copy the codeIn the code, we take an example, a total of eight elements, the target element in the fifth position, the binary search process, let’s use the figure to explain, may be more clear
conclusion
We know that method invocation in OC is actually the process of sending messages. In this article, we explore the slow lookup process of methods together with the ISA bitchain and ISA inheritance chain we explored earlier, as well as the process of dynamic method resolution and message forwarding, which we will continue to explore later.