* Add multiple inheritance to kobj. Each class can have zero or more base

  classes and if a method is not found in a given class, its base classes
  are searched (in the order they were declared). This search is recursive,
  i.e. a method may be define in a base class of a base class.
* Change the kobj method lookup algorithm to one which is SMP-safe. This
  relies only on the constraint that an observer of a sequence of writes
  of pointer-sized values will see exactly one of those values, not a
  mixture of two or more values. This assumption holds for all processors
  which FreeBSD supports.
* Add locking to kobj class initialisation.
* Add a simpler form of 'inheritance' for devclasses. Each devclass can
  have a parent devclass. Searches for drivers continue up the chain of
  devclasses until either a matching driver is found or a devclass is
  reached which has no parent. This can allow, for instance, pci drivers
  to match cardbus devices (assuming that cardbus declares pci as its
  parent devclass).
* Increment __FreeBSD_version.

This preserves the driver API entirely except for one minor feature used
by the ISA compatibility shims. A workaround for ISA compatibility will
be committed separately. The kobj and newbus ABI has changed - all modules
must be recompiled.

2 files changed, 257 insertions, 99 deletions

diff --git a/sys/kern/subr_bus.c b/sys/kern/subr_bus.c
index 03049bf..9a65242 100644
--- a/sys/kern/subr_bus.c
+++ b/sys/kern/subr_bus.c
@@ -1,5 +1,5 @@
 /*-
- * Copyright (c) 1997,1998 Doug Rabson
+ * Copyright (c) 1997,1998,2003 Doug Rabson
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -62,8 +62,8 @@ SYSCTL_NODE(_hw, OID_AUTO, bus, CTLFLAG_RW, NULL, NULL);
  */
 typedef struct driverlink *driverlink_t;
 struct driverlink {
-    driver_t	*driver;
-    TAILQ_ENTRY(driverlink) link;	/* list of drivers in devclass */
+	kobj_class_t	driver;
+	TAILQ_ENTRY(driverlink) link;	/* list of drivers in devclass */
 };
 
 /*
@@ -75,6 +75,7 @@ typedef TAILQ_HEAD(device_list, device) device_list_t;
 
 struct devclass {
 	TAILQ_ENTRY(devclass) link;
+	devclass_t	parent;		/* parent in devclass hierarchy */
 	driver_list_t	drivers;     /* bus devclasses store drivers for bus */
 	char		*name;
 	device_t	*devices;	/* array of devices indexed by unit */
@@ -509,7 +510,8 @@ DEFINE_CLASS(null, null_methods, 0);
 static devclass_list_t devclasses = TAILQ_HEAD_INITIALIZER(devclasses);
 
 static devclass_t
-devclass_find_internal(const char *classname, int create)
+devclass_find_internal(const char *classname, const char *parentname,
+		       int create)
 {
 	devclass_t dc;
 
@@ -519,15 +521,16 @@ devclass_find_internal(const char *classname, int create)
 
 	TAILQ_FOREACH(dc, &devclasses, link) {
 		if (!strcmp(dc->name, classname))
-			return (dc);
+			break;
 	}
 
-	PDEBUG(("%s not found%s", classname, (create? ", creating": "")));
-	if (create) {
+	if (create && !dc) {
+		PDEBUG(("creating %s", classname));
 		dc = malloc(sizeof(struct devclass) + strlen(classname) + 1,
 		    M_BUS, M_NOWAIT|M_ZERO);
 		if (!dc)
 			return (NULL);
+		dc->parent = NULL;
 		dc->name = (char*) (dc + 1);
 		strcpy(dc->name, classname);
 		TAILQ_INIT(&dc->drivers);
@@ -535,6 +538,9 @@ devclass_find_internal(const char *classname, int create)
 
 		bus_data_generation_update();
 	}
+	if (parentname && dc && !dc->parent) {
+		dc->parent = devclass_find_internal(parentname, 0, FALSE);
+	}
 
 	return (dc);
 }
@@ -542,13 +548,13 @@ devclass_find_internal(const char *classname, int create)
 devclass_t
 devclass_create(const char *classname)
 {
-	return (devclass_find_internal(classname, TRUE));
+	return (devclass_find_internal(classname, 0, TRUE));
 }
 
 devclass_t
 devclass_find(const char *classname)
 {
-	return (devclass_find_internal(classname, FALSE));
+	return (devclass_find_internal(classname, 0, FALSE));
 }
 
 int
@@ -574,7 +580,7 @@ devclass_add_driver(devclass_t dc, driver_t *driver)
 	/*
 	 * Make sure the devclass which the driver is implementing exists.
 	 */
-	devclass_find_internal(driver->name, TRUE);
+	devclass_find_internal(driver->name, 0, TRUE);
 
 	dl->driver = driver;
 	TAILQ_INSERT_TAIL(&dc->drivers, dl, link);
@@ -668,7 +674,7 @@ devclass_find_driver_internal(devclass_t dc, const char *classname)
 	return (NULL);
 }
 
-driver_t *
+kobj_class_t
 devclass_find_driver(devclass_t dc, const char *classname)
 {
 	driverlink_t dl;
@@ -751,6 +757,18 @@ devclass_find_free_unit(devclass_t dc, int unit)
 	return (unit);
 }
 
+void
+devclass_set_parent(devclass_t dc, devclass_t pdc)
+{
+	dc->parent = pdc;
+}
+
+devclass_t
+devclass_get_parent(devclass_t dc)
+{
+	return (dc->parent);
+}
+
 static int
 devclass_alloc_unit(devclass_t dc, int *unitp)
 {
@@ -857,7 +875,7 @@ make_device(device_t parent, const char *name, int unit)
 	PDEBUG(("%s at %s as unit %d", name, DEVICENAME(parent), unit));
 
 	if (name) {
-		dc = devclass_find_internal(name, TRUE);
+		dc = devclass_find_internal(name, 0, TRUE);
 		if (!dc) {
 			printf("make_device: can't find device class %s\n",
 			    name);
@@ -1043,44 +1061,54 @@ device_probe_child(device_t dev, device_t child)
 	if (child->state == DS_ALIVE)
 		return (0);
 
-	for (dl = first_matching_driver(dc, child);
-	     dl;
-	     dl = next_matching_driver(dc, child, dl)) {
-		PDEBUG(("Trying %s", DRIVERNAME(dl->driver)));
-		device_set_driver(child, dl->driver);
-		if (!hasclass)
-			device_set_devclass(child, dl->driver->name);
-		result = DEVICE_PROBE(child);
-		if (!hasclass)
-			device_set_devclass(child, 0);
+	for (; dc; dc = dc->parent) {
+		for (dl = first_matching_driver(dc, child);
+		     dl;
+		     dl = next_matching_driver(dc, child, dl)) {
+			PDEBUG(("Trying %s", DRIVERNAME(dl->driver)));
+			device_set_driver(child, dl->driver);
+			if (!hasclass)
+				device_set_devclass(child, dl->driver->name);
+			result = DEVICE_PROBE(child);
+			if (!hasclass)
+				device_set_devclass(child, 0);
 
-		/*
-		 * If the driver returns SUCCESS, there can be no higher match
-		 * for this device.
-		 */
-		if (result == 0) {
-			best = dl;
-			pri = 0;
-			break;
-		}
+			/*
+			 * If the driver returns SUCCESS, there can be
+			 * no higher match for this device.
+			 */
+			if (result == 0) {
+				best = dl;
+				pri = 0;
+				break;
+			}
 
-		/*
-		 * The driver returned an error so it certainly doesn't match.
-		 */
-		if (result > 0) {
-			device_set_driver(child, 0);
-			continue;
-		}
+			/*
+			 * The driver returned an error so it
+			 * certainly doesn't match.
+			 */
+			if (result > 0) {
+				device_set_driver(child, 0);
+				continue;
+			}
 
+			/*
+			 * A priority lower than SUCCESS, remember the
+			 * best matching driver. Initialise the value
+			 * of pri for the first match.
+			 */
+			if (best == 0 || result > pri) {
+				best = dl;
+				pri = result;
+				continue;
+			}
+		}
 		/*
-		 * A priority lower than SUCCESS, remember the best matching
-		 * driver. Initialise the value of pri for the first match.
+		 * If we have an unambiguous match in this devclass,
+		 * don't look in the parent.
 		 */
-		if (best == 0 || result > pri) {
-			best = dl;
-			pri = result;
-			continue;
-		}
+		if (best && pri == 0)
+			break;
 	}
 
 	/*
@@ -1377,7 +1405,7 @@ device_set_devclass(device_t dev, const char *classname)
 		return (EINVAL);
 	}
 
-	dc = devclass_find_internal(classname, TRUE);
+	dc = devclass_find_internal(classname, 0, TRUE);
 	if (!dc)
 		return (ENOMEM);
 
@@ -2242,7 +2270,7 @@ root_bus_module_handler(module_t mod, int what, void* arg)
 		kobj_init((kobj_t) root_bus, (kobj_class_t) &root_driver);
 		root_bus->driver = &root_driver;
 		root_bus->state = DS_ATTACHED;
-		root_devclass = devclass_find_internal("root", FALSE);
+		root_devclass = devclass_find_internal("root", 0, FALSE);
 		devinit();
 		return (0);
 
@@ -2276,12 +2304,13 @@ root_bus_configure(void)
 int
 driver_module_handler(module_t mod, int what, void *arg)
 {
-	int error, i;
+	int error;
 	struct driver_module_data *dmd;
 	devclass_t bus_devclass;
+	kobj_class_t driver;
 
 	dmd = (struct driver_module_data *)arg;
-	bus_devclass = devclass_find_internal(dmd->dmd_busname, TRUE);
+	bus_devclass = devclass_find_internal(dmd->dmd_busname, 0, TRUE);
 	error = 0;
 
 	switch (what) {
@@ -2289,31 +2318,38 @@ driver_module_handler(module_t mod, int what, void *arg)
 		if (dmd->dmd_chainevh)
 			error = dmd->dmd_chainevh(mod,what,dmd->dmd_chainarg);
 
-		for (i = 0; !error && i < dmd->dmd_ndrivers; i++) {
-			PDEBUG(("Loading module: driver %s on bus %s",
-			    DRIVERNAME(dmd->dmd_drivers[i]), dmd->dmd_busname));
-			error = devclass_add_driver(bus_devclass,
-			    dmd->dmd_drivers[i]);
-		}
+		driver = dmd->dmd_driver;
+		PDEBUG(("Loading module: driver %s on bus %s",
+		    DRIVERNAME(driver), dmd->dmd_busname));
+		error = devclass_add_driver(bus_devclass, driver);
 		if (error)
 			break;
 
 		/*
-		 * The drivers loaded in this way are assumed to all
-		 * implement the same devclass.
+		 * If the driver has any base classes, make the
+		 * devclass inherit from the devclass of the driver's
+		 * first base class. This will allow the system to
+		 * search for drivers in both devclasses for children
+		 * of a device using this driver.
 		 */
-		*dmd->dmd_devclass =
-		    devclass_find_internal(dmd->dmd_drivers[0]->name, TRUE);
+		if (driver->baseclasses) {
+			const char *parentname;
+			parentname = driver->baseclasses[0]->name;
+			*dmd->dmd_devclass =
+				devclass_find_internal(driver->name,
+				    parentname, TRUE);
+		} else {
+			*dmd->dmd_devclass =
+				devclass_find_internal(driver->name, 0, TRUE);
+		}
 		break;
 
 	case MOD_UNLOAD:
-		for (i = 0; !error && i < dmd->dmd_ndrivers; i++) {
-			PDEBUG(("Unloading module: driver %s from bus %s",
-			    DRIVERNAME(dmd->dmd_drivers[i]),
-			    dmd->dmd_busname));
-			error = devclass_delete_driver(bus_devclass,
-			    dmd->dmd_drivers[i]);
-		}
+		PDEBUG(("Unloading module: driver %s from bus %s",
+		    DRIVERNAME(dmd->dmd_driver),
+		    dmd->dmd_busname));
+		error = devclass_delete_driver(bus_devclass,
+		    dmd->dmd_driver);
 
 		if (!error && dmd->dmd_chainevh)
 			error = dmd->dmd_chainevh(mod,what,dmd->dmd_chainarg);
diff --git a/sys/kern/subr_kobj.c b/sys/kern/subr_kobj.c
index a3fc230..1704a0f 100644
--- a/sys/kern/subr_kobj.c
+++ b/sys/kern/subr_kobj.c
@@ -1,5 +1,5 @@
 /*-
- * Copyright (c) 2000 Doug Rabson
+ * Copyright (c) 2000,2003 Doug Rabson
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -28,16 +28,15 @@
 __FBSDID("$FreeBSD$");
 
 #include <sys/param.h>
-#include <sys/queue.h>
-#include <sys/malloc.h>
 #include <sys/kernel.h>
-#include <sys/module.h>
-#include <sys/errno.h>
+#include <sys/kobj.h>
+#include <sys/lock.h>
+#include <sys/malloc.h>
+#include <sys/mutex.h>
 #include <sys/sysctl.h>
 #ifndef TEST
 #include <sys/systm.h>
 #endif
-#include <sys/kobj.h>
 
 #ifdef TEST
 #include "usertest.h"
@@ -57,22 +56,43 @@ SYSCTL_UINT(_kern, OID_AUTO, kobj_misses, CTLFLAG_RD,
 
 #endif
 
+static struct mtx kobj_mtx;
 static int kobj_next_id = 1;
 
 SYSCTL_UINT(_kern, OID_AUTO, kobj_methodcount, CTLFLAG_RD,
 	   &kobj_next_id, 0, "");
 
-static int
+static void
+kobj_init_mutex(void *arg)
+{
+
+	mtx_init(&kobj_mtx, "kobj", NULL, MTX_DEF);
+}
+
+SYSINIT(kobj, SI_SUB_LOCK, SI_ORDER_ANY, kobj_init_mutex, NULL);
+
+/*
+ * This method structure is used to initialise new caches. Since the
+ * desc pointer is NULL, it is guaranteed never to match any read
+ * descriptors.
+ */
+static struct kobj_method null_method = {
+	0, 0,
+};
+
+int
 kobj_error_method(void)
 {
+
 	return ENXIO;
 }
 
 static void
 kobj_register_method(struct kobjop_desc *desc)
 {
+
+	mtx_assert(&kobj_mtx, MA_OWNED);
 	if (desc->id == 0) {
-		KASSERT((kobj_next_id < KOBJ_CACHE_SIZE), ("kobj method table overflow"));
 		desc->id = kobj_next_id++;
 	}
 }
@@ -88,6 +108,8 @@ kobj_class_compile_common(kobj_class_t cls, kobj_ops_t ops)
 	kobj_method_t *m;
 	int i;
 
+	mtx_assert(&kobj_mtx, MA_OWNED);
+
 	/*
 	 * Don't do anything if we are already compiled.
 	 */
@@ -103,7 +125,8 @@ kobj_class_compile_common(kobj_class_t cls, kobj_ops_t ops)
 	/*
 	 * Then initialise the ops table.
 	 */
-	bzero(ops, sizeof(struct kobj_ops));
+	for (i = 0; i < KOBJ_CACHE_SIZE; i++)
+		ops->cache[i] = &null_method;
 	ops->cls = cls;
 	cls->ops = ops;
 }
@@ -113,42 +136,106 @@ kobj_class_compile(kobj_class_t cls)
 {
 	kobj_ops_t ops;
 
+	mtx_assert(&kobj_mtx, MA_NOTOWNED);
+
 	/*
 	 * Allocate space for the compiled ops table.
 	 */
 	ops = malloc(sizeof(struct kobj_ops), M_KOBJ, M_NOWAIT);
 	if (!ops)
 		panic("kobj_compile_methods: out of memory");
+
+	mtx_lock(&kobj_mtx);
+	
+	/*
+	 * We may have lost a race for kobj_class_compile here - check
+	 * to make sure someone else hasn't already compiled this
+	 * class.
+	 */
+	if (cls->ops) {
+		mtx_unlock(&kobj_mtx);
+		free(ops, M_KOBJ);
+		return;
+	}
+
 	kobj_class_compile_common(cls, ops);
+	mtx_unlock(&kobj_mtx);
 }
 
 void
 kobj_class_compile_static(kobj_class_t cls, kobj_ops_t ops)
 {
+
+	mtx_assert(&kobj_mtx, MA_NOTOWNED);
+
 	/*
 	 * Increment refs to make sure that the ops table is not freed.
 	 */
+	mtx_lock(&kobj_mtx);
 	cls->refs++;
 	kobj_class_compile_common(cls, ops);
+	mtx_unlock(&kobj_mtx);
 }
 
-void
-kobj_lookup_method(kobj_method_t *methods,
-		   kobj_method_t *ce,
-		   kobjop_desc_t desc)
+static kobj_method_t*
+kobj_lookup_method_class(kobj_class_t cls, kobjop_desc_t desc)
 {
-	ce->desc = desc;
-	for (; methods && methods->desc; methods++) {
-		if (methods->desc == desc) {
-			ce->func = methods->func;
-			return;
+	kobj_method_t *methods = cls->methods;
+	kobj_method_t *ce;
+
+	for (ce = methods; ce && ce->desc; ce++) {
+		if (ce->desc == desc) {
+			return ce;
 		}
 	}
-	if (desc->deflt)
-		ce->func = desc->deflt;
-	else
-		ce->func = kobj_error_method;
-	return;
+
+	return 0;
+}
+
+static kobj_method_t*
+kobj_lookup_method_mi(kobj_class_t cls,
+		      kobjop_desc_t desc)
+{
+	kobj_method_t *ce;
+	kobj_class_t *basep;
+
+	ce = kobj_lookup_method_class(cls, desc);
+	if (ce)
+		return ce;
+
+	basep = cls->baseclasses;
+	if (basep) {
+		for (; *basep; basep++) {
+			ce = kobj_lookup_method_mi(*basep, desc);
+			if (ce)
+				return ce;
+		}
+	}
+
+	return 0;
+}
+
+kobj_method_t*
+kobj_lookup_method(kobj_class_t cls,
+		   kobj_method_t **cep,
+		   kobjop_desc_t desc)
+{
+	kobj_method_t *ce;
+
+#ifdef KOBJ_STATS
+	/*
+	 * Correct for the 'hit' assumption in KOBJOPLOOKUP and record
+	 * a 'miss'.
+	 */
+	kobj_lookup_hits--;
+	kobj_lookup_misses--;
+#endif
+
+	ce = kobj_lookup_method_mi(cls, desc);
+	if (!ce)
+		ce = desc->deflt;
+	*cep = ce;
+	return ce;
 }
 
 void
@@ -156,18 +243,33 @@ kobj_class_free(kobj_class_t cls)
 {
 	int i;
 	kobj_method_t *m;
+	void* ops = 0;
 
-	/*
-	 * Unregister any methods which are no longer used.
-	 */
-	for (i = 0, m = cls->methods; m->desc; i++, m++)
-		kobj_unregister_method(m->desc);
+	mtx_assert(&kobj_mtx, MA_NOTOWNED);
+	mtx_lock(&kobj_mtx);
 
 	/*
-	 * Free memory and clean up.
+	 * Protect against a race between kobj_create and
+	 * kobj_delete.
 	 */
-	free(cls->ops, M_KOBJ);
-	cls->ops = 0;
+	if (cls->refs == 0) {
+		/*
+		 * Unregister any methods which are no longer used.
+		 */
+		for (i = 0, m = cls->methods; m->desc; i++, m++)
+			kobj_unregister_method(m->desc);
+
+		/*
+		 * Free memory and clean up.
+		 */
+		ops = cls->ops;
+		cls->ops = 0;
+	}
+	
+	mtx_unlock(&kobj_mtx);
+
+	if (ops)
+		free(ops, M_KOBJ);
 }
 
 kobj_t
@@ -191,28 +293,48 @@ kobj_create(kobj_class_t cls,
 void
 kobj_init(kobj_t obj, kobj_class_t cls)
 {
+	mtx_assert(&kobj_mtx, MA_NOTOWNED);
+  retry:
+	mtx_lock(&kobj_mtx);
+
 	/*
 	 * Consider compiling the class' method table.
 	 */
-	if (!cls->ops)
+	if (!cls->ops) {
+		/*
+		 * kobj_class_compile doesn't want the lock held
+		 * because of the call to malloc - we drop the lock
+		 * and re-try.
+		 */
+		mtx_unlock(&kobj_mtx);
 		kobj_class_compile(cls);
+		goto retry;
+	}
 
 	obj->ops = cls->ops;
 	cls->refs++;
+
+	mtx_unlock(&kobj_mtx);
 }
 
 void
 kobj_delete(kobj_t obj, struct malloc_type *mtype)
 {
 	kobj_class_t cls = obj->ops->cls;
+	int refs;
 
 	/*
 	 * Consider freeing the compiled method table for the class
 	 * after its last instance is deleted. As an optimisation, we
 	 * should defer this for a short while to avoid thrashing.
 	 */
+	mtx_assert(&kobj_mtx, MA_NOTOWNED);
+	mtx_lock(&kobj_mtx);
 	cls->refs--;
-	if (!cls->refs)
+	refs = cls->refs;
+	mtx_unlock(&kobj_mtx);
+
+	if (!refs)
 		kobj_class_free(cls);
 
 	obj->ops = 0;