News
Type Dependent Dispatch
Posted on 1 September 2010 by
Every language contains some painfully stupid design decisions and Objective-C is no exception. The one that I find the most irritating is the definition of a selector. Selectors are an abstraction of method identifiers. In the original StepStone compiler, and with the NeXT and Apple runtimes, these are represented by uniqued strings.
This representation was inherited from Smalltalk. In Smalltalk, it made sense. Every method was uniquely identified by a string. Every method returned an object (self if no explicit return was specified) and took objects as arguments.
Unfortunately, Objective-C inherited the C structural type system as well as the Smalltalk algebraic type system. This means that methods have a name and a set of parameter types, but selectors don't. To give you some idea of why this is a problem, consider this trivial program:
#import <Foundation/Foundation.h>
@interface A : NSObject
- (void)foo: (int)a;
@end
@interface B : A
- (void)foo: (float)a;
@end
@implementation A
- (void)foo: (int)a
{
printf("int: %d\n", a);
}
@end
@implementation B : A
- (void)foo: (float)a
{
printf("float: %f", a);
}
@end
int main(void)
{
A *a = [A new];
B *b = [B new];
[a foo: 12];
[b foo: 12];
a = b;
[a foo: 12];
return 0;
}
If you compile this - with GCC or clang - on OS X, it gives no errors, no warnings. When you run it, you get this output:
int: 12
float: 12.000000
float: 0.000000
The first two look sensible. The correct method is being called with the correct parameter. What about the third one? Whether the correct method is being called depends on how you interpret the Objective-C language, but the parameter is definitely wrong.
Why does this happen? The answer is quite simple. The compiler needs to know the types of the method to be able to construct the call frame correctly. You've told it that the receiver is an instance of class A, so it looks up the method in this class and finds the one that takes an integer as an argument. It therefore puts 12 into an integer register.
The called method, however, expects a float and so it looks in the first floating point register to find it. Nothing has touched these since the program started, so it finds 0. In this case, the result is quite benign. The program does the wrong thing, but not catastrophically. If one of the arguments had been a structure, or they differed in return types, you might have the program dereferencing an invalid pointer or simply corrupting the stack. Because this can lead to stack corruption, it has the potential to expose some fun security holes in any Objective-C program using an implementation that inherits this behaviour.
The problem here is that the compiler is making certain assumptions, but is not enforcing a check at run time that they are correct. When they are not, bad things happen.
This looks like a fairly contrived example, but it's actually relatively common. Remember that methods in Objective-C do not have to be declared publicly. If -foo: in A was not in the interface, someone might easily create a definition of B as a subclass of A which added a new -foo: method with a different set of types. They might then pass a pointer to an instance of B to something expecting an instance of A (which, after all, is one of the things that inheritance is meant to let you do). This object might then send a -foo: message to the object it receives and suddenly the stack is corrupted.
With libobjc2, I've been working on a solution to this, which is now working correctly. Before I explain how it works, a little bit of background:
The GNUstep runtime (libobjc2) is designed to be a drop-in replacement for the old GNU runtime. The GNU runtime did not copy this design decision. Selectors in the GNU runtime contain both a name and a type encoding. This was done to make distributed objects faster - the caller knows the types of the method (in theory, at least), so you don't need a round-trip over the network to look them up. Unfortunately, for compatibility with NeXT, the types were not used for message lookup.
The latest version of libobjc2 now supports type dependent dispatch. With this enabled (it isn't by default, but it will be soon), the types are also used for message lookup. This means that, when we run the example program, we get this output:
int: 12
float: 12.000000
int: 12
The method that has a different type signature does not override the old one. This interoperates with old code safely too - if you call a method using a selector with no type encoding, it looks up the same method that the old runtime would return. This change does not require any modification to the ABI - you can still use it with code compiled with GCC, targeting the old GNU runtime.
Currently, if you call a method with an incorrect signature, it logs a warning. I've fixed a few subtle bugs in Étoilé and GNUstep that this has uncovered. The next thing on my TODO list is to add a callback that runs whenever the lookup returns mismatched selector types. This will allow us to do some very clever things with LanguageKit. For example, we can dynamically fix up these errors at run time by adding a method to the class that performs auto boxing or unboxing and then calls the correct method.
It's also worth noting that, when the types don't match, this uses the same lookup mechanism as type-independent dispatch. Methods are still looked up as a single sparse array lookup with the selector as the index. There is a slight space penalty, because both the typed and untyped version of the selector are added to the dispatch table as keys whenever a method is added, and registering selectors is slightly more expensive, but that's all.
