mikeash.com: just this guy, you know?

Posted at 2009-01-23 21:31 | RSS feed (Full text feed) | Blog Index
Next article: Friday Q&A 2009-01-30: Code Injection
Previous article: Friday Q&A 2009-01-16
Tags: fridayqna kvo
Friday Q&A 2009-01-23
by Mike Ash  

Welcome to the first Friday Q&A; of the new Presidential administration. Unlike Mr. Obama, I'm afraid of change and so this week's edition will be just like all the other ones. This week I'll be taking Jonathan Mitchell's suggestion to talk about how Key-Value Observing (KVO) is actually implemented at the runtime level.

What Is It?
Most readers probably know this already, but just for a quick recap: KVO is the technology that underlies Cocoa Bindings, and it provides a way for objects to get notified when the properties of other objects are changed. One object observes a key of another object. When the observed object changes the value of that key, the observer gets notified. Pretty straightforward, right? The tricky part is that KVO operates with no code needed in the object being observed... usually.

Overview
So how does that work, not needing any code in the observed object? Well it all happens through the power of the Objective-C runtime. When you observe an object of a particular class for the first time, the KVO infrastructure creates a brand new class at runtime that subclasses your class. In that new class, it overrides the set methods for any observed keys. It then switches out the isa pointer of your object (the pointer that tells the Objective-C runtime what kind of object a particular blob of memory actually is) so that your object magically becomes an instance of this new class.

The overridden methods are how it does the real work of notifying observers. The logic goes that changes to a key have to go through that key's set method. It overrides that set method so that it can intercept it and post notifications to observers whenever it gets called. (Of course it's possible to make a modification without going through the set method if you modify the instance variable directly. KVO requires that compliant classes must either not do this, or must wrap direct ivar access in manual notification calls.)

It gets trickier though: Apple really doesn't want this machinery to be exposed. In addition to setters, the dynamic subclass also overrides the -class method to lie to you and return the original class! If you don't look too closely, the KVO-mutated objects look just like their non-observed counterparts.

Digging Deeper
Enough talk, let's actually see how all of this works. I wrote a program that illustrates the principles behind KVO. Because of the dynamic KVO subclass tries to hide its own existence, I mainly use Objective-C runtime calls to get the information we're looking for.

Here's the program:

    // gcc -o kvoexplorer -framework Foundation kvoexplorer.m
    
    #import <Foundation/Foundation.h>
    #import <objc/runtime.h>
    
    
    @interface TestClass : NSObject
    {
        int x;
        int y;
        int z;
    }
    @property int x;
    @property int y;
    @property int z;
    @end
    @implementation TestClass
    @synthesize x, y, z;
    @end
    
    static NSArray *ClassMethodNames(Class c)
    {
        NSMutableArray *array = [NSMutableArray array];
        
        unsigned int methodCount = 0;
        Method *methodList = class_copyMethodList(c, &methodCount);
        unsigned int i;
        for(i = 0; i < methodCount; i++)
            [array addObject: NSStringFromSelector(method_getName(methodList[i]))];
        free(methodList);
        
        return array;
    }
    
    static void PrintDescription(NSString *name, id obj)
    {
        NSString *str = [NSString stringWithFormat:
            @"%@: %@\n\tNSObject class %s\n\tlibobjc class %s\n\timplements methods <%@>",
            name,
            obj,
            class_getName([obj class]),
            class_getName(obj->isa),
            [ClassMethodNames(obj->isa) componentsJoinedByString:@", "]];
        printf("%s\n", [str UTF8String]);
    }
    
    int main(int argc, char **argv)
    {
        [NSAutoreleasePool new];
        
        TestClass *x = [[TestClass alloc] init];
        TestClass *y = [[TestClass alloc] init];
        TestClass *xy = [[TestClass alloc] init];
        TestClass *control = [[TestClass alloc] init];
        
        [x addObserver:x forKeyPath:@"x" options:0 context:NULL];
        [xy addObserver:xy forKeyPath:@"x" options:0 context:NULL];
        [y addObserver:y forKeyPath:@"y" options:0 context:NULL];
        [xy addObserver:xy forKeyPath:@"y" options:0 context:NULL];
        
        PrintDescription(@"control", control);
        PrintDescription(@"x", x);
        PrintDescription(@"y", y);
        PrintDescription(@"xy", xy);
        
        printf("Using NSObject methods, normal setX: is %p, overridden setX: is %p\n",
              [control methodForSelector:@selector(setX:)],
              [x methodForSelector:@selector(setX:)]);
        printf("Using libobjc functions, normal setX: is %p, overridden setX: is %p\n",
              method_getImplementation(class_getInstanceMethod(object_getClass(control),
                                       @selector(setX:))),
              method_getImplementation(class_getInstanceMethod(object_getClass(x),
                                       @selector(setX:))));
        
        return 0;
    }
Let's walk through it, top to bottom.

First we define a class called TestClass which has three properties. (KVO works on non-@property keys too but this is the simplest way to define pairs of setters and getters.)

Next we define a pair of utility functions. ClassMethodNames uses Objective-C runtime functions to go through a class and get a list of all the methods it implements. Note that it only gets methods implemented directly in that class, not in superclasses. PrintDescription prints a full description of the object passed to it, showing the object's class as obtained through the -class method as well as through an Objective-C runtime function, and the methods implemented on that class.

Then we start experimenting using those facilities. We create four instances of TestClass, each of which will be observed in a different way. The x instance will have an observer on its x key, similar for y, and xy will get both. The z key is left unobserved for comparison purposes. And lastly the control instance serves as a control on the experiment and will not be observed at all.

Next we print out the description of all four objects.

After that we dig a little deeper into the overridden setter and print out the address of the implementation of the -setX: method on the control object and an observed object to compare. And we do this twice, because using -methodForSelector: fails to show the override. KVO's attempt to hide the dynamic subclass even hides the overridden method with this technique! But of course using Objective-C runtime functions instead provides the proper result.

Running the Code
So that's what it does, now let's look at a sample run:

    control: <TestClass: 0x104b20>
        NSObject class TestClass
        libobjc class TestClass
        implements methods <setX:, x, setY:, y, setZ:, z>
    x: <TestClass: 0x103280>
        NSObject class TestClass
        libobjc class NSKVONotifying_TestClass
        implements methods <setY:, setX:, class, dealloc, _isKVOA>
    y: <TestClass: 0x104b00>
        NSObject class TestClass
        libobjc class NSKVONotifying_TestClass
        implements methods <setY:, setX:, class, dealloc, _isKVOA>
    xy: <TestClass: 0x104b10>
        NSObject class TestClass
        libobjc class NSKVONotifying_TestClass
        implements methods <setY:, setX:, class, dealloc, _isKVOA>
    Using NSObject methods, normal setX: is 0x195e, overridden setX: is 0x195e
    Using libobjc functions, normal setX: is 0x195e, overridden setX: is 0x96a1a550
First it prints our control object. As expected, its class is TestClass and it implements the six methods we synthesized from the class's properties.

Next it prints the three observed objects. Note that while -class is still showing TestClass, using object_getClass shows the true face of this object: it's an instance of NSKVONotifying_TestClass. There's your dynamic subclass!

Notice how it implements the two observed setters. This is interesting because you'll note that it's smart enough not to override -setZ: even though that's also a setter, because nobody has observed it. Presumably if we were to add an observer to z as well, then NSKVONotifying_TestClass would suddenly sprout a -setZ: override. But also note that it's the same class for all three instances, meaning they all have overrides for both setters, even though two of them only have one observed property. This costs some efficiency due to passing through the observed setter even for a non-observed property, but Apple apparently thought it was better not to have a proliferation of dynamic subclasses if each object had a different set of keys being observed, and I think that was the correct choice.

And you'll also notice three other methods. There's the overridden -class method as mentioned before, the one that tries to hide the existence of this dynamic subclass. There's a -dealloc method to handle cleanup. And there's a mysterious -_isKVOA method which looks to be a private method that Apple code can use to determine if an object is being subject to this dynamic subclassing.

Next we print out the implementation for -setX:. Using -methodForSelector: returns the same value for both. Since there is no override for this method in the dynamic subclass, this must mean that -methodForSelector: uses -class as part of its internal workings and is getting the wrong answer due to that.

So of course we bypass that altogether and use the Objective-C runtime to print the implementations instead, and here we can see the difference. The original agrees with -methodForSelector: (as of course it should), but the second is completely different.

Being good explorers, we're running in the debugger and so can see exactly what this second function actually is:

    (gdb) print (IMP)0x96a1a550
    $1 = (IMP) 0x96a1a550 <_NSSetIntValueAndNotify>
It's some sort of private function that implements the observer notification. By using nm -a on Foundation we can get a complete listing of all of these private functions:
    0013df80 t __NSSetBoolValueAndNotify
    000a0480 t __NSSetCharValueAndNotify
    0013e120 t __NSSetDoubleValueAndNotify
    0013e1f0 t __NSSetFloatValueAndNotify
    000e3550 t __NSSetIntValueAndNotify
    0013e390 t __NSSetLongLongValueAndNotify
    0013e2c0 t __NSSetLongValueAndNotify
    00089df0 t __NSSetObjectValueAndNotify
    0013e6f0 t __NSSetPointValueAndNotify
    0013e7d0 t __NSSetRangeValueAndNotify
    0013e8b0 t __NSSetRectValueAndNotify
    0013e550 t __NSSetShortValueAndNotify
    0008ab20 t __NSSetSizeValueAndNotify
    0013e050 t __NSSetUnsignedCharValueAndNotify
    0009fcd0 t __NSSetUnsignedIntValueAndNotify
    0013e470 t __NSSetUnsignedLongLongValueAndNotify
    0009fc00 t __NSSetUnsignedLongValueAndNotify
    0013e620 t __NSSetUnsignedShortValueAndNotify
There are some interesting things to be found in this list. First, you'll notice that Apple has to implement a separate function for every primitive type that they want to support. They only need one for Objective-C objects (_NSSetObjectValueAndNotify) but they need a whole host of functions for the rest. And that host is kind of incomplete: there's no function for long double or _Bool. There isn't even one for a generic pointer type, such as you'd get if you had a CFTypeRef property. And while there are several functions for various common Cocoa structs, there obviously aren't any for the huge universe of other structs out there. This means that any properties of these types will simply be ineligible for automatic KVO notification, so beware!

KVO is a powerful technology, sometimes a little too powerful, especially when automatic notification is involved. Now you know exactly how it all works on the inside and this knowledge may help you decide how to use it or to debug it when it goes wrong.

If you plan to use KVO in your own application you may want to check out my article on Key-Value Observing Done Right.

Wrapping Up
That's it for this week. Will Mike face down the terrifying code monster? Will his IDE finish compiling in time? Tune in next week for another exciting installment! In the meantime, post your thoughts below.

And as a reminder, Friday Q&A; is run by your generous donations. No, not money, just ideas! If you have a topic you would like to see discussed here, post it in the comments or e-mail it directly. (Your name will be used unless you ask me not to.)

Did you enjoy this article? I'm selling whole books full of them! Volumes II and III are now out! They're available as ePub, PDF, print, and on iBooks and Kindle. Click here for more information.

Comments:

At least according to the Leopard Foundation Release Notes, KVO does now support arbitrary types. So something else must be going on in that case. Automatic boxing in NSValue maybe?

http://developer.apple.com/ReleaseNotes/Cocoa/Foundation.html
So, I modified your code to perform some KVO on a struct and the resulting selector for the overridden structure setter that I'm getting back is confounding me:


(gdb) p (IMP)0x90bca9a0
$1 = (IMP) 0x90bca9a0 <__forwarding_prep_0___>

That'll teach me to make such assertions without testing them! Thanks for correcting me. I modified my code and tested it out and, you're right, KVO notifications are generated even for custom structs.

The __forwarding_prep_0___ function is part of the -forwardInvocation: machinery. It appears that KVO uses the NSInvocation support to package up the parameters being passed in. This allows it to support any type that the forwarding machinery can understand, which should be everything. Presumably the fixed functions that can be found in Foundation exist as an optimization for common types, with the forwarding stuff as a backup for everything else.

Thanks, I learned something!
One thing that is not clear is where are the references to the observers stored?

The observed instance must store these somewhere, and NsObject has no ivars for this

I haven't actually looked at the real implementation, but I assume that there is a global table somewhere which maps instances to observer info. The KVO subclass would actually be a good place to store such a table, too.
Yes, the global table could be how it's done. It just doesn't sound very elegant.

As for the KVO subclass, how would it provide any storage?
You are creating these classes dynamically, and there are no "class variables" in Objective-C. Even if there were, this would be a similar solution to the global table since these dynamic subclasses are reused for all observed instances.

Also, declaring an instance variable on this new dynamic class would not work because the object instance being observed is already created (only the isa pointer is changed) and thus would require reallocating the object.

The language doesn't support class variables, but the runtime does. You can allocate storage for them with the extraBytes parameter to objc_allocateClassPair. I believe they can be accessed with object_getIndexedIvars. KVO uses this for something, although I don't know what, as my only familiarity with it is watching it crash after pulling isa-swizzling shenanigans on KVO-occupied objects.
Didn't know that. Having a per class table sounds better than a global table.

I guess one would have to have access to the code to be sure on how it is really done. :)

Terrific post nonetheless.
Thanks for the article! I know it's been around for a long while, but...

Did you mean to have the ;); below, or do you have an extra semicolon?

        Method *methodList = class_copyMethodList(c, &methodCount;);
That's called "when entities attack". Fixed now, thanks.
Sorry for the late revival of this old article, but here's my observation (no pun intended): so basically, if back in 2009 you used -[NSObject methodForSelector:] for obtaining a setter method, then calls to that setter wouldn't have shown up in KVO?

It seems to me that it is indeed the case, but unfortunately I can't reproduce it (methodForSelector: now returns the modified setter…)
Without actually testing to find out, I think that whether methodForSelector: works depends on when you call it. If you call it on an object that has already had its class swizzled, you'll get the KVO-aware shim setter and all will be well. If you call it on a virgin object, you'll get the naive setter that doesn't invoke KVO. I don't think this would have changed.
I found what Xcode is tricky cheater. When I'm creating subclass with prefix "NSKVONotifying_" and override class method - it looks like you described and only runtime tells us what it's the our lying class.

But when I name prefix with another string, for example "NSKVONotifyingA_", Xcode shows in debugger real name "NSKVONotifyingA_TestObject". However myObj.class returns his superclass "TestObject", as expected. I tried create classes in code, at runtime, etc – but result is the same – Xcode shows real class name. Looks like they use object_getClass call and have exception for KVO prefix.
Thanks for your post.It helped me a lot to dig deeper into KVO, although it's written 8 years ago.But I found a typo from your comment which replied to Ashley Clark about custom structs.As you said, apple do some forwarding stuff for those custom structs.But it's forwarded by -forwardingTargetForSelector not -forwardInvocation.That's different.
Some dogs don't know when to get old and die.

             Note that when observing deep keypaths such as obs observes xy.brain.structure.name the registered observer for structure (0x100600600) is not the original observer (obs) but a NSKeyValueObservance instance associated with obs.


             obs : 0x100400170
             obs.xy : 0x100400d10
             obs.xy : <NSKeyValueObservationInfo 0x100500ca0> (
             <NSKeyValueObservance 0x1003041e0: Observer: 0x100400170, Key path: x, Options: <New: NO, Old: NO, Prior: NO> Context: 0x0, Property: 0x1004012c0>
             <NSKeyValueObservance 0x100306320: Observer: 0x100400170, Key path: y, Options: <New: NO, Old: NO, Prior: NO> Context: 0x0, Property: 0x100306350>
             <NSKeyValueObservance 0x100401140: Observer: 0x100400170, Key path: brain.name, Options: <New: YES, Old: YES, Prior: NO> Context: 0x0, Property: 0x100401890>
             <NSKeyValueObservance 0x100600000: Observer: 0x100400170, Key path: brain.structure.name, Options: <New: YES, Old: YES, Prior: NO> Context: 0x0, Property: 0x1004041e0>
             )
             obs.xy.brain : <NSKeyValueObservationInfo 0x103800370> (
             <NSKeyValueObservance 0x100600600: Observer: 0x100600000, Key path: structure.name, Options: <New: YES, Old: YES, Prior: NO> Context: 0x0, Property: 0x100500dd0>
             <NSKeyValueObservance 0x103800340: Observer: 0x100401140, Key path: name, Options: <New: YES, Old: YES, Prior: NO> Context: 0x0, Property: 0x100402d20>
             )
             obs.xy.brain.structure : <NSKeyValueObservationInfo 0x100600690> (
             <NSKeyValueObservance 0x100600660: Observer: 0x100600600, Key path: name, Options: <New: YES, Old: YES, Prior: NO> Context: 0x0, Property: 0x1005011f0>
             )
I am a new bee in Objective-C and really appreciated to your article, it given me a lot of help. I already knew how to use nm -a command to kvoexplorer.o file. But I have no idea to how to use nm -a to Foundation. Thanks!
Thanks a lot for sharing the internals of KVO!!
I have a though on an alternate approach and would like to now if that would be achievable.
KVO could also be implemented by swapping the original setter with a custom setter that calls the observers with the new value and then calls the original setter. Would that also be a possibility to implement this feature?

Comments RSS feed for this page

Add your thoughts, post a comment:

Spam and off-topic posts will be deleted without notice. Culprits may be publicly humiliated at my sole discretion.

Name:
The Answer to the Ultimate Question of Life, the Universe, and Everything?
Comment:
Formatting: <i> <b> <blockquote> <code>.
NOTE: Due to an increase in spam, URLs are forbidden! Please provide search terms or fragment your URLs so they don't look like URLs.
Code syntax highlighting thanks to Pygments.
Hosted at DigitalOcean.