Tony Finch – blog

Between returning from San Francisco and getting my job at the University, I did some FreeBSD-related things. One of its features which captured my interest was its kernel object system, kobj. This was designed to make the driver ABI more dynamic so that modules compiled against older source could be loaded into newer kernels and still work. The problem is that if a driver call is changed, you don't want to have to add compatibility tests to every call point in the kernel. FreeBSD uses kobj to solve this problem by making drivers into classes (such that each object of the class represents a device controlled by the driver) so that driver calls become method calls. What caught my interest is that the method calls are much more dynamic than I was used to from languages like C++.

C++ does method lookup using an array of method pointers called a vtbl. The static type of the object determines the layout of the vtbl, i.e. which method pointer is at which index in the table. (The dynamic type of the object may be a derived type of its static type, in which case the vtbl contains more entries than are determined by the static type.) A method call object.method(args) compiles to object.vtbl[method_index](args). This is no good for our problem because any change to a class's methods changes its ABI and means that old code will no longer work.

In kobj, the method lookup table is a cache, so that method lookups are fast in the normal case, but fall back to a more complicated dynamic lookup if there is a cache miss. This means that if a new method is called against an old object then the lookup code can return a pointer to a compatibility shim method instead of one of the methods defined by the object's class. I'm going to show you my version of the method call sequence, but I need to explain a few basics first. In kobj (and my object system cobj) a class is just a collection of method implementations: there is no type system determining the set of methods implemented by a class. The most obvious consequence is that method declarations are divorced from classes. They are effectively just names, like method selectors in Smalltalk. A method has several parts: at compile time it has an inline function that is used to call the method, and a type so that implementations and calls can be checked; at run time it has an extern object that serves to represent the method selector.

	/* In a header file somewhere... */

	/* The type signature of my_method() */
	typedef int my_method_t(cobj_t *o, int a, void *p);

	/* An extern object representing the method selector.
	 * It is not declared as a pointer because we want to
	 * be able to get its address efficiently: addresses
	 * are resolved at link time, saving an indirection
	 * at run time. The object itself is just a place-
	 * holder, but may be useful for introspection.
	 */
	extern struct cobj_meth_t my_method_sel;

	/* Method dispatch is implemented as an inline function.
	 * The actual code is the same for all methods, except
	 * for variations in the types, and would normally be
	 * created with a macro.
	 */
	static inline int my_method(cobj_t *o, int a, void *p) {
		cobj_mi_t *mi = &o->cobj_mi[COBJ_HASH(&my_method_sel)];
		if(mi.m != &my_method_sel)
			cobj_lookup(o, &my_method_sel);
		return ((my_method_t*)mi.i)(o, a, p);
	}

The lookup cache is an array of {method,implementation} pairs, indexed by a hash of the method selector. If the selector doesn't match then we call the dynamic lookup function to find the implementation and fill in the table entry. Then we can just do an indirect call of the implementation. The hash function is defined to be as lightweight as possible:

	/* In the main cobj header file... */

	typedef void cobj_impl_t(void);

	/* {method,implementation} pairs */
	typedef struct cobj_mi_t {
		cobj_meth_t *m;
		cobj_impl_t *i;
	} cobj_mi_t;

	/* standard prefix of all objects */
	#define COBJ_PREFIX cobj_mi_t *cobj_mi

	typedef struct cobj_t {
		COBJ_PREFIX;
	} cobj_t;

	#define COBJ_MI_SIZE 32
	#define COBJ_HASH(m) (((int)(m) / sizeof(cobj_mi_t)) % COBJ_MI_SIZE)

As well as the explicit operations for computing the hash, the compiler needs to multiply it by sizeof(cobj_mi_t) when indexing the cache. The resulting combination will just compile to (m & 0xF8) - i.e. we use the most random bits from the method object's address as the index.

In kobj, the lookup function was fixed. Classes just consisted of a lookup cache shared by all instances, and a simple table of {method,implementation} pairs that the dynamic lookup function could search. Objects had a similarly simple structure: they were just structs whose first member pointed to the object's class's method cache. There was no support for inheritance; however some parts of the kernel had hacked up their own implementations using the C++ layout with the base class's members as the prefix of the object with the derived class's members following. The problem with this is it introduces another opportunity for ABI incompatibility: if the base class changes size then all derived classes need to be recompiled.

I was interested in extending the object system to allow inheritance of various kinds whilst avoiding as much ABI coupling as possible. I had read the Art of the Metaobject Protocol so I was also interested in playing around with object systems where you could replace key parts like object layout, inheritance structure, etc.

In a traditional OO system, each class is also an object. The class-dependent operations are things like dynamic method lookup and object creation. If a class is an object then these operations should be methods on the class object. This implies that a class must be an instance of a class, which in Smalltalk terminology is called a metaclass. I envisioned having different metaclasses to implement simple method lookup, single inheritance, multiple inheritance, mixin inheritance, etc. Thus the dynamic lookup function just juggles things so that it can perform the appropriate method invocation on the original object's class and save the result in the cache.

	/* In the main cobj header file... */

	/* common prefix of class objects */
	#define COBJ_CLASS_PREFIX COBJ_PREFIX; cobj_mi_t cache[COBJ_MI_SIZE]

	typedef struct cobj_class_t {
		COBJ_CLASS_PREFIX;
	} cobj_class_t;

	static inline cobj_t *cobj_class(cobj_t *obj) {
		void *cache = obj->cobj_mi;
		void *class = (char *)cache - offsetof(cobj_class_t, cache);
		return(class);
	}

	/* In the main cobj code file... */

	void cobj_lookup(cobj_t *obj, cobj_meth_t *meth) {
		cobj_mi_t *mi = &obj->cobj_mi[COBJ_HASH(meth)];
		mi->i = cobj_do_lookup(cobj_class(obj), meth, obj);
		mi->m = meth;
	}

This function is designed to make the method dispatch fast path as small as possible, particularly by minimizing the number of arguments. It is also the vehicle for recursion up through the metaclasses. Since a class is an object with an implementation of the cobj_do_lookup() method, and a metaclass is the class of a class, metaclasses are also objects with implementations of the cobj_do_lookup() method. Obviously we need a way to bound the recursion.

Eventually we must reach the class that is its own metaclass. The safe way is to detect this case in cobj_lookup() and call a hardcoded cobj_do_lookup_base() implementation. This tactic allows the ur-class to be a fairly normal class that supports other methods (e.g. for introspection or construction). A much more amusing way is to arrange that the ur-class only has one method, so we can pre-populate its cache. (We can't do this if there's more than one method because we don't know what addresses and therefore indexes they will have - and they might clash). Then the recursion will always terminate with a cache hit. You then need a slightly more elaborate bootstrap strategy. The ur-class is the metaclass of classes with one method, of which there will be a zeroth instance with the pre-populated cache. There will be one other instance which knows how to do method lookup for simple classes with more than one method but no inheritance etc. This will in turn have an instance which is the same as the safe (boring) ur-class.

	struct cobj_class_ur {
		COBJ_CLASS_PREFIX;
		cobj_impl_t *do_lookup;
	} cobj_zero = {
		/* cache pointer */
		&cobj_zero.cobj_mi,
		/* pre-populated cache */
		{ { cobj_do_lookup_o, cobj_do_lookup_ur },
		  /* COBJ_MI_SIZE times... */ 	
		  { cobj_do_lookup_o, cobj_do_lookup_ur } },
		/* the only method we support */
		(cobj_impl_t *)cobj_do_lookup_ur
	}, cobj_one = {
		/* cache pointer */
		&cobj_zero.cobj_mi,
		/* no need to pre-populate this cache */
		{ { NULL, NULL } },
		/* the only method we support */
		(cobj_impl_t *)cobj_do_lookup_simple
	};

	cobj_impl_t *cobj_do_lookup_ur(cobj_t *class, cobj_meth_t *meth, cobj_t *obj) {
		assert(meth == cobj_do_lookup_sel);
		return(class->do_lookup);
	}

Apart from the goal of supporting different kinds of inheritance, this metaclass approach is very like Smalltalk (including the recursion back to a class that is its own metaclass), and Objective C is very like Smalltalk. However they are not solutions to the ABI skew problem (or the API skew problem!) that I started with, because in Smalltalk and Objective C the members of base classes and the size of base objects are exposed to derived classes, so you can't extend a base class without losing compatibility.

This was all quite fun to play with, but unfortunately I got hung up on writing a preprocessor to make declaring classes and methods less painful, so it never got very far before I got a job.