Small valley bottom exploration collection

  • Everybody knowsobjc_msgSendCore method through assembly, assembly lookup cache is fast lookup, today we understand a wave of slow lookup!

1. Locate the search core method

Without further ado, code:

@interface XGTest : NSObject
- (void)say5;
@end

@implementation XGTest
@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        
        XGTest *test = [XGTest alloc];
        [test say5];
    }
    return 0;
}
Copy the code
    1. Our test today is to call a method that is not implementedsay5“So you can watch him go through the process more closely! (If the method is implemented and can be found, then our process research is not careful enough!)
    1. Let’s look at the assembly and see how it finds methods!

    1. Then after the break, we look at the assembly (the operation method is shown in figure)

    1. We’ll follow.

    1. And so we found our methodlookUpImpOrForward

2. LookUpImpOrForward analysis

Same old rule — code

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();

    // Optimistic cache lookup
    if (fastpath(behavior & LOOKUP_CACHE)) {
        imp = cache_getImp(cls, sel);
        if (imp) goto done_nolock;
    }

    // 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);

    if(slowpath(! cls->isRealized())) { cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);// runtimeLock may have been dropped but is now locked again
    }

    if(slowpath((behavior & LOOKUP_INITIALIZE) && ! cls->isInitialized())) { cls = initializeAndLeaveLocked(cls, inst, runtimeLock);// runtimeLock may have been dropped but is now locked again

        // If sel == initialize, class_initialize will send +initialize and 
        // then the messenger will send +initialize again after this 
        // procedure finishes. Of course, if this is not being called 
        // from the messenger then it won't happen. 2778172
    }

    runtimeLock.assertLocked();
    curClass = cls;

    // The code used to lookpu 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();;) {
        // curClass method list.
        Method meth = getMethodNoSuper_nolock(curClass, sel);
        if (meth) {
            imp = meth->imp(false);
            goto done;
        }

        if (slowpath((curClass = curClass->superclass) == 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:
    log_and_fill_cache(cls, imp, sel, inst, curClass);
    runtimeLock.unlock();
 done_nolock:
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
    return imp;
}
Copy the code

2.1. General analysis of a wave

    1. This code eventually returnsimpHis core idea was to find himimp
    1. Let’s take a quick look at the code: first, assign the definitionforward_impAnd then decide whether to look it up in the cache. And then went to for!
    1. You see thisThe for loopDon’t panic, the back condition is not written, then he is a default loop, can only passbreakorgotoJump out

We can start with a general understanding of the process and then slowly analyze

  • Let me take a look at the picture above.

    1. I use putonghua to express a wave (😆) : the general process is now their own list to find, find out jump out, find not to hisSuperclass (superclass)Look, I found itdoneCan’t find continue until foundNSObjectIf you still can’t find it, assign itforward_imp

2.2. Specific analysis

So, we carefully study, the specific code is how to achieve!!

    1. Gets the code for the method
Method meth = getMethodNoSuper_nolock(curClass, sel);
Copy the code

Let’s see how he does it:

    1. Okay, I finally figured out how he did it!
ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
    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)probe->name();
        
        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)(probe - 1)->name()) {
                probe--;
            }
            return &*probe;
        }
        
        if (keyValue > probeValue) {
            base = probe + 1; count--; }}return nil;
}
Copy the code

Isn’t the core idea a binary search (binary search or fast)

Count >>= 1, : count = count>>1 (0000 1000 –> 0000 0100:8 –> 4)

It’s just count = count/2, but it’s just the bitwise operator they use.

    1. At this point, you need a wave of binary search

    1. Let’s go ahead and look at the code.
imp = cache_getImp(curClass, sel);
Copy the code

Let’s look at the parameters inside:This is already pointing to hissuperclassthe

    1. So let’s seecache_getImp

No longer available ~ (this time we will think, will be assembly processing. Let’s do a global search.

    1. assembly_cache_getImp
	 STATIC_ENTRY _cache_getImp

     GetClassFromIsa_p16 p0
     CacheLookup GETIMP, _cache_getImp
Copy the code

Combined with the assembly code, we can see that the cache will be found from the parent class. If not, ret(return) is used, so cache_getImp does not go recursively, but rather iterates through the inheritance chain through an infinite loop of for

    1. That’s pretty much it for loopsThen keep looking at the picture

Method search process almost finished ~(after all, my level is limited, may not be detailed, I hope brothers grace, 😆)

3. Summary of slow search process

For slow search, I drew a simple flow chart ~ (MY art level is so low, don’t laugh at me)