Multithread initcalls to auto-resolve ordering issues.

[ To: list stolen from "introduce External Connector Class (extcon)" thread
where this topic was briefly mentioned. ]

Hi,
I welcome review/feedback on the following idea and code.

The problem:

Many devices - particular platform devices - have dependencies on other devices. That is - they use a resource that another device provides. This includes (but it not limited to):
GPIOs
IRQs
Regulators
PWMs

The identity of the resource is usually passed to the dependent device via the platform_data. If the resource is not available, the device probe will either fail or will continue without the resource - neither of which are satisfactory.

Current approaches:

I am aware of two current approaches to ensuring that all dependencies are available when a device is probed:

1/ hand-tuning of the order of init calls, whether by reordering entries in
a Makefile or by using early_initcall or late_initcall.

This approach is not very transparent, and assumes that a single ordering of driver-initialisation can address all dependencies orderings.

2/ The use of 'setup' function such as e.g. drivers/gpio/gpio-pca953x.c
provides which can be used to add a device *after* the gpios are available.

This approach requires code in the 'board' file and so is not really compatible with the move to 'device tree'.
Also - many drives to not provide a setup callback.

Proposed solution:

The solution I am proposing is to:
1/ allow the 'request' functions which find and provide a resource to block
until the resource is available
2/ run the init calls in multiple threads so that when one blocks waiting
for a resource, another starts up to run subsequent initcalls until the blocking call gets its resource and can complete.

Details and issues.

1/ Sometimes it is appropriate to fail rather than to block, and a resource
providers need to know which.
This is unlikely to be an issue with GPIO and IRQ as is the identifying number is >= 0, then the resource must be expected at some stage. However for regulators a name is not given to the driver but rather the driver asks if a supply is available with a given name for the device. If not, it makes do without.
So for regulators (and probably other resources) we need to know what resources to expect so we know if a resource will never appear.

In this sample code I have added a call
regulator_has_full_constraints_listed()
which not only assures that all constraints are known, but list them (array of pointers to regulator_init_data) so when a supply is requested the regulator code can see if it expected.

2/ We probably don't want lots of threads running at once as there is
no good way to decide how many (maybe num_cpus??).
This patch takes the approach that only one thread should be runnable at once in most cases.

We keep a count of the number of threads started and the number of threads that are blocked, and only start a new thread when all threads are blocked, and only start a new initcall when all other threads are blocked.

So when one initcall makes a resource available, another thread which was waiting could wake up and both will run concurrently. However no more initcalls will start until all threads have completed or blocked.

3/ The parent locking that __driver_attach() does which is "Needed for USB"
was a little problem - I changed it to alert the initcall thread management so it knew that thread was blocking. I think this wouldn't be a problem is the parent lock was *only* taken for USB...

4/ It is possible that some existing code registers a resource before it is
really ready to be used. Currently that isn't a problem as no-one will actually try to use it until the initcall has completed. However with this patch the device that wants to use a resource can do so the moment it is registered.

This should probably be fixed by re-arranging the problematic code. However we could use a mutex (a bit like the old BKL) to ensure that only one initcall runs at a time, and any blocking initcall must wait for others to complete before it is allowed to run. I don't really like this approach and so haven't implemented it.

5/ This patch ensure that currently working code should keep working. It
only blocks if an expected resource isn't available yet, and anything that currently works must be getting things in the right order. Also, it only starts a second thread if something blocks and as nothing will block, it will run everything in one thread just as current code does.

6/ There is some ugliness in this code due to duplication. I think it could
be made a lot cleaner if every resource had a simple textual name. Then then the code for managing lists of expected resource and who is waiting for them could all be common.

7/ Ultimately I suspect (or hope) that the "device tree" could be used to
provide lists of all expected resources.

8/ This sample code only provides blocking for GPIO and REGULATOR resources
as that is all I needed - so that is all I could test.

I've been using this on my GTA04 which has an interesting dependencies where the WIFI - plugged into an MMC channels which is normally initialised quite early - depends on a regulator (which is initialised fairly early) and a GPIO on an I2C device (which is initialised quite late), and a virtual regulator which depends on the GPIO (for the 'enable' line) and the regulator (as the power source).

So it certainly solved my problem.

Thanks for your time.

NeilBrown

From 752e8a82aa4cee7040f5d6ad86de54ba3ec048af Mon Sep 17 00:00:00 2001
From: NeilBrown <[email protected]>
Date: Wed, 21 Dec 2011 10:15:51 +1100
Subject: [PATCH] Multi-threading initcall

Allow initcall functions to block waiting for resources, and for other initcall functions to then be run in separate threads.

Signed-off-by NeilBrown <[email protected]>

drivers/base/dd.c +1 -1

index 142e3d600..06963e4 100644
@@ -288,7 +288,7 @@ static int __driver_attach(struct device *dev, void *data)
 		return 0;
 
 	if (dev->parent)	/* Needed for USB */
-		device_lock(dev->parent);
+		initcall_lock(&dev->parent->mutex);
 	device_lock(dev);
 	if (!dev->driver)
 		driver_probe_device(drv, dev);

drivers/gpio/gpiolib.c +16 -0

index a971e3d..7d283af 100644
@@ -11,6 +11,7 @@
 #include <linux/of_gpio.h>
 #include <linux/idr.h>
 #include <linux/slab.h>
+#include <linux/sched.h>
 
 #define CREATE_TRACE_POINTS
 #include <trace/events/gpio.h>

@@ -58,6 +59,7 @@ struct gpio_desc {
 #define FLAG_TRIG_FALL	5	/* trigger on falling edge */
 #define FLAG_TRIG_RISE	6	/* trigger on rising edge */
 #define FLAG_ACTIVE_LOW	7	/* sysfs value has active low */
+#define FLAG_WAITING	8	/* Some initcall is waiting for this gpio */
 
 #define ID_SHIFT	16	/* add new flags before this one */
 

@@ -70,6 +72,13 @@ struct gpio_desc {
 };
 static struct gpio_desc gpio_desc[ARCH_NR_GPIOS];
 
+struct gpio_waiter {
+	struct list_head list;
+	int gpio;
+	wait_queue_head_t queue;
+};
+static LIST_HEAD(waiters);
+
 #ifdef CONFIG_GPIO_SYSFS
 static DEFINE_IDR(dirent_idr);
 #endif

@@ -1065,6 +1074,13 @@ int gpiochip_add(struct gpio_chip *chip)
 		for (id = base; id < base + chip->ngpio; id++) {
 			gpio_desc[id].chip = chip;
 
+			if (test_bit(FLAG_WAITING, &gpio_desc[id].flags)) {
+				struct gpio_waiter *w;
+				list_for_each_entry(w, &waiters, list)
+					if (w->gpio == id)
+						wake_up(&w->queue);
+			}
+
 			/* REVISIT:  most hardware initializes GPIOs as
 			 * inputs (often with pullups enabled) so power
 			 * usage is minimized.  Linux code should set the

drivers/gpio/gpiolib.c +27 -2

 	spin_lock_irqsave(&gpio_lock, flags);
 
 	if (!gpio_is_valid(gpio))
 		goto done;
 	desc = &gpio_desc[gpio];
+	if (desc->chip == NULL) {
+		/* possibly need to wait for the chip to appear */
+		struct gpio_waiter w;
+		int status2 = 0;
+		DEFINE_WAIT(wait);
+		if (test_and_set_bit(FLAG_WAITING, &desc->flags))
+			/* Only one waiter allowed */
+			goto done;
+		if (!can_wait)
+			goto done;
+
+		init_waitqueue_head(&w.queue);
+		w.gpio = gpio;
+		list_add(&w.list, &waiters);
+		prepare_to_wait(&w.queue, &wait, TASK_UNINTERRUPTIBLE);
+
+		while (desc->chip == NULL && status2 == 0) {
+			spin_unlock_irqrestore(&gpio_lock, flags);
+			status2 = initcall_schedule();
+			spin_lock_irqsave(&gpio_lock, flags);
+			prepare_to_wait(&w.queue, &wait, TASK_UNINTERRUPTIBLE);
+		}
+		finish_wait(&w.queue, &wait);
+		list_del(&w.list);
+		if (desc->chip == NULL)
+			goto done;
+	}
 	chip = desc->chip;
-	if (chip == NULL)
-		goto done;
 
 	if (!try_module_get(chip->owner))
 		goto done;

drivers/regulator/core.c +151 -13

index 938398f..0ec34f7 100644
@@ -68,6 +68,15 @@ struct regulator_map {
 	struct regulator_dev *regulator;
 };
 
+struct regulator_waiter {
+	struct list_head list;
+	const char *dev_name;
+	const char *supply;
+	const char *reg;
+	wait_queue_head_t queue;
+};
+static LIST_HEAD(waiters);
+
 /*
  * struct regulator
  *

@@ -961,6 +970,31 @@ static int set_supply(struct regulator_dev *rdev,
 	return 0;
 }
 
+static void regulator_wake_waiters(const char *devname, const char *id,
+	const char *reg)
+{
+	struct regulator_waiter *map;
+
+	list_for_each_entry(map, &waiters, list) {
+		if (map->reg) {
+			if (!reg)
+				continue;
+			if (strcmp(map->reg, reg) == 0)
+				wake_up(&map->queue);
+			continue;
+		}
+		if (reg)
+			continue;
+		/* If the mapping has a device set up it must match */
+		if (map->dev_name &&
+		    (!devname || strcmp(map->dev_name, devname)))
+			continue;
+
+		if (strcmp(map->supply, id) == 0)
+			wake_up(&map->queue);
+	}
+}
+
 /**
  * set_consumer_device_supply - Bind a regulator to a symbolic supply
  * @rdev:         regulator source

@@ -1031,6 +1065,7 @@ static int set_consumer_device_supply(struct regulator_dev *rdev,
 	}
 
 	list_add(&node->list, &regulator_map_list);
+	regulator_wake_waiters(node->dev_name, node->supply, NULL);
 	return 0;
 }
 

@@ -1148,12 +1183,29 @@ static int _regulator_get_enable_time(struct regulator_dev *rdev)
 	return rdev->desc->ops->enable_time(rdev);
 }
 
+static struct regulator_dev *regulator_find(const char *devname, const char *id)
+{
+	struct regulator_map *map;
+
+	list_for_each_entry(map, &regulator_map_list, list) {
+		/* If the mapping has a device set up it must match */
+		if (map->dev_name &&
+		    (!devname || strcmp(map->dev_name, devname)))
+			continue;
+
+		if (strcmp(map->supply, id) == 0)
+			return map->regulator;
+	}
+	return NULL;
+}
+
+static int regulator_expected(const char *reg);
+static int regulator_supply_expected(const char *devname, const char *id);
 /* Internal regulator request function */
 static struct regulator *_regulator_get(struct device *dev, const char *id,
 					int exclusive)
 {
 	struct regulator_dev *rdev;
-	struct regulator_map *map;
 	struct regulator *regulator = ERR_PTR(-ENODEV);
 	const char *devname = NULL;
 	int ret;

@@ -1168,17 +1220,9 @@ static struct regulator *_regulator_get(struct device *dev, const char *id,
 
 	mutex_lock(&regulator_list_mutex);
 
-	list_for_each_entry(map, &regulator_map_list, list) {
-		/* If the mapping has a device set up it must match */
-		if (map->dev_name &&
-		    (!devname || strcmp(map->dev_name, devname)))
-			continue;
-
-		if (strcmp(map->supply, id) == 0) {
-			rdev = map->regulator;
-			goto found;
-		}
-	}
+	rdev = regulator_find(devname, id);
+	if (rdev)
+		goto found;
 
 	if (board_wants_dummy_regulator) {
 		rdev = dummy_regulator_rdev;

@@ -1200,6 +1244,30 @@ static struct regulator *_regulator_get(struct device *dev, const char *id,
 	}
 #endif
 
+	if (regulator_supply_expected(devname, id)) {
+		/* wait for it to appear */
+		struct regulator_waiter w;
+		int status = 0;
+		DEFINE_WAIT(wait);
+		init_waitqueue_head(&w.queue);
+		w.dev_name = devname;
+		w.supply = id;
+		w.reg = NULL;
+		list_add(&w.list, &waiters);
+		prepare_to_wait(&w.queue, &wait, TASK_UNINTERRUPTIBLE);
+		while ((rdev = regulator_find(devname, id)) == NULL &&
+		       status == 0) {
+			mutex_unlock(&regulator_list_mutex);
+			status = initcall_schedule();
+			mutex_lock(&regulator_list_mutex);
+			prepare_to_wait(&w.queue, &wait, TASK_UNINTERRUPTIBLE);
+		}
+		finish_wait(&w.queue, &wait);
+		list_del(&w.list);
+		if (rdev)
+			goto found;
+	}
+
 	mutex_unlock(&regulator_list_mutex);
 	return regulator;
 

@@ -2728,7 +2796,33 @@ struct regulator_dev *regulator_register(struct regulator_desc *regulator_desc,
 				break;
 			}
 		}
-
+		if (!found && regulator_expected(init_data->supply_regulator)) {
+			struct regulator_waiter w;
+			int status = 0;
+			DEFINE_WAIT(wait);
+			init_waitqueue_head(&w.queue);
+			w.reg = init_data->supply_regulator;
+			w.dev_name = w.supply = NULL;
+			list_add(&w.list, &waiters);
+			prepare_to_wait(&w.queue, &wait, TASK_UNINTERRUPTIBLE);
+			while (status == 0) {
+				list_for_each_entry(r, &regulator_list, list) {
+					if (strcmp(rdev_get_name(r),
+						   init_data->supply_regulator) == 0) {
+						found = 1;
+						break;
+					}
+				}
+				if (found)
+					break;
+				mutex_unlock(&regulator_list_mutex);
+				status = initcall_schedule();
+				mutex_lock(&regulator_list_mutex);
+				prepare_to_wait(&w.queue, &wait, TASK_UNINTERRUPTIBLE);
+			}
+			finish_wait(&w.queue, &wait);
+			list_del(&w.list);
+		}
 		if (!found) {
 			dev_err(dev, "Failed to find supply %s\n",
 				init_data->supply_regulator);

@@ -2755,6 +2849,7 @@ struct regulator_dev *regulator_register(struct regulator_desc *regulator_desc,
 	}
 
 	list_add(&rdev->list, &regulator_list);
+	regulator_wake_waiters(NULL, NULL, rdev_get_name(rdev));
 
 	rdev_init_debugfs(rdev);
 out:

@@ -2897,6 +2992,49 @@ void regulator_has_full_constraints(void)
 }
 EXPORT_SYMBOL_GPL(regulator_has_full_constraints);
 
+static struct regulator_init_data **init_data_list;
+void regulator_has_full_constraints_listed(struct regulator_init_data **dlist)
+{
+	has_full_constraints = 1;
+	init_data_list = dlist;
+}
+
+static int regulator_supply_expected(const char *devname, const char *id)
+{
+	int i;
+
+	if (!init_data_list)
+		return 0;
+	for (i = 0; init_data_list[i]; i++) {
+		struct regulator_init_data *d = init_data_list[i];
+		struct regulator_consumer_supply *cs = d->consumer_supplies;
+		int s;
+		for (s = 0; s < d->num_consumer_supplies; s++) {
+			if (cs[s].dev_name &&
+			    (!devname || strcmp(cs[s].dev_name, devname)))
+				continue;
+			if (strcmp(cs[s].supply, id) == 0)
+				return 1;
+		}
+	}
+	return 0;
+}
+
+static int regulator_expected(const char *reg)
+{
+	int i;
+
+	if (!init_data_list)
+		return 0;
+	for (i = 0; init_data_list[i]; i++) {
+		struct regulator_init_data *d = init_data_list[i];
+		if (d->constraints.name &&
+		    strcmp(d->constraints.name, reg) == 0)
+			return 1;
+	}
+	return 0;
+}
+
 /**
  * regulator_use_dummy_regulator - Provide a dummy regulator when none is found
  *

include/linux/init.h +12 -0

index 9146f39..e898afe 100644
@@ -158,6 +158,18 @@ extern void (*late_time_init)(void);
 
 extern int initcall_debug;
 
+
+#ifdef MODULE
+static inline int initcall_schedule(void)
+{
+	return -1;
 
+}
 
+#else
+extern int initcall_schedule(void);
+struct mutex;
+extern void initcall_lock(struct mutex *);
+#endif
+
 #endif

#ifndef MODULE

include/linux/regulator/machine.h +5 -1

index f3f13fd..e78def2 100644
@@ -191,12 +191,16 @@ int regulator_suspend_finish(void);
 
 #ifdef CONFIG_REGULATOR
 void regulator_has_full_constraints(void);
+void regulator_has_full_constraints_listed(struct regulator_init_data **);
 void regulator_use_dummy_regulator(void);
 #else
 static inline void regulator_has_full_constraints(void)
 {
 }
-
+static inline void regulator_has_full_constraints_listed(
+	struct regulator_init_data *)
+{
+}
 static inline void regulator_use_dummy_regulator(void)
 {
 }

init/main.c +103 -3

index 217ed23..6cb2239 100644
@@ -710,12 +710,112 @@ int __init_or_module do_one_initcall(initcall_t fn)
 
 extern initcall_t __initcall_start[], __initcall_end[], __early_initcall_end[];
 
+
+static struct initcall_state {
+	initcall_t	*next_call;
+	atomic_t	threads, waiting;
+	wait_queue_head_t queue;
+	int		master_thread;
+} initcall;
+
+int initcall_schedule(void)
+{
+	/* Some probe function needs to wait for a pre-requisite
+	 * initcall to provide some resource.    A wakeup has already
+	 * been arranged for when it arrives.
+	 */
+	if (!initcall.master_thread)
+		return -ENODEV;
+
+	atomic_inc(&initcall.waiting);
+	/* Might need to start a new thread */
+	wake_up(&initcall.queue);
+
+	schedule();
+
+	atomic_dec(&initcall.waiting);
+	/* Might be time to progress to next initcall */
+	wake_up(&initcall.queue);
+
+	return 0;
+}
+
+void initcall_lock(struct mutex *mutex)
+{
+	if (!initcall.master_thread) {
+		mutex_lock(mutex);
+		return;
+	}
+	if (mutex_trylock(mutex))
+		return;
+
+	atomic_inc(&initcall.waiting);
+	/* Might need to start a new thread */
+	wake_up(&initcall.queue);
+
+	mutex_lock(mutex);
+
+	atomic_dec(&initcall.waiting);
+	/* Might be time to progress to next initcall */
+	wake_up(&initcall.queue);
+}
+
+static int init_caller(void *vtnum)
+{
+	unsigned long tnum = (unsigned long)vtnum;
+
+	/* Both next_call and master_thread can only be changed
+	 * when all other threads are waiting, so there is no
+	 * race here.
+	 */
+	while (initcall.next_call < __initcall_end
+	       && initcall.master_thread == tnum) {
+		initcall_t fn;
+
+		/* Don't want to proceed while other threads are
+		 * running.
+		 */
+		wait_event(initcall.queue,
+			   atomic_read(&initcall.threads)
+			   == atomic_read(&initcall.waiting)+1);
+
+		fn = *initcall.next_call;
+		initcall.next_call++;
+
+		do_one_initcall(fn);
+	}
+	atomic_dec(&initcall.threads);
+	wake_up(&initcall.queue);
+	return 0;
+}
+
 static void __init do_initcalls(void)
 {
-	initcall_t *fn;
+	DEFINE_WAIT(wait);
 
-	for (fn = __early_initcall_end; fn < __initcall_end; fn++)
-		do_one_initcall(*fn);
+	initcall.next_call = __early_initcall_end;
+
+	init_waitqueue_head(&initcall.queue);
+
+	while (1) {
+		prepare_to_wait(&initcall.queue, &wait, TASK_UNINTERRUPTIBLE);
+
+		if (initcall.next_call == __initcall_end)
+			break;
+
+		if (atomic_read(&initcall.threads)
+		    == atomic_read(&initcall.waiting)) {
+			/* All threads are waiting, create a new master */
+			initcall.master_thread++;
+			atomic_inc(&initcall.threads);
+			kernel_thread(init_caller,
+				      (void*)initcall.master_thread, 0);
+		}
+		schedule();
+	}
+	finish_wait(&initcall.queue, &wait);
+	wait_event(initcall.queue, atomic_read(&initcall.threads) == 0);
+	initcall.master_thread = 0;
 }
 
 /*

Quoted 4 lines · NeilBrown

[ To: list stolen from "introduce External Connector Class (extcon)" thread
where this topic was briefly mentioned. ]

Quoted 2 lines

Hi,
I welcome review/feedback on the following idea and code.

Hi Neil,

Interesting idea, some comments below.

Quoted 8 lines

Proposed solution:

The solution I am proposing is to:
1/ allow the 'request' functions which find and provide a resource to block
until the resource is available
2/ run the init calls in multiple threads so that when one blocks waiting
for a resource, another starts up to run subsequent initcalls until the blocking call gets its resource and can complete.

What happens if the resource isn't actually present (driver/hardware missing or resource probe fails for example)? Does the initcall thread get stuck forever, or is there a timeout?

Quoted 19 lines

Details and issues.

1/ Sometimes it is appropriate to fail rather than to block, and a resource
providers need to know which.
This is unlikely to be an issue with GPIO and IRQ as is the identifying number is >= 0, then the resource must be expected at some stage. However for regulators a name is not given to the driver but rather the driver asks if a supply is available with a given name for the device. If not, it makes do without.
So for regulators (and probably other resources) we need to know what resources to expect so we know if a resource will never appear.

In this sample code I have added a call
regulator_has_full_constraints_listed()
which not only assures that all constraints are known, but list them (array of pointers to regulator_init_data) so when a supply is requested the regulator code can see if it expected.

Quoted 4 lines

2/ We probably don't want lots of threads running at once as there is
no good way to decide how many (maybe num_cpus??).
This patch takes the approach that only one thread should be runnable at once in most cases.

num_cpus won't work for UP systems. In practice the number of threads needed is probably low, since most devices probably only have a short dependency chain.

Quoted 10 lines

We keep a count of the number of threads started and the number of threads that are blocked, and only start a new thread when all threads are blocked, and only start a new initcall when all other threads are blocked.

So when one initcall makes a resource available, another thread which was waiting could wake up and both will run concurrently. However no more initcalls will start until all threads have completed or blocked.

With this approach having an unbounded number of threads should be okay right? The number of threads shouldn't exceed the length of a dependency chain.

Quoted 11 lines

3/ The parent locking that __driver_attach() does which is "Needed for USB"
was a little problem - I changed it to alert the initcall thread management so it knew that thread was blocking. I think this wouldn't be a problem is the parent lock was *only* taken for USB...

4/ It is possible that some existing code registers a resource before it is
really ready to be used. Currently that isn't a problem as no-one will actually try to use it until the initcall has completed. However with this patch the device that wants to use a resource can do so the moment it is registered.

Such code would be buggy and need fixing correct? This patch could possibly help identify such buggy code?

drivers/gpio/gpiolib.c int gpio_request(unsigned gpio, const char *label) · line 1198

Quoted 5 lines

drivers/gpio/gpiolib.c +1 -0

@@ -1179,15 +1195,41 @@ int gpio_request(unsigned gpio, const char *label)
 	struct gpio_chip	*chip;
 	int			status = -EINVAL;
 	unsigned long		flags;
+	int			can_wait = !in_atomic();

I don't think you can reliably do this. Callers should always track whether they can sleep or not. See: http://lwn.net/Articles/274695/

Quoted 40 lines

drivers/gpio/gpiolib.c +27 -2

 	spin_lock_irqsave(&gpio_lock, flags);
 
 	if (!gpio_is_valid(gpio))
 		goto done;
 	desc = &gpio_desc[gpio];
+	if (desc->chip == NULL) {
+		/* possibly need to wait for the chip to appear */
+		struct gpio_waiter w;
+		int status2 = 0;
+		DEFINE_WAIT(wait);
+		if (test_and_set_bit(FLAG_WAITING, &desc->flags))
+			/* Only one waiter allowed */
+			goto done;
+		if (!can_wait)
+			goto done;
+
+		init_waitqueue_head(&w.queue);
+		w.gpio = gpio;
+		list_add(&w.list, &waiters);
+		prepare_to_wait(&w.queue, &wait, TASK_UNINTERRUPTIBLE);
+
+		while (desc->chip == NULL && status2 == 0) {
+			spin_unlock_irqrestore(&gpio_lock, flags);
+			status2 = initcall_schedule();
+			spin_lock_irqsave(&gpio_lock, flags);
+			prepare_to_wait(&w.queue, &wait, TASK_UNINTERRUPTIBLE);
+		}
+		finish_wait(&w.queue, &wait);
+		list_del(&w.list);
+		if (desc->chip == NULL)
+			goto done;
+	}
 	chip = desc->chip;
-	if (chip == NULL)
-		goto done;
 
 	if (!try_module_get(chip->owner))
 		goto done;

Quoted 6 lines · On Mon, 09 Jan 2012 12:05:28 +1100 Ryan Mallon <[email protected]> wrote:

Quoted 4 lines · NeilBrown

[ To: list stolen from "introduce External Connector Class (extcon)" thread
where this topic was briefly mentioned. ]

Quoted 8 lines

Quoted 2 lines

Hi,
I welcome review/feedback on the following idea and code.

Hi Neil,

Interesting idea, some comments below.

Thanks for the quick review!

Quoted 9 lines

Quoted 8 lines

Proposed solution:

The solution I am proposing is to:
1/ allow the 'request' functions which find and provide a resource to block
until the resource is available
2/ run the init calls in multiple threads so that when one blocks waiting
for a resource, another starts up to run subsequent initcalls until the blocking call gets its resource and can complete.

Quoted 3 lines

What happens if the resource isn't actually present (driver/hardware missing or resource probe fails for example)? Does the initcall thread get stuck forever, or is there a timeout?

With my code it will get stuck forever.
What is the alternative? Just fail?

Is this a realistic scenario? If it is we would probably need some way to say "this resource is no longer expected" .. sounds messy.

Quoted 26 lines

Quoted 20 lines

Details and issues.

1/ Sometimes it is appropriate to fail rather than to block, and a resource
providers need to know which.
This is unlikely to be an issue with GPIO and IRQ as is the identifying number is >= 0, then the resource must be expected at some stage. However for regulators a name is not given to the driver but rather the driver asks if a supply is available with a given name for the device. If not, it makes do without.
So for regulators (and probably other resources) we need to know what resources to expect so we know if a resource will never appear.

In this sample code I have added a call
regulator_has_full_constraints_listed()
which not only assures that all constraints are known, but list them (array of pointers to regulator_init_data) so when a supply is requested the regulator code can see if it expected.

Quoted 4 lines

2/ We probably don't want lots of threads running at once as there is
no good way to decide how many (maybe num_cpus??).
This patch takes the approach that only one thread should be runnable at once in most cases.

Quoted 3 lines

num_cpus won't work for UP systems. In practice the number of threads needed is probably low, since most devices probably only have a short dependency chain.

My reference to "num_cpus" was for how many threads should be runnable concurrently (rather than blocking on something) so a value of '1' would be OK and is what I (mostly) impose with the current code.

The total number of threads created with be the number of devices that are dependent on something later in the default initcall order. So it could be longer than the longest chain if there are multiple long chains that all block at once. It could likely be a few, quite possibly be dozens, very unlikely to be hundreds unless you really had lots and lots of devices.

Quoted 31 lines

Quoted 4 lines

Quoted 8 lines

We keep a count of the number of threads started and the number of threads that are blocked, and only start a new thread when all threads are blocked, and only start a new initcall when all other threads are blocked.

So when one initcall makes a resource available, another thread which was waiting could wake up and both will run concurrently. However no more initcalls will start until all threads have completed or blocked.

With this approach having an unbounded number of threads should be okay right? The number of threads shouldn't exceed the length of a dependency chain.

Quoted 11 lines

3/ The parent locking that __driver_attach() does which is "Needed for USB"
was a little problem - I changed it to alert the initcall thread management so it knew that thread was blocking. I think this wouldn't be a problem is the parent lock was *only* taken for USB...

4/ It is possible that some existing code registers a resource before it is
really ready to be used. Currently that isn't a problem as no-one will actually try to use it until the initcall has completed. However with this patch the device that wants to use a resource can do so the moment it is registered.

Quoted 2 lines

Such code would be buggy and need fixing correct? This patch could possibly help identify such buggy code?

Probably. When drivers are built as modules the initcalls can already run in parallel so getting the setup wrong could conceivably be an issue already - but yes, I think this patch could make those bugs more obvious.

As an example of something that might be a bug (And I had to look hard to find it), in gpio-pl061.c in the _probe function it calls:

		set_irq_flags(i+chip->irq_base, IRQF_VALID);
		irq_set_chip_data(i + chip->irq_base, chip);

Now I haven't set up any code for blocking when IRQs aren't available yet, but I suspect that the point they become available is when set_irq_flags is called to set IRQF_VALID. If some other driver immediately tired to use that irq it would find that the ->chip_data is NULL. e.g. it could call pl061_irq_enable() which immediately gets the chip_data and dereferences it.

Quoted 9 lines

drivers/gpio/gpiolib.c int gpio_request(unsigned gpio, const char *label) · line 1198

Quoted 5 lines

drivers/gpio/gpiolib.c +1 -0

@@ -1179,15 +1195,41 @@ int gpio_request(unsigned gpio, const char *label)
 	struct gpio_chip	*chip;
 	int			status = -EINVAL;
 	unsigned long		flags;
+	int			can_wait = !in_atomic();

I don't think you can reliably do this. Callers should always track whether they can sleep or not. See: http://lwn.net/Articles/274695/

Undoubtedly true. I'm not even sure that gpio_request can be called from atomic context, but as spin_lock_irqsave was used (below) instead of spin_lock_irq, I thought it safest to test.

If this gets past the initial review stage I'm sure I'll get help from someone how knows this code to make it right.

The solution I am proposing is to:
1/ allow the 'request' functions which find and provide a resource to block
until the resource is available
2/ run the init calls in multiple threads so that when one blocks waiting
for a resource, another starts up to run subsequent initcalls until the blocking call gets its resource and can complete.

In this sample code I have added a call
regulator_has_full_constraints_listed()
which not only assures that all constraints are known, but list them (array of pointers to regulator_init_data) so when a supply is requested the regulator code can see if it expected.

Quoted 6 lines · NeilBrown

The solution I am proposing is to:
1/ allow the 'request' functions which find and provide a resource to block
until the resource is available
2/ run the init calls in multiple threads so that when one blocks waiting
for a resource, another starts up to run subsequent initcalls until the blocking call gets its resource and can complete.

It seems like the end result of this is very similar to the idea of retrying. What are the advantages and disadvantages of the two approaches? My first thought is that retrying is going to give more consistent results between boots but is probably going to take more work (depending on how much context switches end up costing).

Looking at what you've done to the regulators code wise this all looks rather more complicated than I'm entirely happy with - I'm having to think far too much about locking and concurrency - and this work is going to need to be duplicated in every subsystem that is affected. I think if we're going to do this we'd need some common infrastructure to manage the actual waiting and waking to simplify implementation.

It also seems like there's no control given to drivers, everything is done in the frameworks. This means that drivers can't take decisions about what to do which seems like something that ought to be possible.

I'd like to see some way of enumerating what's waiting for what to help people figure out what's going wrong when things fail.

Quoted 6 lines

In this sample code I have added a call
regulator_has_full_constraints_listed()
which not only assures that all constraints are known, but list them (array of pointers to regulator_init_data) so when a supply is requested the regulator code can see if it expected.

This seems pretty restrictive to be honest. It isn't going to work if we don't know which regulators are in the system before we start enumerating which isn't going to be possible when dealing with modular systems that we can enumerate at runtime. It seems like we're taking most of the cost of fully ordering everything in data but still doing some things dynamically here.

It also seems inelegant in that we're having to pass all the constraints both via this and via the normal probe mechanism. If we were going to do this we'd be better off changing the way that regulators find their constraints so they aren't passed in through the driver as it probes.

drivers/regulator/core.c static int set_supply(struct regulator_dev *rdev, · line 974

Quoted 2 lines

drivers/regulator/core.c +2 -0

+static void regulator_wake_waiters(const char *devname, const char *id,
+	const char *reg)

I've no idea what "const char *reg" is...

Quoted 10 lines

drivers/regulator/core.c +9 -0

+{
+	struct regulator_waiter *map;
+
+	list_for_each_entry(map, &waiters, list) {
+		if (map->reg) {
+			if (!reg)
+				continue;
+			if (strcmp(map->reg, reg) == 0)
+				wake_up(&map->queue);

drivers/regulator/core.c static int set_supply(struct regulator_dev *rdev, · line 987

Quoted 4 lines

drivers/regulator/core.c +4 -0

+			continue;
+		}
+		if (reg)
+			continue;

...as a result I don't really know what this is intended to do. It does seem like this and the second half of the function are two separate functions that have been joined together.

drivers/regulator/core.c static struct regulator *_regulator_get(struct device *dev, const char *id, · line 1252

Quoted 7 lines

drivers/regulator/core.c +6 -0

+	if (regulator_supply_expected(devname, id)) {
+		/* wait for it to appear */
+		struct regulator_waiter w;
+		int status = 0;
+		DEFINE_WAIT(wait);
+		init_waitqueue_head(&w.queue);

I rather suspect this is going be able to deadlock if a PMIC supplies itself (which is not unknown - use a high efficiency convertor to drop down the system supply to a lower voltage and then lower efficiency convertors to give a series of lower voltages, giving greater overall efficiency). If the PMIC registers things in the wrong order then it'll never get as far as trying to register the parent regulator as the child regulator will block. We'd need to create a thread per regulator being registered. A similar issue applies with the retry based approach of course.

drivers/regulator/core.c struct regulator_dev *regulator_register(struct regulator_desc *regulator_desc, · line 2803

Quoted 6 lines

drivers/regulator/core.c +5 -0

+		if (!found && regulator_expected(init_data->supply_regulator)) {
+			struct regulator_waiter w;
+			int status = 0;
+			DEFINE_WAIT(wait);
+			init_waitqueue_head(&w.queue);

Seems like there's some code needs to be shared.

drivers/regulator/core.c void regulator_has_full_constraints(void) · line 3028

Quoted 6 lines

drivers/regulator/core.c +6 -0

+static int regulator_expected(const char *reg)
+{
+	int i;
+
+	if (!init_data_list)
+		return 0;

It looks like these tests for init_data_list are the wrong way around, if we don't know if we can fail then surely we always have to block on the off chance that the resource will appear?

drivers/regulator/core.c void regulator_has_full_constraints(void) · line 3033

Quoted 6 lines

drivers/regulator/core.c +5 -0

+	for (i = 0; init_data_list[i]; i++) {
+		struct regulator_init_data *d = init_data_list[i];
+		if (d->constraints.name &&
+		    strcmp(d->constraints.name, reg) == 0)
+			return 1;

This is really bad, the names in the constraints are optional and we should never rely on having them. Note that we never look directly at the name in the bulk of the code.

On Sun, 8 Jan 2012 20:08:02 -0800 Mark Brown

That and the fact that code can run in parallel are the only real differences I think.

Quoted 6 lines

Looking at what you've done to the regulators code wise this all looks rather more complicated than I'm entirely happy with - I'm having to think far too much about locking and concurrency - and this work is going to need to be duplicated in every subsystem that is affected. I think if we're going to do this we'd need some common infrastructure to manage the actual waiting and waking to simplify implementation.

Completely agree. I think the key simplification would be for each resource to have a simple textual name. Then you could write more common infrastructure.

Quoted 3 lines

It also seems like there's no control given to drivers, everything is done in the frameworks. This means that drivers can't take decisions about what to do which seems like something that ought to be possible.

Maybe a non-blocking form of the 'request' function so a driver can choose whether a not-available-yet-but-still-expected resource should be waited for
or should return -EAGAIN? There is certainly precedent for that sort of
control.
Or is there something else you think might be needed?

A/ assume it will never be available and continue as best we can, which
might mean failure.
B/ wait indefinitely until it available.
C/ find out if it could ever become available and then go to either A or B. D/ wait a while and then go to either A or B
E/ set up a callback so we can notified if/when the resource is available
at which point we integrate it and improve functionality.

Are there others?
Current code does 'A'.

I first tried B but found that devices often ask for regulators that will never appear, so that didn't work.

So I went for C which I agree is a little inelegant and I now see doesn't handle cases where some dependencies may or may exist depending on the current hardware.

'E' would be ideal in some sense, but could result in some rather complex code that never gets tested. Maybe with good design and infrastructure it could be made to work. 'C' might be a useful step towards that.

Quoted 9 lines

It also seems inelegant in that we're having to pass all the constraints both via this and via the normal probe mechanism. If we were going to do this we'd be better off changing the way that regulators find their constraints so they aren't passed in through the driver as it probes.

drivers/regulator/core.c static int set_supply(struct regulator_dev *rdev, · line 974

Quoted 2 lines

drivers/regulator/core.c +2 -0

+static void regulator_wake_waiters(const char *devname, const char *id,
+	const char *reg)

I've no idea what "const char *reg" is...

It is the name of a regulator...

There are two ways that you can ask for a regulator.
You can ask for it by device+supply (which is what normal devices ask for) or you can ask for it by regulator-name (which is what a regulator asks for when it is being supplied by some upstream regulator).

So there really are two separate lookup functions here - one to look up by device+supply (aka devname+id) and one to look up by regulator name.

Quoted 8 lines

drivers/regulator/core.c static struct regulator *_regulator_get(struct device *dev, const char *id, · line 1252

Quoted 6 lines

drivers/regulator/core.c +6 -0

+	if (regulator_supply_expected(devname, id)) {
+		/* wait for it to appear */
+		struct regulator_waiter w;
+		int status = 0;
+		DEFINE_WAIT(wait);
+		init_waitqueue_head(&w.queue);

I rather suspect this is going be able to deadlock if a PMIC supplies

Quoted 8 lines

itself (which is not unknown - use a high efficiency convertor to drop down the system supply to a lower voltage and then lower efficiency convertors to give a series of lower voltages, giving greater overall efficiency). If the PMIC registers things in the wrong order then it'll never get as far as trying to register the parent regulator as the child regulator will block. We'd need to create a thread per regulator being registered. A similar issue applies with the retry based approach of course.

Is this just a case of "Doctor, it hurts when I do this"?
i.e. if a PMIC could supply itself, it must register the possible-upstream regulator before requesting supply for the possible-downstream regulator.

You would need that for current code to work anyway.

Quoted 10 lines

drivers/regulator/core.c void regulator_has_full_constraints(void) · line 3028

Quoted 6 lines

drivers/regulator/core.c +6 -0

+static int regulator_expected(const char *reg)
+{
+	int i;
+
+	if (!init_data_list)
+		return 0;

It looks like these tests for init_data_list are the wrong way around, if we don't know if we can fail then surely we always have to block on the off chance that the resource will appear?

My reasoning was that if the init_data_list hadn't been provided, then the board still worked the "old" way by depending on the order of initcall listing.

Remember that threading will only be used by new boards that request it (implicitly) by declaring devices with difficult dependencies.

Quoted 9 lines

drivers/regulator/core.c void regulator_has_full_constraints(void) · line 3033

Quoted 5 lines

drivers/regulator/core.c +5 -0

+	for (i = 0; init_data_list[i]; i++) {
+		struct regulator_init_data *d = init_data_list[i];
+		if (d->constraints.name &&
+		    strcmp(d->constraints.name, reg) == 0)
+			return 1;

This is really bad, the names in the constraints are optional and we should never rely on having them. Note that we never look directly at the name in the bulk of the code.

Understood ... though not sure why we have the name if it is optional...

Quoted 4 lines · NeilBrown

On Sun, 8 Jan 2012 20:08:02 -0800 Mark Brown

That and the fact that code can run in parallel are the only real differences I think.

So, my general inclination is that given the choice between parallel and serial solutions I'll prefer the serial solution on the basis that it's most likely going to be easier to think about and less prone to getting messed up.

Quoted 3 lines

Completely agree. I think the key simplification would be for each resource to have a simple textual name. Then you could write more common infrastructure.

That's pretty much the case already for most things - the cannonical thing is to look up by (struct device, string). Squashing everything into a single flat namespace is painful as completely unrelated bits of the system easily collide with each other. GPIO and IRQ are the only holdouts I can think of in this area.

Quoted 4 lines

Quoted 4 lines

It also seems like there's no control given to drivers, everything is done in the frameworks. This means that drivers can't take decisions about what to do which seems like something that ought to be possible.

Quoted 5 lines

Maybe a non-blocking form of the 'request' function so a driver can choose whether a not-available-yet-but-still-expected resource should be waited for
or should return -EAGAIN? There is certainly precedent for that sort of
control.
Or is there something else you think might be needed?

I can see a driver wanting something like "either A or B".

Quoted 11 lines

A/ assume it will never be available and continue as best we can, which
might mean failure.
B/ wait indefinitely until it available.
C/ find out if it could ever become available and then go to either A or B. D/ wait a while and then go to either A or B
E/ set up a callback so we can notified if/when the resource is available
at which point we integrate it and improve functionality.

Are there others?
Current code does 'A'.

Hrm?

Quoted 2 lines

I first tried B but found that devices often ask for regulators that will never appear, so that didn't work.

That should be extremely rare, you're probably working with broken drivers. The only case I'm aware of is MMC and frankly the way it uses of regulators is more than a little dodgy.

Quoted 4 lines

So I went for C which I agree is a little inelegant and I now see doesn't handle cases where some dependencies may or may exist depending on the current hardware.

The latter bit is the real killer - you need to know right at the start of boot what you're going to find when you start the system. An approach that relies on that but does require us to do work to set it up doesn't seem especially useful.

Quoted 4 lines

'E' would be ideal in some sense, but could result in some rather complex code that never gets tested. Maybe with good design and infrastructure it could be made to work. 'C' might be a useful step towards that.

To a good approximation that's what both the retry based approach and threading approaches do.

Quoted 5 lines

Quoted 5 lines

It also seems inelegant in that we're having to pass all the constraints both via this and via the normal probe mechanism. If we were going to do this we'd be better off changing the way that regulators find their constraints so they aren't passed in through the driver as it probes.

Quoted 6 lines

Quoted 4 lines

drivers/regulator/core.c static int set_supply(struct regulator_dev *rdev, · line 974

Quoted 2 lines

drivers/regulator/core.c +2 -0

+static void regulator_wake_waiters(const char *devname, const char *id,
+	const char *reg)

I've no idea what "const char *reg" is...

It is the name of a regulator...

This is not guaranteed to be unique.

Quoted 8 lines

There are two ways that you can ask for a regulator.
You can ask for it by device+supply (which is what normal devices ask for) or you can ask for it by regulator-name (which is what a regulator asks for when it is being supplied by some upstream regulator).

So there really are two separate lookup functions here - one to look up by device+supply (aka devname+id) and one to look up by regulator name.

Not really, you're always asking for a supply by name.

On Sun, 8 Jan 2012 22:22:31 -0800 Mark Brown

Quoted 6 lines · NeilBrown

So, my general inclination is that given the choice between parallel and serial solutions I'll prefer the serial solution on the basis that it's most likely going to be easier to think about and less prone to getting messed up.

Surely anyone doing kernel work needs to be able to understand parallel solutions at least enough to place locks in appropriate places ???

I thought about doing a serial retry solution the error from the ->probe function doesn't percolate all the way up the the initcall.
In particular, when a driver is registered driver_attach is called for each unattached device on the bus. This is done in __driver_attach which discard the error return from driver_probe_device().

Quoted 9 lines

Quoted 3 lines

Completely agree. I think the key simplification would be for each resource to have a simple textual name. Then you could write more common infrastructure.

That's pretty much the case already for most things - the cannonical thing is to look up by (struct device, string). Squashing everything into a single flat namespace is painful as completely unrelated bits of the system easily collide with each other. GPIO and IRQ are the only holdouts I can think of in this area.

I don't see (struct device, string) being used at all.

Regulator used (devicename, string). It seems that it used to use (struct device, string) but that is deprecated.

So strings seem simple. Each different resource type would be a different name space of course.

If a particular resource wanted to encourage "devicename-usagetype" that would be fine, but requiring "devicename" to be present would be a problem for resources (like some IRQs) which are shared between devices... though I guess regulators are shared between devices.... Do we really need the extra level of indirection provided by regulator_consumer_supply? I presume there is a good reason.

Quoted 5 lines

Quoted 3 lines

or should return -EAGAIN? There is certainly precedent for that sort of
control.
Or is there something else you think might be needed?

I can see a driver wanting something like "either A or B".

I think you agree with me. 'A' is non-blocking lookup that can fail. 'B' is blocking lookup. That is what I suggested above.

But when would it ever be safe for a driver to ask for A? How would it know if it isn't available yet it never will be?

Quoted 6 lines

Quoted 2 lines

I first tried B but found that devices often ask for regulators that will never appear, so that didn't work.

That should be extremely rare, you're probably working with broken drivers. The only case I'm aware of is MMC and frankly the way it uses of regulators is more than a little dodgy.

Yes, MMC is exactly the case I am aware of. If this usage is "wrong" then I guess it needs to be "fixed" before we can proceed.

Quoted 3 lines

Quoted 3 lines

So I went for C which I agree is a little inelegant and I now see doesn't handle cases where some dependencies may or may exist depending on the current hardware.

Quoted 4 lines

The latter bit is the real killer - you need to know right at the start of boot what you're going to find when you start the system. An approach that relies on that but does require us to do work to set it up doesn't seem especially useful.

I must admit that I find this possibility perplexing.
I can certainly imagine individual independent devices that may or may not exists (USB things etc) but there are no dependencies there to worry about.

But if we find a device, and we know that it depends on some resource, and that resource is never going to be available - then is there really anything useful that can be done?
Wouldn't it be correct to fail the boot ??

Quoted 6 lines

Quoted 3 lines

'E' would be ideal in some sense, but could result in some rather complex code that never gets tested. Maybe with good design and infrastructure it could be made to work. 'C' might be a useful step towards that.

To a good approximation that's what both the retry based approach and threading approaches do.

I disagree. My "E" was "provide partial functionality until the resource becomes available, then provide more full functionality". The retry and threading are "provide no functionality until the resource is available" and I would say that is a difference of kind, not just of degree.

Quoted 3 lines

Quoted 1 line

It is the name of a regulator...

This is not guaranteed to be unique.

Well, it is whatever is expected in .supply_regulator in 'struct regulator_init_data'. That's not a name??

Do we really need uniform resource naming so we can use common code, or can we proceed with multiple ad-hoc source lookup schemes (like I provided) and then encourage subsystems to move towards a standard? The former would risk never making progress.

Is single-threading really worth all the churn deep inside the drivers/base code that is would probably require?

Is mmc's use of regulators a problem that can be fixed, or a reasonable if baroque use of available interfaces and something we should just live with?

Quoted 7 lines · NeilBrown

On Sun, 8 Jan 2012 22:22:31 -0800 Mark Brown

Quoted 6 lines · NeilBrown

So, my general inclination is that given the choice between parallel and serial solutions I'll prefer the serial solution on the basis that it's most likely going to be easier to think about and less prone to getting messed up.

Quoted 2 lines

Surely anyone doing kernel work needs to be able to understand parallel solutions at least enough to place locks in appropriate places ???

You'd expect people to be able to work it out but there's no sense in doing something hard if something easy works just as well - concurrency can bring problems with things like reproducibility which make life harder than it might otherwise be.

Quoted 5 lines

I thought about doing a serial retry solution the error from the ->probe function doesn't percolate all the way up the the initcall.
In particular, when a driver is registered driver_attach is called for each unattached device on the bus.  This is done in __driver_attach which discard the error return from driver_probe_device().

There's code for doing the retries floating around, Grant Likely was working on it initially then someone from Linaro picked it up and I'm not sure what happened.

Quoted 2 lines

Is single-threading really worth all the churn deep inside the drivers/base code that is would probably require?

I don't see why it'd require much churn to be honest - the patches that I looked at weren't that invasive, basically just shove devices that fail with a particular code into a retry list and iterate through it whenever it seems useful to do so.