Re: [PATCH] driver core: multithreaded device matching with dependency

Re: [PATCH] driver core: multithreaded device matching with dependency

[Stefan Richter]

Huang, Ying wrote:
> This is another solution to implement multithreaded device matching
> (probing). The device matching is delayed until all drivers are
> registered. The driver registering is executed one by one, this
> eliminates the potential of interdependency between driver. All devices
> are matched to drivers afterwards, multithreaded. The parent <->
> children relationship between devices is used as the dependency between
> devices, that is, the children devices matching will not begin until
> parent device matching finishes.

How can subsystems control multithreaded vs. singlethreaded probes?

For example, the IEEE 1394 subsystem should probe different nodes in
parallel, but different units on the same node serially.  Similar
requirements exist with other hardware.

Also, how can subsystems enable and disable multithreaded probes?

...
> +EXPORT_SYMBOL_GPL(device_match_freeze);
> +EXPORT_SYMBOL_GPL(device_match_thaw);

Their definitions lack kerneldoc comments.
-- 
Stefan Richter
-=====-=-=== -==- -=---
http://arcgraph.de/sr/

RE: [PATCH] driver core: multithreaded device matching with dependency

[Huang, Ying]

>From: Stefan Richter [mailto:stefanr@s5r6.in-berlin.de]
>
>How can subsystems control multithreaded vs. singlethreaded probes?
>
>For example, the IEEE 1394 subsystem should probe different nodes in
>parallel, but different units on the same node serially.  Similar
>requirements exist with other hardware.

For subsystems specific dependency problems, a field as follow can be
added into struct device:

struct device *depend;

The parallel device probing code will not do probing for the device,
unless the device pointed by "depend" has been probed, that is, they are
probed serially. As for IEEE 1394 subsystem, when the subsystem adds new
devices, the different units on the same node are linked together with
the "depend" field, so that they can be probed serially. So do other
subsystems.

>Also, how can subsystems enable and disable multithreaded probes?

If subsystem needs strictly serial probing, it can accomplish this
through "depend" field as mentioned above.

>> +EXPORT_SYMBOL_GPL(device_match_freeze);
>> +EXPORT_SYMBOL_GPL(device_match_thaw);
>
>Their definitions lack kerneldoc comments.

Sorry, I will add it in the next version.

Best Regards,
Huang Ying

[PATCH] driver core: multithreaded device matching with dependency

[Huang, Ying]

From: Huang Ying <ying.huang@intel.com>

This is another solution to implement multithreaded device matching
(probing). The device matching is delayed until all drivers are
registered. The driver registering is executed one by one, this
eliminates the potential of interdependency between driver. All devices
are matched to drivers afterwards, multithreaded. The parent <->
children relationship between devices is used as the dependency between
devices, that is, the children devices matching will not begin until
parent device matching finishes.

Signed-off-by: Huang Ying <ying.huang@intel.com>
---
The patch has been tested on a thinkpad T42. The system boot-up time can
be reduced effectively. To take advantage of the multithreaded matching
with the patch, following option must be added to kernel command line:

dev_match_thread=<thread number>

For many distributions, the drivers are not compiled in kernel directly,
instead, they are compiled as modules and inserted into kernel by a
initramfs. To take advanage of multithreaded matching in this situation,
the device_match_freeze and device_match_thaw can be encapsulated into
two syscall, and the device probing sequence of initramfs should be:

1. device_match_freeze
2. modprobe <driver1>
3. modprobe <driver2>
...
<n>. device_match_thaw.

 drivers/base/dd.c      |  168 ++++++++++++++++++++++++++++++++++++---
 include/linux/device.h |    5 +
 init/main.c            |    3
 3 files changed, 165 insertions(+), 11 deletions(-)
Index: linux-2.6.22-rc4/init/main.c
===================================================================
--- linux-2.6.22-rc4.orig/init/main.c	2007-06-08 18:26:11.000000000
+0800
+++ linux-2.6.22-rc4/init/main.c	2007-06-08 18:27:01.000000000 +0800
@@ -652,6 +652,7 @@
 	initcall_t *call;
 	int count = preempt_count();
 
+	device_match_freeze();
 	for (call = __initcall_start; call < __initcall_end; call++) {
 		ktime_t t0, t1, delta;
 		char *msg = NULL;
@@ -703,6 +704,8 @@
 		}
 	}
 
+	device_match_thaw(0);
+
 	/* Make sure there is no pending stuff from the initcall sequence */
 	flush_scheduled_work();
 }
Index: linux-2.6.22-rc4/drivers/base/dd.c
===================================================================
--- linux-2.6.22-rc4.orig/drivers/base/dd.c	2007-06-08
18:26:11.000000000 +0800
+++ linux-2.6.22-rc4/drivers/base/dd.c	2007-06-08 10:41:18.000000000
+0800
@@ -25,6 +25,7 @@
 
 #define to_drv(node) container_of(node, struct device_driver,
kobj.entry)
 
+static atomic_t device_match_freezed = ATOMIC_INIT(0);
 
 static void driver_bound(struct device *dev)
 {
@@ -220,6 +221,25 @@
 	return ret;
 }
 
+/* This function must be called with dev->sem held. */
+static inline int real_device_attach(struct device * dev)
+{
+	int ret = 0;
+
+	if (dev->driver) {
+		ret = device_bind_driver(dev);
+		if (ret == 0)
+			ret = 1;
+		else {
+			dev->driver = NULL;
+			ret = 0;
+		}
+	} else {
+		ret = bus_for_each_drv(dev->bus, NULL, dev, __device_attach);
+	}
+	return ret;
+}
+
 /**
  *	device_attach - try to attach device to a driver.
  *	@dev:	device.
@@ -238,18 +258,10 @@
 {
 	int ret = 0;
 
+	if (atomic_read(&device_match_freezed))
+		return 0;
 	down(&dev->sem);
-	if (dev->driver) {
-		ret = device_bind_driver(dev);
-		if (ret == 0)
-			ret = 1;
-		else {
-			dev->driver = NULL;
-			ret = 0;
-		}
-	} else {
-		ret = bus_for_each_drv(dev->bus, NULL, dev, __device_attach);
-	}
+	ret = real_device_attach(dev);
 	up(&dev->sem);
 	return ret;
 }
@@ -291,6 +303,8 @@
  */
 int driver_attach(struct device_driver * drv)
 {
+	if (atomic_read(&device_match_freezed))
+		return 0;
 	return bus_for_each_dev(drv->bus, NULL, drv, __driver_attach);
 }
 
@@ -380,3 +394,135 @@
 EXPORT_SYMBOL_GPL(device_attach);
 EXPORT_SYMBOL_GPL(driver_attach);
 
+#define to_dev(obj) container_of(obj, struct device, kobj)
+
+static void init_devices_check(void)
+{
+	struct kobject *kobj;
+	struct device *dev;
+
+	spin_lock(&devices_subsys.list_lock);
+	list_for_each_entry(kobj, &(devices_subsys.list), entry) {
+		dev = to_dev(kobj);
+		dev = get_device(dev);
+		/* class device and root device need not be checked */
+		if (dev->class || !dev->parent) {
+			dev->is_checked = 1;
+			dev->is_matched = 1;
+		} else
+			dev->is_checked = 0;
+		dev->is_checking = 0;
+		put_device(dev);
+	}
+	spin_unlock(&devices_subsys.list_lock);
+}
+
+#define CONTINUE_FOUND  1
+#define CONTINUE_WAIT   2
+
+static int find_next_device_to_check(struct device **pdev)
+{
+	struct kobject *kobj;
+	struct device *dev, *parent;
+	int cont = 0;
+
+	spin_lock(&devices_subsys.list_lock);
+	list_for_each_entry(kobj, &(devices_subsys.list), entry) {
+		dev = to_dev(kobj);
+		dev = get_device(dev);
+		parent = get_device(dev->parent);
+		if (dev->is_checking)
+			cont = CONTINUE_WAIT;
+		else if (!dev->is_matched && !dev->is_checked) {
+			if (parent->is_matched || parent->is_checked) {
+				*pdev = dev;
+				cont = CONTINUE_FOUND;
+			} else
+				cont = CONTINUE_WAIT;
+		}
+		put_device(parent);
+		if (cont == CONTINUE_FOUND)
+			break;
+		put_device(dev);
+	}
+	spin_unlock(&devices_subsys.list_lock);
+	return cont;
+}
+
+static void check_device(struct device *dev)
+{
+	int ret;
+
+	down(&dev->sem);
+	if (dev->is_checking || dev->is_checked)
+		goto out;
+	dev->is_checking = 1;
+	pr_debug("dev: %s - begin\n", dev->bus_id);
+	ret = real_device_attach(dev);
+	pr_debug("dev: %s - end\n", dev->bus_id);
+	dev->is_checking = 0;
+	dev->is_checked = 1;
+	dev->is_matched = (ret == 1);
+out:
+	up(&dev->sem);
+}
+
+static int devices_check_thread(void *data)
+{
+	struct device *dev = NULL;
+	int cont;
+	struct completion *thread_complete = data;
+
+	while ((cont = find_next_device_to_check(&dev))) {
+		if (cont == CONTINUE_FOUND) {
+			check_device(dev);
+			put_device(dev);
+		} else
+			yield();
+	}
+	complete_and_exit(thread_complete, 0);
+	return 0;
+}
+
+void device_match_freeze(void)
+{
+	atomic_set(&device_match_freezed, 1);
+}dev_match_thread
+
+static int dev_match_thread_default = 1;
+
+void device_match_thaw(int thread)
+{
+	struct completion *threads_complete;
+	int i;
+	static DECLARE_MUTEX(sem_thaw);
+
+	down(&sem_thaw);
+	if (thread <= 0)
+		thread = dev_match_thread_default > 0 ? \
+			dev_match_thread_default : 1;
+	threads_complete = kmalloc(sizeof(struct completion) * thread,
+				   GFP_KERNEL);
+	init_devices_check();
+	for (i = 0; i < thread; i++) {
+		init_completion(&threads_complete[i]);
+		kernel_thread(devices_check_thread,
+			      &threads_complete[i],
+			      CLONE_KERNEL);
+	}
+	for (i = 0; i < thread; i++)
+		wait_for_completion(&threads_complete[i]);
+	atomic_set(&device_match_freezed, 0);
+	up(&sem_thaw);
+}
+
+static int __init dev_match_thread(char *str)
+{
+	get_option(&str, &dev_match_thread_default);
+	return 1;
+}
+
+__setup("dev_match_thread=", dev_match_thread);
+
+EXPORT_SYMBOL_GPL(device_match_freeze);
+EXPORT_SYMBOL_GPL(device_match_thaw);
Index: linux-2.6.22-rc4/include/linux/device.h
===================================================================
--- linux-2.6.22-rc4.orig/include/linux/device.h	2007-06-08
18:26:11.000000000 +0800
+++ linux-2.6.22-rc4/include/linux/device.h	2007-06-08
10:35:21.000000000 +0800
@@ -419,6 +419,9 @@
 	struct device_type	*type;
 	unsigned		is_registered:1;
 	unsigned		uevent_suppress:1;
+ 	unsigned		is_matched:1;
+ 	unsigned		is_checking:1;
+ 	unsigned		is_checked:1;
 	struct device_attribute uevent_attr;
 	struct device_attribute *devt_attr;
 
@@ -525,6 +528,8 @@
 extern int  __must_check device_attach(struct device * dev);
 extern int __must_check driver_attach(struct device_driver *drv);
 extern int __must_check device_reprobe(struct device *dev);
+extern void device_match_freeze(void);
+extern void device_match_thaw(int thread);
 
 /*
  * Easy functions for dynamically creating devices on the fly

Re: [PATCH] driver core: multithreaded device matching with dependency

[Stefan Richter]

Huang, Ying wrote:
>>From: Stefan Richter [mailto:stefanr@s5r6.in-berlin.de]
>>
>>How can subsystems control multithreaded vs. singlethreaded probes?
>>
>>For example, the IEEE 1394 subsystem should probe different nodes in
>>parallel, but different units on the same node serially.  Similar
>>requirements exist with other hardware.
> 
> For subsystems specific dependency problems, a field as follow can be
> added into struct device:
> 
> struct device *depend;
> 
> The parallel device probing code will not do probing for the device,
> unless the device pointed by "depend" has been probed,

A bad API.  Subsystems and the driver core will both traverse the trees
(usually just lists) which can be built from the depend pointers, and
the trees grow and shrink dynamically.  Perhaps it would be simpler if
the subsystem would just use a mutex per group of devices which have to
be serialized.

*However*, IMO parallelized probing should be implemented in the
subsystems themselves in the first place, _not in the driver core_.

The subsystems know where parallelism is possible and safe and
effective, the driver core doesn't.
-- 
Stefan Richter
-=====-=-=== -==- -=---
http://arcgraph.de/sr/

RE: [PATCH] driver core: multithreaded device matching with dependency

[Huang, Ying]

>A bad API.  Subsystems and the driver core will both traverse the trees
>(usually just lists) which can be built from the depend pointers, and
>the trees grow and shrink dynamically.  Perhaps it would be simpler if
>the subsystem would just use a mutex per group of devices which have to
>be serialized.

Yes, this is a bad API. I have a new idea. The /sys/devices is a tree,
which is linked by dev->klist_children, any sub-tree of /sys/devices
tree can be a parallel unit, which can be indicated by a flag of struct
device of root node of sub-tree. In a sub-tree being a parallel unit,
all probing is serialized, while the probing of different sub-trees is
parallelized. The find_next_device_to_check will not traverse through
devices_subsys.list, but traverse through dev->klist_children. In the
IEEE 1394 case, the "node" can be a parallel unit (sub-tree) by set the
corresponding flag in struct device of "node", and the "unit" under
"node" will be probed serially. In general, subsystems can set the flag
in any struct device if necessary, even the root struct device of
subsystem, which means all devices in the subsystem must be probed
serially.

I will work out a new patch based on this new idea.

>*However*, IMO parallelized probing should be implemented in the
>subsystems themselves in the first place, _not in the driver core_.
>
>The subsystems know where parallelism is possible and safe and
>effective, the driver core doesn't.

I totally agree that the parallelized probing should be controlled by
the subsystems. By if the mechanism can be provided by driver core
effectively, the solution will be ideal.

Best Regards,
Huang Ying

RE: [PATCH] driver core: multithreaded device matching with dependency

[Huang, Ying]

Hi, Stefan,

I have worked out a new patch with single-threaded unit supported in
multithreaded device probing. A new flag as follow is added to struct
device,

unsigned singlethreaded_probe:1;

Which indicate that the device node and all its children node must be
probed single-threaded. During searching next device to probe, if a
device has singlethreaded_probe flag set, the devices under it will not
be searched. Instead, the device and all devices under it will be probed
serially.

Can this mechanism solve the demand of IEEE1394 subsystem effectively?

The patch is only for concept verification. It can work on my thinkpad
T42. More optimization can be done if necessary. Because I have only
"Outlook" as mail client, the format of patch may have some problem. If
the patch has any problem and you need the patch, I can resend it in
attach file.

Best Regards,
Huang Ying 

Index: linux-2.6.22-rc4/init/main.c
===================================================================
--- linux-2.6.22-rc4.orig/init/main.c	2007-06-08 18:26:11.000000000
+0800
+++ linux-2.6.22-rc4/init/main.c	2007-06-08 18:27:01.000000000
+0800
@@ -652,6 +652,7 @@
 	initcall_t *call;
 	int count = preempt_count();
 
+	device_match_freeze();
 	for (call = __initcall_start; call < __initcall_end; call++) {
 		ktime_t t0, t1, delta;
 		char *msg = NULL;
@@ -703,6 +704,8 @@
 		}
 	}
 
+	device_match_thaw(0);
+
 	/* Make sure there is no pending stuff from the initcall
sequence */
 	flush_scheduled_work();
 }
Index: linux-2.6.22-rc4/drivers/base/dd.c
===================================================================
--- linux-2.6.22-rc4.orig/drivers/base/dd.c	2007-06-08
18:26:11.000000000 +0800
+++ linux-2.6.22-rc4/drivers/base/dd.c	2007-06-09 22:30:26.000000000
+0800
@@ -25,6 +25,7 @@
 
 #define to_drv(node) container_of(node, struct device_driver,
kobj.entry)
 
+static atomic_t device_match_freezed = ATOMIC_INIT(0);
 
 static void driver_bound(struct device *dev)
 {
@@ -220,6 +221,25 @@
 	return ret;
 }
 
+/* This function must be called with dev->sem held. */
+static inline int real_device_attach(struct device * dev)
+{
+	int ret = 0;
+
+	if (dev->driver) {
+		ret = device_bind_driver(dev);
+		if (ret == 0)
+			ret = 1;
+		else {
+			dev->driver = NULL;
+			ret = 0;
+		}
+	} else {
+		ret = bus_for_each_drv(dev->bus, NULL, dev,
__device_attach);
+	}
+	return ret;
+}
+
 /**
  *	device_attach - try to attach device to a driver.
  *	@dev:	device.
@@ -238,18 +258,10 @@
 {
 	int ret = 0;
 
+	if (atomic_read(&device_match_freezed))
+		return 0;
 	down(&dev->sem);
-	if (dev->driver) {
-		ret = device_bind_driver(dev);
-		if (ret == 0)
-			ret = 1;
-		else {
-			dev->driver = NULL;
-			ret = 0;
-		}
-	} else {
-		ret = bus_for_each_drv(dev->bus, NULL, dev,
__device_attach);
-	}
+	ret = real_device_attach(dev);
 	up(&dev->sem);
 	return ret;
 }
@@ -291,6 +303,8 @@
  */
 int driver_attach(struct device_driver * drv)
 {
+	if (atomic_read(&device_match_freezed))
+		return 0;
 	return bus_for_each_dev(drv->bus, NULL, drv, __driver_attach);
 }
 
@@ -380,3 +394,186 @@
 EXPORT_SYMBOL_GPL(device_attach);
 EXPORT_SYMBOL_GPL(driver_attach);
 
+#define to_dev(obj) container_of(obj, struct device, kobj)
+
+static void init_devices_check(void)
+{
+	struct kobject *kobj;
+	struct device *dev;
+
+	spin_lock(&devices_subsys.list_lock);
+	list_for_each_entry(kobj, &(devices_subsys.list), entry) {
+		dev = to_dev(kobj);
+		dev = get_device(dev);
+		/* class device and root device need not be checked */
+		if (dev->class || !dev->parent) {
+			dev->is_checked = 1;
+			dev->is_matched = 1;
+		} else
+			dev->is_checked = 0;
+		dev->is_checking = 0;
+		put_device(dev);
+	}
+	spin_unlock(&devices_subsys.list_lock);
+}
+
+#define FIND_DEVICE_FOUND  1
+#define FIND_DEVICE_WAIT   2
+
+struct find_device_data
+{
+	struct device **pdev;
+	int result;
+};
+
+static int find_next_device_to_check_in_tree(struct device *dev,
+					     void *data)
+{
+	struct find_device_data *pfind = data;
+
+	get_device(dev);
+	if (dev->is_checking)
+		pfind->result = FIND_DEVICE_WAIT;
+	else if (dev->is_matched || dev->is_checked) {
+		if (!dev->singlethreaded_probe &&
+		    !list_empty(&dev->klist_children.k_list))
+			device_for_each_child(dev, data,
+
find_next_device_to_check_in_tree);
+	} else {
+		struct device *depend;
+
+		depend = get_device(dev->depend);
+		if (!depend || depend->is_matched || depend->is_checked)
{
+			*pfind->pdev = dev;
+			pfind->result = FIND_DEVICE_FOUND;
+		} else
+			pfind->result = FIND_DEVICE_WAIT;
+		put_device(depend);
+	}
+	if (pfind->result != FIND_DEVICE_FOUND) {
+		put_device(dev);
+		return 1;
+	}
+	return 0;
+}
+
+static int find_next_device_to_check(struct device **pdev)
+{
+	struct kobject *kobj;
+	struct device *dev;
+	struct find_device_data find;
+
+	find.pdev = pdev;
+	find.result = 0;
+	spin_lock(&devices_subsys.list_lock);
+	list_for_each_entry(kobj, &(devices_subsys.list), entry) {
+		dev = to_dev(kobj);
+		dev = get_device(dev);
+		if (!dev->parent)
+			find_next_device_to_check_in_tree(dev, &find);
+		put_device(dev);
+		if (find.result == FIND_DEVICE_FOUND)
+			break;
+	}
+	spin_unlock(&devices_subsys.list_lock);
+	return find.result;
+}
+
+static int check_device(struct device *dev, void *data)
+{
+	int ret;
+
+	down(&dev->sem);
+	if (dev->is_checking || dev->is_checked) {
+		up(&dev->sem);
+		return 0;
+	}
+	dev->is_checking = 1;
+	//pr_debug("dev: %s - begin\n", dev->bus_id);
+	printk("dev: %s - begin\n", dev->bus_id);
+	ret = real_device_attach(dev);
+	//pr_debug("dev: %s - end\n", dev->bus_id);
+	printk("dev: %s - end\n", dev->bus_id);
+	dev->is_checking = 0;
+	dev->is_checked = 1;
+	dev->is_matched = (ret == 1);
+	up(&dev->sem);
+	if (data)
+		device_for_each_child(dev, data, check_device);
+	return 0;
+}
+
+static int devices_check_thread(void *data)
+{
+	struct device *dev = NULL;
+	int result;
+	struct completion *thread_complete = data;
+
+	while ((result = find_next_device_to_check(&dev))) {
+		if (result == FIND_DEVICE_FOUND) {
+			check_device(dev, (void
*)!!dev->singlethreaded_probe);
+			put_device(dev);
+		} else
+			yield();
+	}
+	complete_and_exit(thread_complete, 0);
+	return 0;
+}
+
+/**
+ *	device_match_freeze - disable device/driver matching.
+ *
+ *	All subsequent device or driver registering will not trigger
+ *	device/driver matching until device_match_thaw is called.
+ */
+void device_match_freeze(void)
+{
+	atomic_set(&device_match_freezed, 1);
+}
+
+static int dev_match_thread_default = 1;
+
+/**
+ *	device_match_thaw - renable device/driver matching and check all
+ *	pending device/driver matching.
+ *	@thread: number of threads to do device/driver matching.
+ *
+ *	All devices are checked for driver matching, multithreaded
matching
+ *	is used to accelerate matching process. The device/driver
matching
+ *	is reenabled afterwards.
+ */
+void device_match_thaw(int thread)
+{
+	struct completion *threads_complete;
+	int i;
+	static DECLARE_MUTEX(sem_thaw);
+
+	down(&sem_thaw);
+	if (thread <= 0)
+		thread = dev_match_thread_default > 0 ? \
+			dev_match_thread_default : 1;
+	threads_complete = kmalloc(sizeof(struct completion) * thread,
+				   GFP_KERNEL);
+	init_devices_check();
+	for (i = 0; i < thread; i++) {
+		init_completion(&threads_complete[i]);
+		kernel_thread(devices_check_thread,
+			      &threads_complete[i],
+			      CLONE_KERNEL);
+	}
+	for (i = 0; i < thread; i++)
+		wait_for_completion(&threads_complete[i]);
+	atomic_set(&device_match_freezed, 0);
+	up(&sem_thaw);
+}
+
+static int __init dev_match_thread(char *str)
+{
+	get_option(&str, &dev_match_thread_default);
+	return 1;
+}
+
+__setup("dev_match_thread=", dev_match_thread);
+
+EXPORT_SYMBOL_GPL(device_match_freeze);
+EXPORT_SYMBOL_GPL(device_match_thaw);
Index: linux-2.6.22-rc4/include/linux/device.h
===================================================================
--- linux-2.6.22-rc4.orig/include/linux/device.h	2007-06-08
18:26:11.000000000 +0800
+++ linux-2.6.22-rc4/include/linux/device.h	2007-06-09
19:41:03.000000000 +0800
@@ -413,12 +413,17 @@
 	struct klist_node	knode_driver;
 	struct klist_node	knode_bus;
 	struct device		*parent;
+	struct device		*depend;
 
 	struct kobject kobj;
 	char	bus_id[BUS_ID_SIZE];	/* position on parent bus */
 	struct device_type	*type;
 	unsigned		is_registered:1;
 	unsigned		uevent_suppress:1;
+	unsigned		is_matched:1;
+	unsigned		is_checking:1;
+	unsigned		is_checked:1;
+	unsigned		singlethreaded_probe:1;
 	struct device_attribute uevent_attr;
 	struct device_attribute *devt_attr;
 
@@ -525,6 +530,8 @@
 extern int  __must_check device_attach(struct device * dev);
 extern int __must_check driver_attach(struct device_driver *drv);
 extern int __must_check device_reprobe(struct device *dev);
+extern void device_match_freeze(void);
+extern void device_match_thaw(int thread);
 
 /*
  * Easy functions for dynamically creating devices on the fly

Re: [PATCH] driver core: multithreaded device matching with dependency

[Stefan Richter]

Huang, Ying wrote:
> Can this mechanism solve the demand of IEEE1394 subsystem effectively?

Probably.  I don't know when I will have time to try it.

(BTW, we should actually be able to probe subunits in parallel, however
I suspect that some firmwares will not tolerate this.)

...
> +/**
> + *	device_match_thaw - renable device/driver matching and check all
> + *	pending device/driver matching.

This has to be a single line.

> + *	@thread: number of threads to do device/driver matching.
> + *
> + *	All devices are checked for driver matching, multithreaded

...
> +EXPORT_SYMBOL_GPL(device_match_freeze);
> +EXPORT_SYMBOL_GPL(device_match_thaw);

I don't know, perhaps names like "device_driver_matching_disable" and
"device_driver_matching_enable" would be more to the point.  Or do you
actually "freeze" (i.e. halt) ongoing driver probes?

> Index: linux-2.6.22-rc4/include/linux/device.h
> ===================================================================
> --- linux-2.6.22-rc4.orig/include/linux/device.h	2007-06-08
> 18:26:11.000000000 +0800
> +++ linux-2.6.22-rc4/include/linux/device.h	2007-06-09
> 19:41:03.000000000 +0800
> @@ -413,12 +413,17 @@
>  	struct klist_node	knode_driver;
>  	struct klist_node	knode_bus;
>  	struct device		*parent;
> +	struct device		*depend;

Is this core-internal now?  If not, add a comment what it does and how
it has to be written and read.

I'm curious how this has to be used; perhaps it will turn out that the
whole thing is over-engineered this way.  I.e. there might be easier
options like:
  - Let subsystems which don't want multithreaded probing at all
    disable multithreaded probing globally by a susbsystem flag.
    (Or rather, let subsystems which want multithreaded probing
    enable it globally by a subsystem flag. IOW make singlethreaded
    probing the default.  Multithreaded probing has to be tested
    thoroughly for each subsystem.)
  - Let subsystems which want only partially multithreaded probing
    serialize the necessary regions on their own by subsystem-internal
    mutexes.

However, this really depends on what the actual cost of dev->depend is.

>  	struct kobject kobj;
>  	char	bus_id[BUS_ID_SIZE];	/* position on parent bus */
>  	struct device_type	*type;
>  	unsigned		is_registered:1;
>  	unsigned		uevent_suppress:1;
> +	unsigned		is_matched:1;
> +	unsigned		is_checking:1;
> +	unsigned		is_checked:1;
> +	unsigned		singlethreaded_probe:1;
...

Ditto here:  Which of these belong to the public API?  Those flags which
are not private to the core need to be commented.

PS:  There is also a kerneldoc format for structs.  It also allows to
mark private struct members, i.e. those which do not belong to the API.
See Documentation/kernel-doc-nano-HOWTO.txt.

PPS:  Sadly, the whole struct device and some other driver core API
items lack kerneldocs.  It's ironic that the deprecated class_device is
the only drivercore struct which comes with a kerneldoc.
-- 
Stefan Richter
-=====-=-=== -==- -=--=
http://arcgraph.de/sr/

Re: [PATCH] driver core: multithreaded device matching with dependency

[Huang, Ying]

> > Index: linux-2.6.22-rc4/include/linux/device.h
> > ===================================================================
> > --- linux-2.6.22-rc4.orig/include/linux/device.h	2007-06-08
> > 18:26:11.000000000 +0800
> > +++ linux-2.6.22-rc4/include/linux/device.h	2007-06-09
> > 19:41:03.000000000 +0800
> > @@ -413,12 +413,17 @@
> >  	struct klist_node	knode_driver;
> >  	struct klist_node	knode_bus;
> >  	struct device		*parent;
> > +	struct device		*depend;
> 
> Is this core-internal now?  If not, add a comment what it does and how
> it has to be written and read.
> 
> I'm curious how this has to be used; perhaps it will turn out that the
> whole thing is over-engineered this way.  I.e. there might be easier
> options like:
>   - Let subsystems which don't want multithreaded probing at all
>     disable multithreaded probing globally by a susbsystem flag.
>     (Or rather, let subsystems which want multithreaded probing
>     enable it globally by a subsystem flag. IOW make singlethreaded
>     probing the default.  Multithreaded probing has to be tested
>     thoroughly for each subsystem.)
>   - Let subsystems which want only partially multithreaded probing
>     serialize the necessary regions on their own by subsystem-internal
>     mutexes.
> 
> However, this really depends on what the actual cost of dev->depend is.

Maybe it is a little over-engineered. I think it may be used for some
random dependency between devices. Such as in some embedded system, the
power of USB controller may be controlled by some GPIO, so the USB
controller driver should access the GPIO driver.

Now, I made the signalthreaded probing the default. But the probing of
different subsystems are still parallelized.

Thanks for your comments. There are many problems in my patch. But for
now, the feasibility may be the biggest problem. The patch can be seen
as the helper for my description.

The summary of dependency rule is as follow:

1. A flag as follow is added to struct device.
     unsigned multithreaded_probe:1;
If it is set, the devices sub-tree with this device as root will be
probed parallelized with other devices sub-tree. If it is clear, the
device belongs to the devices sub-tree of the parent of the device, and
should be probed serially with other devices in the devices sub-tree.
The root devices (without parent) is assumed to have this flag set (in
spite of the actual value). With this flag, the PCI subsystem can be
probed serially, while IEEE 1394 subsystem can be probed parallelized
among different device node, but serially among different unit in a
node.

2. A field as follow is added to struct device.
     struct device *depend;
The device will not start probing unless the probing of the device
pointed by depend has been finished. This is used to control some random
dependency between devices.

3. The probing of the device will not be started, unless the probing of
the parent of the device has been finished.

I revised my patch to reflect the rule above, so resend it.

 drivers/base/base.h    |    5 +
 drivers/base/core.c    |   35 +++++--
 drivers/base/dd.c      |  230 ++++++++++++++++++++++++++++++++++++++++++++++---
 include/linux/device.h |    7 +
 init/main.c            |    3 
 5 files changed, 259 insertions(+), 21 deletions(-)
Index: linux-2.6.22-rc4/init/main.c
===================================================================
--- linux-2.6.22-rc4.orig/init/main.c	2007-06-11 11:24:27.000000000 +0800
+++ linux-2.6.22-rc4/init/main.c	2007-06-11 11:25:07.000000000 +0800
@@ -652,6 +652,7 @@
 	initcall_t *call;
 	int count = preempt_count();
 
+	device_match_freeze();
 	for (call = __initcall_start; call < __initcall_end; call++) {
 		ktime_t t0, t1, delta;
 		char *msg = NULL;
@@ -703,6 +704,8 @@
 		}
 	}
 
+	device_match_thaw(0);
+
 	/* Make sure there is no pending stuff from the initcall sequence */
 	flush_scheduled_work();
 }
Index: linux-2.6.22-rc4/drivers/base/dd.c
===================================================================
--- linux-2.6.22-rc4.orig/drivers/base/dd.c	2007-06-11 11:24:27.000000000 +0800
+++ linux-2.6.22-rc4/drivers/base/dd.c	2007-06-11 21:51:06.000000000 +0800
@@ -25,6 +25,7 @@
 
 #define to_drv(node) container_of(node, struct device_driver, kobj.entry)
 
+static atomic_t device_match_freezed = ATOMIC_INIT(0);
 
 static void driver_bound(struct device *dev)
 {
@@ -220,6 +221,25 @@
 	return ret;
 }
 
+/* This function must be called with dev->sem held. */
+static inline int real_device_attach(struct device * dev)
+{
+	int ret = 0;
+
+	if (dev->driver) {
+		ret = device_bind_driver(dev);
+		if (ret == 0)
+			ret = 1;
+		else {
+			dev->driver = NULL;
+			ret = 0;
+		}
+	} else {
+		ret = bus_for_each_drv(dev->bus, NULL, dev, __device_attach);
+	}
+	return ret;
+}
+
 /**
  *	device_attach - try to attach device to a driver.
  *	@dev:	device.
@@ -238,18 +258,10 @@
 {
 	int ret = 0;
 
+	if (atomic_read(&device_match_freezed))
+		return 0;
 	down(&dev->sem);
-	if (dev->driver) {
-		ret = device_bind_driver(dev);
-		if (ret == 0)
-			ret = 1;
-		else {
-			dev->driver = NULL;
-			ret = 0;
-		}
-	} else {
-		ret = bus_for_each_drv(dev->bus, NULL, dev, __device_attach);
-	}
+	ret = real_device_attach(dev);
 	up(&dev->sem);
 	return ret;
 }
@@ -291,6 +303,8 @@
  */
 int driver_attach(struct device_driver * drv)
 {
+	if (atomic_read(&device_match_freezed))
+		return 0;
 	return bus_for_each_dev(drv->bus, NULL, drv, __driver_attach);
 }
 
@@ -380,3 +394,197 @@
 EXPORT_SYMBOL_GPL(device_attach);
 EXPORT_SYMBOL_GPL(driver_attach);
 
+#define to_dev(obj) container_of(obj, struct device, kobj)
+
+static void init_devices_check(void)
+{
+	struct kobject *kobj;
+	struct device *dev;
+
+	spin_lock(&devices_subsys.list_lock);
+	list_for_each_entry(kobj, &(devices_subsys.list), entry) {
+		dev = to_dev(kobj);
+		dev = get_device(dev);
+		dev->is_checked = 0;
+		dev->is_checking = 0;
+		put_device(dev);
+	}
+	spin_unlock(&devices_subsys.list_lock);
+}
+
+#define FIND_DEVICE_FOUND  1
+#define FIND_DEVICE_WAIT   2
+
+struct find_device_data
+{
+	struct device **pdev;
+	int result;
+};
+
+static int find_next_device_to_check_in_tree(struct device *dev,
+					     void *data)
+{
+	struct find_device_data *pfind = data;
+
+	get_device(dev);
+	if (dev->class)
+		;
+	else if (dev->is_checking)
+		pfind->result = FIND_DEVICE_WAIT;
+	else if (dev->is_matched || dev->is_checked)
+		device_for_each_child(dev, data,
+				      find_next_device_to_check_in_tree);
+	else if (dev->multithreaded_probe || !dev->parent) {
+		struct device *depend;
+
+		depend = get_device(dev->depend);
+		if (!depend || depend->is_matched || depend->is_checked) {
+			*pfind->pdev = dev;
+			get_device(dev);
+			pfind->result = FIND_DEVICE_FOUND;
+		} else
+			pfind->result = FIND_DEVICE_WAIT;
+		put_device(depend);
+	} else {
+		struct device *probe_root = dev;
+		while (probe_root->parent && !probe_root->multithreaded_probe)
+			probe_root = probe_root->parent;
+		if (probe_root->is_checking)
+			pfind->result = FIND_DEVICE_WAIT;
+		else {
+			pfind->result = FIND_DEVICE_FOUND;
+			get_device(probe_root);
+			*pfind->pdev = probe_root;
+		}
+	}
+	put_device(dev);
+	return pfind->result == FIND_DEVICE_FOUND;
+}
+
+static int find_next_device_to_check(struct device **pdev)
+{
+	struct find_device_data find;
+
+	find.pdev = pdev;
+	find.result = 0;
+	klist_for_each_child_device(&klist_root_devices, &find,
+				    find_next_device_to_check_in_tree);
+	return find.result;
+}
+
+static int check_device(struct device *dev, void *data)
+{
+	int ret;
+	int is_probe_root = !!data;
+
+	get_device(dev);
+	/* The dev is another probing root device */
+	if (!is_probe_root && dev->multithreaded_probe) {
+		put_device(dev);
+		return 0;
+	}
+	down(&dev->sem);
+	if (dev->is_checking) {
+		up(&dev->sem);
+		put_device(dev);
+		return 0;
+	}
+	if (is_probe_root)
+		dev->is_checking = 1;
+	if (!dev->is_checked && !dev->is_matched) {
+		dev->is_checking = 1;
+		pr_debug("dev: %s - begin\n", dev->bus_id);
+		ret = real_device_attach(dev);
+		pr_debug("dev: %s - end\n", dev->bus_id);
+		if (!is_probe_root)
+			dev->is_checking = 0;
+		dev->is_checked = 1;
+		dev->is_matched = (ret == 1);
+	}
+	up(&dev->sem);
+	device_for_each_child(dev, NULL, check_device);
+	if (is_probe_root)
+		dev->is_checking = 0;
+	put_device(dev);
+	return 0;
+}
+
+static int devices_check_thread(void *data)
+{
+	struct device *dev = NULL;
+	int result;
+	struct completion *thread_complete = data;
+
+	while ((result = find_next_device_to_check(&dev))) {
+		pr_debug("find %d, %s\n", result, dev ? dev->bus_id : NULL);
+		if (result == FIND_DEVICE_FOUND) {
+			check_device(dev, (void *)1);
+			put_device(dev);
+		} else
+			yield();
+	}
+	complete(thread_complete);
+	return 0;
+}
+
+/**
+ *	device_match_freeze - disable device/driver matching.
+ *
+ *	All subsequent device or driver registering will not trigger
+ *	device/driver matching until device_match_thaw is called.
+ */
+void device_match_freeze(void)
+{
+	atomic_set(&device_match_freezed, 1);
+}
+
+static int dev_match_thread_default = 1;
+
+/**
+ *	device_match_thaw - renable device/driver matching.
+ *	@thread: number of threads to do device/driver matching.
+ *
+ *	All devices are checked for driver matching, multithreaded matching
+ *	is used to accelerate matching process. The device/driver matching
+ *	is reenabled afterwards.
+ */
+void device_match_thaw(int thread)
+{
+	struct completion *threads_complete;
+	int i;
+	static DECLARE_MUTEX(sem_thaw);
+
+	down(&sem_thaw);
+	if (thread <= 0)
+		thread = dev_match_thread_default > 0 ? \
+			dev_match_thread_default : 1;
+	threads_complete = kmalloc(sizeof(struct completion) * thread,
+				   GFP_KERNEL);
+	init_devices_check();
+	for (i = 0; i < thread; i++) {
+		init_completion(&threads_complete[i]);
+		kernel_thread(devices_check_thread,
+			      &threads_complete[i],
+			      CLONE_KERNEL);
+	}
+	for (i = 0; i < thread; i++)
+		wait_for_completion(&threads_complete[i]);
+	atomic_set(&device_match_freezed, 0);
+	/* check again because drivers may be inserted during probing. */
+	init_devices_check();
+	init_completion(&threads_complete[0]);
+	devices_check_thread(&threads_complete[0]);
+	kfree(threads_complete);
+	up(&sem_thaw);
+}
+
+static int __init dev_match_thread(char *str)
+{
+	get_option(&str, &dev_match_thread_default);
+	return 1;
+}
+
+__setup("dev_match_thread=", dev_match_thread);
+
+EXPORT_SYMBOL_GPL(device_match_freeze);
+EXPORT_SYMBOL_GPL(device_match_thaw);
Index: linux-2.6.22-rc4/include/linux/device.h
===================================================================
--- linux-2.6.22-rc4.orig/include/linux/device.h	2007-06-11 11:24:27.000000000 +0800
+++ linux-2.6.22-rc4/include/linux/device.h	2007-06-11 11:25:07.000000000 +0800
@@ -413,12 +413,17 @@
 	struct klist_node	knode_driver;
 	struct klist_node	knode_bus;
 	struct device		*parent;
+	struct device		*depend;
 
 	struct kobject kobj;
 	char	bus_id[BUS_ID_SIZE];	/* position on parent bus */
 	struct device_type	*type;
 	unsigned		is_registered:1;
 	unsigned		uevent_suppress:1;
+	unsigned		is_matched:1;
+	unsigned		is_checking:1;
+	unsigned		is_checked:1;
+	unsigned		multithreaded_probe:1;
 	struct device_attribute uevent_attr;
 	struct device_attribute *devt_attr;
 
@@ -525,6 +530,8 @@
 extern int  __must_check device_attach(struct device * dev);
 extern int __must_check driver_attach(struct device_driver *drv);
 extern int __must_check device_reprobe(struct device *dev);
+extern void device_match_freeze(void);
+extern void device_match_thaw(int thread);
 
 /*
  * Easy functions for dynamically creating devices on the fly
Index: linux-2.6.22-rc4/drivers/base/core.c
===================================================================
--- linux-2.6.22-rc4.orig/drivers/base/core.c	2007-06-07 17:17:37.000000000 +0800
+++ linux-2.6.22-rc4/drivers/base/core.c	2007-06-11 11:25:07.000000000 +0800
@@ -635,6 +635,8 @@
 	return 0;
 }
 
+struct klist klist_root_devices;
+
 /**
  *	device_add - add device to device hierarchy.
  *	@dev:	device.
@@ -741,6 +743,8 @@
 	bus_attach_device(dev);
 	if (parent)
 		klist_add_tail(&dev->knode_parent, &parent->klist_children);
+	else
+		klist_add_tail(&dev->knode_parent, &klist_root_devices);
 
 	if (dev->class) {
 		down(&dev->class->sem);
@@ -975,6 +979,19 @@
 	return n ? container_of(n, struct device, knode_parent) : NULL;
 }
 
+int klist_for_each_child_device(struct klist * klist, void * data,
+				int (*fn)(struct device *, void *))
+{
+	struct klist_iter i;
+	struct device * child;
+	int error = 0;
+
+	klist_iter_init(klist, &i);
+	while ((child = next_device(&i)) && !error)
+		error = fn(child, data);
+	klist_iter_exit(&i);
+	return error;
+}
 /**
  *	device_for_each_child - device child iterator.
  *	@parent: parent struct device.
@@ -990,15 +1007,8 @@
 int device_for_each_child(struct device * parent, void * data,
 		     int (*fn)(struct device *, void *))
 {
-	struct klist_iter i;
-	struct device * child;
-	int error = 0;
-
-	klist_iter_init(&parent->klist_children, &i);
-	while ((child = next_device(&i)) && !error)
-		error = fn(child, data);
-	klist_iter_exit(&i);
-	return error;
+	return klist_for_each_child_device(&parent->klist_children,
+					   data, fn);
 }
 
 /**
@@ -1035,7 +1045,12 @@
 
 int __init devices_init(void)
 {
-	return subsystem_register(&devices_subsys);
+	int ret;
+
+	ret = subsystem_register(&devices_subsys);
+	klist_init(&klist_root_devices, klist_children_get,
+		   klist_children_put);
+	return ret;
 }
 
 EXPORT_SYMBOL_GPL(device_for_each_child);
Index: linux-2.6.22-rc4/drivers/base/base.h
===================================================================
--- linux-2.6.22-rc4.orig/drivers/base/base.h	2007-06-07 17:17:37.000000000 +0800
+++ linux-2.6.22-rc4/drivers/base/base.h	2007-06-11 11:25:07.000000000 +0800
@@ -47,3 +47,8 @@
 extern void devres_release_all(struct device *dev);
 
 extern struct kset devices_subsys;
+
+extern struct klist klist_root_devices;
+
+int klist_for_each_child_device(struct klist * klist, void * data,
+				int (*fn)(struct device *, void *));

Re: [PATCH] driver core: multithreaded device matching with dependency

[Stefan Richter]

Huang, Ying wrote:
> The summary of dependency rule is as follow:
> 
> 1. A flag as follow is added to struct device.
>      unsigned multithreaded_probe:1;
> If it is set, the devices sub-tree with this device as root will be
> probed parallelized with other devices sub-tree. If it is clear, the
> device belongs to the devices sub-tree of the parent of the device, and
> should be probed serially with other devices in the devices sub-tree.
> The root devices (without parent) is assumed to have this flag set (in
> spite of the actual value). With this flag, the PCI subsystem can be
> probed serially, while IEEE 1394 subsystem can be probed parallelized
> among different device node, but serially among different unit in a
> node.
> 
> 2. A field as follow is added to struct device.
>      struct device *depend;
> The device will not start probing unless the probing of the device
> pointed by depend has been finished. This is used to control some random
> dependency between devices.
> 
> 3. The probing of the device will not be started, unless the probing of
> the parent of the device has been finished.
> 
> I revised my patch to reflect the rule above, so resend it.

Looks good, except for two points, IMO:

  - I'd still like to see kerneldoc comments in your patch for each new
    API element.  You did so already for the new exported functions, but
    you didn't provide kerneldoc for the new members of struct device
    which are API elements.

    Of course, the whole struct device is /not/ quite well documented at
    the moment, but that doesn't mean that new extensions should make
    matters even worse.

  - Your rules 1 and 3 are simple and useful.  Rule 2 is in itself
    simple too, but the maintenance of the dependency tree which is
    built from the .depend pointers comes at a cost.  (Devices come and
    go all the time; the .depend pointers must always be valid.  How is
    this accomplished?)

    Consider to reduce your patch to rule 1 and 3, and throw out rule 2.
    If a subsystem has a more complicated requirement which cannot be
    satisfied by rule 1 and 3, it can either just restrict itself to
    dumb single-threaded device-driver matching, or it can pretend to be
    fully capable of parallel device-driver matching and ensure the
    necessary serialization by own internal mutexes.

There is so much unskilled labor in driver hacking land (I'm merely
speaking for myself of course) that something like the driver core
/really/ needs well-working, easy to understand, and well-documented APIs.

PS:  By a well-documented struct definition I mean:
   - Public members have a type and name which indicate the meaning of
     the member, and there is a comment on permissible or required
     write/read accesses to the member.
   - Private members are undocumented or even better yet explicitly
     marked as private.
If the access methods to public members turn out too difficult and
fragile, make the members private and provide documented public accessors.
-- 
Stefan Richter
-=====-=-=== -==- -==--
http://arcgraph.de/sr/

Re: [PATCH] driver core: multithreaded device matching with dependency

[Greg KH]

On Tue, Jun 12, 2007 at 04:30:57PM +0200, Stefan Richter wrote:
> 
> There is so much unskilled labor in driver hacking land (I'm merely
> speaking for myself of course) that something like the driver core
> /really/ needs well-working, easy to understand, and well-documented APIs.
> 
> PS:  By a well-documented struct definition I mean:
>    - Public members have a type and name which indicate the meaning of
>      the member, and there is a comment on permissible or required
>      write/read accesses to the member.
>    - Private members are undocumented or even better yet explicitly
>      marked as private.

We are slowly working toward this goal with the cleanups and work that
Kay has been doing over the past year.  So be patient, it is slowly
coming, or please help out if you can.

> If the access methods to public members turn out too difficult and
> fragile, make the members private and provide documented public accessors.

Well, let's not get into the whole "accessors are good/evil" type thread
here, but yes, we'll work to try to make this whole thing easier to use
and very hard to use incorrectly (which is not true today, I know,
sorry...)

thanks,

greg k-h