One, when to enter the slow search
The quick lookup process is cache lookup. If it is not found in the cache, the method slow lookup process will be entered
Second, __objc_msgSend_uncached
Search globally for STATIC_ENTRY __objc_msgSend_uncached in objC source code
Arm64 source code content
STATIC_ENTRY __objc_msgSend_uncached
UNWIND __objc_msgSend_uncached, FrameWithNoSaves
// THIS IS NOT A CALLABLE C FUNCTION
// Out-of-band p15 is the class to search
MethodTableLookup
TailCallFunctionPointer x17
END_ENTRY __objc_msgSend_uncached
Copy the code
-
Source code analysis: core parts also methodTable ELookup and TailCallFunctionPointer x17
-
MethodTableLookup calls c++ code to perform a slow lookup process
-
TailCallFunctionPointer x17 jump to register X17 with the result of the previous step
MethodTableLookup
- Global search arm64 source code
.macro MethodTableLookup
SAVE_REGS MSGSEND
// lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
// receiver and selector already in x0 and x1
mov x2, x16
mov x3, #3
bl _lookUpImpOrForward
// IMP in x0
mov x17, x0
RESTORE_REGS MSGSEND
.endmacro
Copy the code
- What do we do with the source code
- X16 = class assigns x2
- 3 is assigned to x3
- Jump to _lookUpImpOrForward to look for IMP
- Place the IMP found in X0 and assign x0 to X17
TailCallFunctionPointer
// The IMP is found through the slow search process, so it will jump to register X17
// to provide subsequent assembly to continue execution
.macro TailCallFunctionPointer
// $0 = function pointer value
// $0 represents the parameter x17
braaz $0
.endmacro
.macro TailCallFunctionPointer
// $0 = function pointer value
br $0
.endmacro
Copy the code
Explore and learn
Quick Lookup process
No find will enterSlow search process
- Slow search process
__objc_msgSend_uncached
Will perform2
MethodTableLookup to find and returnimp
.TailCallFunctionPointer
Jump tox17
The register, which is thetaimp
Register in which - The slow lookup process will enter
C++
, then returns through the X0 register, continues down in assembly, and the method lookup process eventually jumps to the X17 register (either slow or fast lookup)
lookUpImpOrForward
NEVER_INLINE
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
// create forward_imp and give Dimmer the value _objc_msgForward_impcache
const IMP forward_imp = (IMP)_objc_msgForward_impcache;
IMP imp = nil;// Create an IMP to receive an IMP from sel
// Create the class to look for. This class is always changing through isa's pointing relationship.
// until it ends up pointing to NSObject's parent class nil
Class curClass;
runtimeLock.assertUnlocked();
if(slowpath(! cls->isInitialized())) {/** The first message sent to the class is usually +new or +alloc or +self but at this point the class has not been initialized, Behavior = 1, behavior = 1, LOOKUP_NOCACHE = 1, behavior = 1, LOOKUP_NOCACHE = 1, behavior = 1, LOOKUP_NOCACHE = 1, behavior = 1, LOOKUP_NOCACHE = 1, behavior = 1, LOOKUP_NOCACHE = 1, behavior = 1, LOOKUP_NOCACHE = 1, behavior = 1, LOOKUP_NOCACHE = 1 If the class is already initialized, behavior is not changed, behavior=3 and our custom method can be loaded into the cache. * /
behavior |= LOOKUP_NOCACHE;
}
// runtimeLock was held during checks by isRealized and isInitialized
// Prevent competing with concurrent implementations.
runtimeLock.lock();
// Check if the class is registered
checkIsKnownClass(cls);
/** Initializes CLS instance objects in each class (class and metaClass) in the ISA pointing diagram so that subsequent classes cannot find methods in the parent class, so all related classes are initialized here */
cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
//runtimeLock may have been dropped but is now locked again
runtimeLock.assertLocked();
//curClass is the current instance object's class
curClass = cls;
class_getInstanceMethod().
/** * Loops through the class object's methodList, looking for the parent if the current class doesn't have one Find all the way to the NSObject class * if NSObject isn't found * eventually curClass will point to nil * assign the prepared forward_IMP to IMP * and end the slow lookup process, and then go to the Runtime message forwarding mechanism */
for (unsigned attempts = unreasonableClassCount();;) {
if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
#if CONFIG_USE_PREOPT_CACHES
/** * The first step is to check if there are any methods in the shared cache. */ Usually our custom methods do not appear in the shared cache
imp = cache_getImp(curClass, sel);
if (imp) goto done_unlock;
curClass = curClass->cache.preoptFallbackClass();
#endif
} else {
/** * search the list of methods in the current class, this is important * search algorithm is binary */
Method meth = getMethodNoSuper_nolock(curClass, sel);
if (meth) {
imp = meth->imp(false);
goto done;
}
/** * If the current class is not found, take the methodList that points curClass to superClass * and query the parent until it finds NSObject's parent nil * assign the prepared forward_IMP to IMP * and end the slow lookup process, Next, the Runtime message forwarding mechanism completes the loop loop */
if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
imp = forward_imp;
break; }}// Memory in the class list is corrupted
if (slowpath(--attempts == 0)) {
_objc_fatal("Memory corruption in class list.");
}
// Look it up in the cache of the parent class
imp = cache_getImp(curClass, sel);
// If not found, the default forward_IMP is assigned to imp
if (slowpath(imp == forward_imp)) {
break;
}
// If found
if (fastpath(imp)) {
// Insert the found method into the cache for the next lookup to use the fast cache lookup
gotodone; }}// No implementation was found. Try the method resolver once.
if (slowpath(behavior & LOOKUP_RESOLVER)) {
behavior ^= LOOKUP_RESOLVER;
return resolveMethod_locked(inst, sel, cls, behavior);
}
// find sel imp, load method into 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);
}
done_unlock:
runtimeLock.unlock();
if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
return nil;
}
return imp;
}
Copy the code
Binary lookup process (getMethodNoSuper_nolock)
static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
runtimeLock.assertLocked();
ASSERT(cls->isRealized());
// Get methodList, which may be a two-dimensional array because of the data type
// The loop condition is that the array is not empty, i.e. the start position is not equal to the end position
auto const methods = cls->data()->methods();
for(auto mlists = methods.beginLists(), end = methods.endLists(); mlists ! = end; ++mlists) {// go to search_method_list_inline and fix to an ordered list
method_t *m = search_method_list_inline(*mlists, sel);
if (m) return m;
}
return nil;
}
Copy the code
Fix function (search_method_list_inline)
ALWAYS_INLINE static method_t *
search_method_list_inline(const method_list_t *mlist, SEL sel)
{
int methodListIsFixedUp = mlist->isFixedUp();
int methodListHasExpectedSize = mlist->isExpectedSize();
if (fastpath(methodListIsFixedUp && methodListHasExpectedSize)) {
return findMethodInSortedMethodList(sel, mlist);
} else {
// Linear search of unsorted method list
if (auto *m = findMethodInUnsortedMethodList(sel, mlist))
return m;
}
#if DEBUG
// sanity-check negative results
if (mlist->isFixedUp()) {
for (auto& meth : *mlist) {
if (meth.name() == sel) {
_objc_fatal("linear search worked when binary search did not"); }}}#endif
return nil;
}
Copy the code
Binary search (findMethodInSortedMethodList)
ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
if (list->isSmallList()) {
if (CONFIG_SHARED_CACHE_RELATIVE_DIRECT_SELECTORS && objc::inSharedCache((uintptr_t)list)) {
return findMethodInSortedMethodList(key, list, [](method_t &m) { return m.getSmallNameAsSEL(); });
} else {
return findMethodInSortedMethodList(key, list, [](method_t &m) { returnm.getSmallNameAsSELRef(); }); }}else {
return findMethodInSortedMethodList(key, list, [](method_t &m) { returnm.big().name; }); }}Copy the code
Binary search is really implemented
template<class getNameFunc>
ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)
{
ASSERT(list);
// Start position: 0
auto first = list->begin();
// Base starts with 0
auto base = first;
/ / the probe is 0
decltype(first) probe;
// select sel for imp
uintptr_t keyValue = (uintptr_t)key;
/ / the number of the list
uint32_t count;
/** dichotomy logic works in a lot of places, it can greatly reduce the number of look-ups so let's say we're going to draw numbers from 1 to 10,000 and one of them is a winning number and we're going to draw a lottery and the stupid way to draw is to start at 1 and if you don't get to 2 and so on until the dichotomy is to start at 10,000/2 = 5,000, If you win the lottery and you don't win the lottery, someone will tell you whether your number is too big or too small. If it's too big, the next drawing number will be 0+5000/2 = 2500. If it's too small, the next drawing number will be 5000+5000/2 = 7500. We can save a lot of unnecessary times, quickly draw the big prize, is really a happy thing */
for(count = list->count; count ! =0; count >>= 1) {
probe = base + (count >> 1);
uintptr_t probeValue = (uintptr_t)getName(probe);
if (keyValue == probeValue) {
// Find the first occurrence of the IMP, to avoid the classification method is the same as the main class method problem
// This is why the classification method is loaded
while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
probe--;
}
return &*probe;
}
if (keyValue > probeValue) {
base = probe + 1; count--; }}return nil;
}
Copy the code
- Dichotomy source lottery imitation
auto first = 0;
auto base = first;
decltype(first) probe = 0;
uintptr_t keyValue = 8888;
uint32_t count;
uint32_t current = 1;
for (count = 10000; count ! =0; count >>= 1) {
probe = base + (count >> 1);
NSLog(@" lucky draw % D -- The lucky draw number is % D",current,probe);
if (keyValue == probe) {
NSLog("Congratulations on winning the lottery. The winning number is % D",probe);
break;
}
else{
NSLog("Didn't win!! Keep up the good work.");
}
if (keyValue > probe) {
base = probe + 1;
count--;
}
current += 1;
}
Copy the code
- Lottery results
Slow search processlookUpImpOrForward
Once you find the IMP, you call log_and_fill_cache.
If the logger allows it, the cache’s insert method is called to insert it into the cache, and the next lookup will be a quick cache lookup.
static void log_and_fill_cache(Class cls, IMP imp, SEL sel, id receiver, Class implementer) { #if SUPPORT_MESSAGE_LOGGING if (slowpath(objcMsgLogEnabled && implementer)) { bool cacheIt = logMessageSend(implementer->isMetaClass(), cls->nameForLogging(), implementer->nameForLogging(), sel); if (! cacheIt) return; } #endif cls->cache.insert(sel, imp, receiver); }Copy the code
- LookUpImpOrForward, which is a slow lookup process,
- Search continuously by dichotomy
imp
. - For the global, go first
Shared cache
. - Then look up yours
methodList
If you don’t have one, find oneThe parent class
There is no parent classNSObject
. - NSObject doesn’t, it points to
nil
“And finally jumped out. - General process:
Shared cache
->methodList
->The parent class
->NSObject
->nil
– >Jump out of the loop