The assembly cache cannot be found
In the “OC bottom explore from cache to objc_msgSend” article, we put the search cache assembly process over, assembly process is a quick search process, but has not entered the MissLabelDynamic process, this is slow search process!
And MissLabelDynamic is __objc_msgSend_uncached:
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
Copy the codeMethodTableLookup ();
.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 codeHere some values are stored and _lookUpImpOrForward is called.
Watching TailCallFunctionPointer:
#if __has_feature(ptrauth_calls)
.macro TailCallFunctionPointer
// $0 = function pointer value
braaz $0
.endmacro
#else
.macro TailCallMethodListImp
// $0 = method list imp, $1 = address of method list imp
br $0
.endmacro
#endif
Copy the codeYou see that $0 is returned directly, and $0 is the x17 that was passed in.
So what is x17?
In the methodTable ookup there are:
// IMP in x0
mov x17, x0
Copy the codeSo x17 is x0, and x0 is either the first argument passed in or the result returned.
It is clear that x0 is the result returned by _lookUpImpOrForward!
Two, slow search process preparation
Overview lookUpImpOrForward
NEVER_INLINE
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
const IMP forward_imp = (IMP)_objc_msgForward_impcache;
IMP imp = nil;
Class curClass;
runtimeLock.assertUnlocked();
if(slowpath(! cls->isInitialized())) {// The first message sent to a class is often +new or +alloc, or +self
// which goes through objc_opt_* or various optimized entry points.
//
// However, the class isn't realized/initialized yet at this point,
// and the optimized entry points fall down through objc_msgSend,
// which ends up here.
//
// We really want to avoid caching these, as it can cause IMP caches
// to be made with a single entry forever.
//
// Note that this check is racy as several threads might try to
// message a given class for the first time at the same time,
// in which case we might cache anyway.
behavior |= LOOKUP_NOCACHE;
}
// runtimeLock is held during isRealized and isInitialized checking
// to prevent races against concurrent realization.
// runtimeLock is held during method search to make
// method-lookup + cache-fill atomic with respect to method addition.
// Otherwise, a category could be added but ignored indefinitely because
// the cache was re-filled with the old value after the cache flush on
// behalf of the category.
runtimeLock.lock();
// We don't want people to be able to craft a binary blob that looks like
// a class but really isn't one and do a CFI attack.
//
// To make these harder we want to make sure this is a class that was
// either built into the binary or legitimately registered through
// objc_duplicateClass, objc_initializeClassPair or objc_allocateClassPair.
checkIsKnownClass(cls);
cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
// runtimeLock may have been dropped but is now locked again
runtimeLock.assertLocked();
curClass = cls;
// The code used to lookup the class's cache again right after
// we take the lock but for the vast majority of the cases
// evidence shows this is a miss most of the time, hence a time loss.
//
// The only codepath calling into this without having performed some
// kind of cache lookup is class_getInstanceMethod().
for (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.
Method meth = getMethodNoSuper_nolock(curClass, sel);
if (meth) {
imp = meth->imp(false);
goto done;
}
if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
// No implementation found, and method resolver didn't help.
// Use forwarding.
imp = 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 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.
gotodone; }}// 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 codeThere is a lot of code, but the main purpose of this method is to find imp, see return can also know imp.
Imp is mostly for (unsigned attempts = unreasonableClassCount();) This cycle, in so that you can know this cycle is the focus!
2. Determine initialization
Start from the beginning, first check whether initialization:
if(slowpath(! cls->isInitialized())) { behavior |= LOOKUP_NOCACHE; }Copy the code3. Detection
We then call checkIsKnownClass to check whether the current class is registered in the current cache table:
/***********************************************************************
* checkIsKnownClass
* Checks the given class against the list of all known classes. Dies
* with a fatal error if the class is not known.
* Locking: runtimeLock must be held by the caller.
**********************************************************************/
ALWAYS_INLINE
static void
checkIsKnownClass(Class cls)
{
if(slowpath(! isKnownClass(cls))) { _objc_fatal("Attempt to use unknown class %p.", cls); }}Copy the codeEnter isKnownClass using an intermediate method:
/*********************************************************************** * isKnownClass * Return true if the class is known to the runtime (located within the * shared cache, within the data segment of a loaded image, or has been * allocated with obj_allocateClassPair). * * The result of this operation is cached on the class in a "witness" * value that is cheaply checked in the fastpath. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
ALWAYS_INLINE
static bool
isKnownClass(Class cls)
{
if (fastpath(objc::dataSegmentsRanges.contains(cls->data()->witness, (uintptr_t)cls))) {
return true;
}
auto &set = objc::allocatedClasses.get();
return set.find(cls) ! =set.end() || dataSegmentsContain(cls);
}
Copy the codeGet the table from the allocatedClasses method:
/*********************************************************************** * allocatedClasses * A table of all classes (and metaclasses) which have been allocated * with objc_allocateClassPair. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
namespace objc {
static ExplicitInitDenseSet<Class> allocatedClasses;
}
Copy the code4. Class implementation
Then to the implementation of the class:
cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
Copy the codeAfter a few intermediate methods, I finally get to the realizeClassWithoutSwift method:
/*********************************************************************** * realizeClassWithoutSwift * Performs first-time initialization on class cls, * including allocating its read-write data. * Does not perform any Swift-side initialization. * Returns the real class structure for the class. * Locking: runtimeLock must be write-locked by the caller **********************************************************************/
static Class realizeClassWithoutSwift(Class cls, Class previously)
{
runtimeLock.assertLocked();
class_rw_t *rw;
Class supercls;
Class metacls;
if(! cls)return nil;
if (cls->isRealized()) {
validateAlreadyRealizedClass(cls);
return cls;
}
ASSERT(cls == remapClass(cls));
// fixme verify class is not in an un-dlopened part of the shared cache?
auto ro = (const class_ro_t *)cls->data();
auto isMeta = ro->flags & RO_META;
if (ro->flags & RO_FUTURE) {
// This was a future class. rw data is already allocated.rw = cls->data(); ro = cls->data()->ro(); ASSERT(! isMeta); cls->changeInfo(RW_REALIZED|RW_REALIZING, RW_FUTURE); }else {
// Normal class. Allocate writeable class data.
rw = objc::zalloc<class_rw_t> (); rw->set_ro(ro); rw->flags = RW_REALIZED|RW_REALIZING|isMeta; cls->setData(rw); } cls->cache.initializeToEmptyOrPreoptimizedInDisguise();#if FAST_CACHE_META
if (isMeta) cls->cache.setBit(FAST_CACHE_META);
#endif
// Choose an index for this class.
// Sets cls->instancesRequireRawIsa if indexes no more indexes are available
cls->chooseClassArrayIndex();
if (PrintConnecting) {
_objc_inform("CLASS: realizing class '%s'%s %p %p #%u %s%s",
cls->nameForLogging(), isMeta ? " (meta)" : "",
(void*)cls, ro, cls->classArrayIndex(),
cls->isSwiftStable() ? "(swift)" : "",
cls->isSwiftLegacy() ? "(pre-stable swift)" : "");
}
// Realize superclass and metaclass, if they aren't already.
// This needs to be done after RW_REALIZED is set above, for root classes.
// This needs to be done after class index is chosen, for root metaclasses.
// This assumes that none of those classes have Swift contents,
// or that Swift's initializers have already been called.
// fixme that assumption will be wrong if we add support
// for ObjC subclasses of Swift classes.
supercls = realizeClassWithoutSwift(remapClass(cls->getSuperclass()), nil);
metacls = realizeClassWithoutSwift(remapClass(cls->ISA()), nil);
#if SUPPORT_NONPOINTER_ISA
if (isMeta) {
// Metaclasses do not need any features from non pointer ISA
// This allows for a faspath for classes in objc_retain/objc_release.
cls->setInstancesRequireRawIsa();
} else {
// Disable non-pointer isa for some classes and/or platforms.
// Set instancesRequireRawIsa.
bool instancesRequireRawIsa = cls->instancesRequireRawIsa();
bool rawIsaIsInherited = false;
static bool hackedDispatch = false;
if (DisableNonpointerIsa) {
// Non-pointer isa disabled by environment or app SDK version
instancesRequireRawIsa = true;
}
else if(! hackedDispatch &&0= =strcmp(ro->getName(), "OS_object"))
{
// hack for libdispatch et al - isa also acts as vtable pointer
hackedDispatch = true;
instancesRequireRawIsa = true;
}
else if (supercls && supercls->getSuperclass() &&
supercls->instancesRequireRawIsa())
{
// This is also propagated by addSubclass()
// but nonpointer isa setup needs it earlier.
// Special case: instancesRequireRawIsa does not propagate
// from root class to root metaclass
instancesRequireRawIsa = true;
rawIsaIsInherited = true;
}
if(instancesRequireRawIsa) { cls->setInstancesRequireRawIsaRecursively(rawIsaIsInherited); }}// SUPPORT_NONPOINTER_ISA
#endif
// Update superclass and metaclass in case of remapping
cls->setSuperclass(supercls);
cls->initClassIsa(metacls);
// Reconcile instance variable offsets / layout.
// This may reallocate class_ro_t, updating our ro variable.
if(supercls && ! isMeta) reconcileInstanceVariables(cls, supercls, ro);// Set fastInstanceSize if it wasn't set already.
cls->setInstanceSize(ro->instanceSize);
// Copy some flags from ro to rw
if (ro->flags & RO_HAS_CXX_STRUCTORS) {
cls->setHasCxxDtor();
if(! (ro->flags & RO_HAS_CXX_DTOR_ONLY)) { cls->setHasCxxCtor(); }}// Propagate the associated objects forbidden flag from ro or from
// the superclass.
if ((ro->flags & RO_FORBIDS_ASSOCIATED_OBJECTS) ||
(supercls && supercls->forbidsAssociatedObjects()))
{
rw->flags |= RW_FORBIDS_ASSOCIATED_OBJECTS;
}
// Connect this class to its superclass's subclass lists
if (supercls) {
addSubclass(supercls, cls);
} else {
addRootClass(cls);
}
// Attach categories
methodizeClass(cls, previously);
return cls;
}
Copy the codeFirst, rW, RO assignments, that is, property lists, method lists, and so on.
Then implement metaclass and superclass:
supercls = realizeClassWithoutSwift(remapClass(cls->getSuperclass()), nil);
metacls = realizeClassWithoutSwift(remapClass(cls->ISA()), nil);
Copy the codeThis is a recursive call.
Then assign the metaclass and superclass to the current class:
// Update superclass and metaclass in case of remapping
cls->setSuperclass(supercls);
cls->initClassIsa(metacls);
Copy the codeIt is in this recursive call isa bitmap all related classes are implemented!
Why implement all related classes?
Because to find a way!
Object method if the current class can not find the method need to look in the parent class!
If the isa of the current class cannot find the method, you need to look for the parent class isa.
That’s all for the for loop!
Three, binary search process
In our general understanding, find object methods:
1. Look for sel and IMP in methodList.
2. If you can’t find it, look in the parent class, look in NSObject, and get nil.
And then we’ll see if that’s the case.
For (unsigned attempts = unreasonableClassCount(); Cycle, found this is a dead cycle!
Only break or goto can break out of the loop!
The first judgment that comes in:
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
}
Copy the codeHere is to go to the shared cache inside the search! The shared cache is usually a storage system method, and our method is usually not in the shared cache.
Go straight to else:
else {
// curClass method list.
Method meth = getMethodNoSuper_nolock(curClass, sel);
if (meth) {
imp = meth->imp(false);
goto done;
}
if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
// No implementation found, and method resolver didn't help.
// Use forwarding.
imp = forward_imp;
break; }}Copy the codeFirst call getMethodNoSuper_nolock to get the list of methods:
/*********************************************************************** * getMethodNoSuper_nolock * fixme * Locking: runtimeLock must be read- or write-locked by the caller * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
runtimeLock.assertLocked();
ASSERT(cls->isRealized());
// fixme nil cls?
// fixme nil sel?
auto const methods = cls->data()->methods();
for (automlists = methods.beginLists(), end = methods.endLists(); mlists ! = end; ++mlists) {// <rdar://problem/46904873> getMethodNoSuper_nolock is the hottest
// caller of search_method_list, inlining it turns
// getMethodNoSuper_nolock into a frame-less function and eliminates
// any store from this codepath.
method_t *m = search_method_list_inline(*mlists, sel);
if (m) return m;
}
return nil;
}
Copy the codeThe list of methods was first obtained through CLS ->data()-> Methods (), and explored in the article “Underlying Principle Structure of OC Underlying Exploration”.
We then call search_method_list_inline to retrieve method method_t by iterating through the list of methods:
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 codeThen enter the findMethodInSortedMethodList lookup list by using the method of sorted:
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 codeSmallList or BigList.
BigList is one of the traditional computer, so see the else, first enter the findMethodInSortedMethodList:
/*********************************************************************** * 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;
for (count = list->count; count ! =0; count >>= 1) {
probe = base + (count >> 1);
uintptr_t probeValue = (uintptr_t)getName(probe);
if (keyValue == probeValue) {
// `probe` is a match.
// Rewind looking for the *first* occurrence of this value.
// This is required for correct category overrides.
while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
probe--;
}
return &*probe;
}
if (keyValue > probeValue) {
base = probe + 1; count--; }}return nil;
}
Copy the codeSo let’s look at the for loop, and each time we go through the loop, we move 1 bit to the right, which is essentially dividing by 2!
Then look inside the loop:
Probe is set to base + (count >> 1). Base is the starting position, which is 0, so probe is count / 2.
Then take the name of probe, that is, SEL, and compare the sel to be searched with the current SEL. If it is the same and Probe is larger than the starting position, let the SEL to be searched continue to compare the next SEL. If it is the same, probe–, until it cannot find the same method as the SEL to be searched. Return probe’s address at last!
Why compare the next name? Because there may be times when object methods and classification methods have the same name!
If not, compare the size. If the SEL to be searched is larger than the current SEL, it means that the SEL to be searched is in the back, otherwise it is in the front!
Base is set to probe + 1, count–, and the loop continues.
Slow search recursive process
1. Check the method
When you find method_t in the dichotomy, jump to done:
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 codeExecute the fill cache method log_and_fill_cache:
/***********************************************************************
* log_and_fill_cache
* Log this method call. If the logger permits it, fill the method cache.
* cls is the method whose cache should be filled.
* implementer is the class that owns the implementation in question.
**********************************************************************/
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 codeFinally, the familiar insert function!
2. Go to the parent class
Slowpath ((curClass = curClass->getSuperclass()) == nil)) slowPath ((curClass = curClass->getSuperclass()) == nil)) When is it nil? NSObject’s parent is nil! Explain to have checked all the parent class here, did not check! Then the message forwarding process will begin!
If there is still a parent class, start looking in the parent class:
// Superclass cache.
imp = cache_getImp(curClass, sel);
Copy the codeTo enter cache_getImp:
// returns:
// - the cached IMP when one is found
// - nil if there's no cached value and the cache is dynamic
// - `value_on_constant_cache_miss` if there's no cached value and the cache is preoptimized
extern "C" IMP cache_getImp(Class cls, SEL sel, IMP value_on_constant_cache_miss = nil);
Copy the codeFound no follow-up!
Global search cache_getImp:
STATIC_ENTRY _cache_getImp
GetClassFromIsa_p16 p0, 0
CacheLookup GETIMP, _cache_getImp, LGetImpMissDynamic, LGetImpMissConstant
Copy the codeFound that this is our previous assembly lookup cache flow, namely quick lookup flow!
After the current class can not find a method, go to the parent class for a quick search process, find the method in the cache!
But the parameters passed in are different from what we saw before. Now the Mode passed in is GETIMP and MissLabelDynamic is LGetImpMissDynamic!
After finding a way into the CacheHit cache:
.elseif $0 == GETIMP
mov p0, p17
cbz p0, 9f // don't ptrauth a nil imp
AuthAndResignAsIMP x0, x10, x1, x16 // authenticate imp and re-sign as IMP
9: ret // return IMP
//-- AuthAndResignAsIMP--
.macro AuthAndResignAsIMP
// $0 = cached imp, $1 = address of cached imp, $2 = SEL
eor $0, $0, $3
.endmacro
Copy the codeIf IMP is nil, return nil directly; If IMP is not nil, return IMP after decoding!
If not, go to __objc_msgSend_uncached and then _lookUpImpOrForward!
Instead, enter LGetImpMissDynamic:
LGetImpMissDynamic:
mov p0, #0
ret
Copy the codeIf you can’t find it, return nil!
So in the loop of the slow lookup process:
If a method is found in the parent class, go to done and cache it.
If no method is found in the parent class, continue the loop for a slow lookup!
3. Method resolution
If you break out of the loop, you enter method resolution resolveMethod_locked!
