[RFC/PATCH] Multithread initcalls to auto-resolve ordering issues.

[RFC/PATCH] Multithread initcalls to auto-resolve ordering issues.

[NeilBrown]

[-- Attachment #1: Type: text/plain, Size: 20153 bytes --]


[ 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 <neilb@suse.de>
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 <neilb@suse.de>

diff --git a/drivers/base/dd.c b/drivers/base/dd.c
index 142e3d600..06963e4 100644
--- a/drivers/base/dd.c
+++ b/drivers/base/dd.c
@@ -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);
diff --git a/drivers/gpio/gpiolib.c b/drivers/gpio/gpiolib.c
index a971e3d..7d283af 100644
--- a/drivers/gpio/gpiolib.c
+++ b/drivers/gpio/gpiolib.c
@@ -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
@@ -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();
 
 	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;
diff --git a/drivers/regulator/core.c b/drivers/regulator/core.c
index 938398f..0ec34f7 100644
--- a/drivers/regulator/core.c
+++ b/drivers/regulator/core.c
@@ -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
  *
diff --git a/include/linux/init.h b/include/linux/init.h
index 9146f39..e898afe 100644
--- a/include/linux/init.h
+++ b/include/linux/init.h
@@ -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
diff --git a/include/linux/regulator/machine.h b/include/linux/regulator/machine.h
index f3f13fd..e78def2 100644
--- a/include/linux/regulator/machine.h
+++ b/include/linux/regulator/machine.h
@@ -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)
 {
 }
diff --git a/init/main.c b/init/main.c
index 217ed23..6cb2239 100644
--- a/init/main.c
+++ b/init/main.c
@@ -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;
 }
 
 /*

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: [RFC/PATCH] Multithread initcalls to auto-resolve ordering issues.

[Ryan Mallon]

On 09/01/12 11:21, NeilBrown wrote:

> 
> [ 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.


Hi Neil,

Interesting idea, some comments below.

~Ryan

> 
> 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.

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?

> 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.


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.

> 
>      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.

> 
>   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?

>      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 <neilb@suse.de>
> 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 <neilb@suse.de>
> 
> diff --git a/drivers/base/dd.c b/drivers/base/dd.c
> index 142e3d600..06963e4 100644
> --- a/drivers/base/dd.c
> +++ b/drivers/base/dd.c
> @@ -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);
> diff --git a/drivers/gpio/gpiolib.c b/drivers/gpio/gpiolib.c
> index a971e3d..7d283af 100644
> --- a/drivers/gpio/gpiolib.c
> +++ b/drivers/gpio/gpiolib.c
> @@ -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
> @@ -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/

>  
>  	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;
> diff --git a/drivers/regulator/core.c b/drivers/regulator/core.c
> index 938398f..0ec34f7 100644
> --- a/drivers/regulator/core.c
> +++ b/drivers/regulator/core.c
> @@ -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
>   *
> diff --git a/include/linux/init.h b/include/linux/init.h
> index 9146f39..e898afe 100644
> --- a/include/linux/init.h
> +++ b/include/linux/init.h
> @@ -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
> diff --git a/include/linux/regulator/machine.h b/include/linux/regulator/machine.h
> index f3f13fd..e78def2 100644
> --- a/include/linux/regulator/machine.h
> +++ b/include/linux/regulator/machine.h
> @@ -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)
>  {
>  }
> diff --git a/init/main.c b/init/main.c
> index 217ed23..6cb2239 100644
> --- a/init/main.c
> +++ b/init/main.c
> @@ -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;
>  }
>  
>  /*

Re: [RFC/PATCH] Multithread initcalls to auto-resolve ordering issues.

[NeilBrown]

[-- Attachment #1: Type: text/plain, Size: 7520 bytes --]

On Mon, 09 Jan 2012 12:05:28 +1100 Ryan Mallon <rmallon@gmail.com> wrote:

> On 09/01/12 11:21, NeilBrown wrote:
> 
> > 
> > [ 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.
> 
> 
> Hi Neil,
> 
> Interesting idea, some comments below.
> 

Thanks for the quick review!

> > 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?

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.

> 
> > 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.
> 
> 
> 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.


> 
> > 
> >      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.
> 
> > 
> >   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?

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.


> > @@ -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.


Thanks again,

NeilBrown

> 
> >  
> >  	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;

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: [RFC/PATCH] Multithread initcalls to auto-resolve ordering issues.

[Ryan Mallon]

On 09/01/12 14:29, NeilBrown wrote:

> On Mon, 09 Jan 2012 12:05:28 +1100 Ryan Mallon <rmallon@gmail.com> wrote:
> 
>> On 09/01/12 11:21, NeilBrown wrote:
>>
>>>
>>> [ 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.
>>
>>
>> Hi Neil,
>>
>> Interesting idea, some comments below.
>>
> 
> Thanks for the quick review!
> 
>>> 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?
> 
> 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.


I think this is a realistic scenario in the cases I gave. A resource may
fail to load properly for a variety of reasons. For example in an
embedded system a regulator driver could be dependent on an i2c io
expander to provide some of its gpios. If the expander or i2c bus
hardware are faulty then it will fail to probe and the regulator driver
probe will get stuck forever.

If the resource driver is present, then it could notify the waiter if
its probe fails. It's a bit trickier if the resource driver probe never
even runs (driver missing, etc). Having a long timeout for the waiter
might be annoying if the dependency is missing since it will
unnecessarily stall the boot, and having too short a timeout could
result in the dependency being missed.

> 
>>
>>> 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.
>>
>>
>> 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.


Ah, yes. I was mistakenly thinking that when an initcall thread blocked,
the newly launched thread would be for its dependency, which is not
always going to be true.

Your solution seems like a good starting point. Without knowledge of how
many devices/dependencies there are, limiting the number of threads may
result in a situation where the system is unable to boot because all of
the threads are blocked and no more are allowed to be allocated.

I remember reading a few threads about making the boot process parallel,
and vaguely recall that there were a few difficulties in doing so. Is
making these initcalls parallel completely safe?


> 
> 
>>
>>>
>>>      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.
>>
>>>
>>>   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?
> 
> 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.
> 
> 
>>> @@ -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.

Yeah, I figured you may have done this just for testing purposes.

~Ryan

Re: [RFC/PATCH] Multithread initcalls to auto-resolve ordering issues.

[Mark Brown]

On Mon, Jan 09, 2012 at 11:21:13AM +1100, NeilBrown wrote:

>   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.

>      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.

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

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

> +{
> +	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;

...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.

> +	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.

> +		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.

> +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?

> +	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.

Re: [RFC/PATCH] Multithread initcalls to auto-resolve ordering issues.

[NeilBrown]

[-- Attachment #1: Type: text/plain, Size: 9210 bytes --]

On Sun, 8 Jan 2012 20:08:02 -0800 Mark Brown
<broonie@opensource.wolfsonmicro.com> wrote:

> On Mon, Jan 09, 2012 at 11:21:13AM +1100, NeilBrown wrote:
> 
> >   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).

Yes, I think there would be a lot of similarities between this approach and
some sort of re-try approach.  Both good points and bad points would be
shared.

The way I look at the difference is to look at the state that has been
assembled in the probe function at the point where the needed resource is
found to be unavailable.

In my threaded approach, this state is stored in a thread until it is needed.
In a retry approach it would be unwound, and then recreated at some later
time.

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

> 
> 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.

> 
> 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?


> 
> 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.

Yes, I sprinkled a few printk's around when developing this.  Some proper
tracing could certainly be useful.


> 
> >      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.

If you want a resource and it isn't available there are a few thing you can
do:

 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.
I then tried D but that easily resulted in failures.  One device waiting for
something that will never appear, a second waiting for the first.
If the first times out it works OK.  If the second times out you get a
failure.  So not good.

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.

(I have exactly this problem with in md/raid.  e.g. if 3 drives of a 4-drive
RAID5 array appear, do I start the array in degraded mode, or wait for the
4th drive.  If the latter, when do I give up waiting?).


> 
> 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.
> 
> > +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...

> 
> > +{
> > +	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;
> 
> ...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.

Very perceptive!

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.


> 
> > +	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.

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.



> 
> > +		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.
> 
> > +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.


> 
> > +	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...

Anyway it just an easy way to get a list of names of expected regulators.

If "expected" isn't really a well defined concept, then we will need
something else.

Thanks a lot for the review,

NeilBrown


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: [RFC/PATCH] Multithread initcalls to auto-resolve ordering issues.

[Mark Brown]

On Mon, Jan 09, 2012 at 04:10:58PM +1100, NeilBrown wrote:
> 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.

> > 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.

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.

> > 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?

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

>  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?

> 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.

> 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.

> '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.

> > 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.

> > > +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.

> 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.

> > > +	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.

> 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.

No, the driver has no idea how the system integrator chose to design
their board and different system integrators may make different
decisions.

> You would need that for current code to work anyway.

Sort of.  The data is OK as-is, we could handle this entirely in core.

> > > +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.

That's not going to work for anyone making new boards and increases
fragility.

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

I'd rather expect that as soon as we can we're going to back out all the
bodges we use currently.

> > > +	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...

The primary purpose is so that we can provide a meaningful name for the
supply when talking about it.  Usually this would be filled in with the
names the rails have in the schematic but there's no reason to require
that.

Re: [RFC/PATCH] Multithread initcalls to auto-resolve ordering issues.

[NeilBrown]

[-- Attachment #1: Type: text/plain, Size: 8473 bytes --]

On Sun, 8 Jan 2012 22:22:31 -0800 Mark Brown
<broonie@opensource.wolfsonmicro.com> wrote:

> On Mon, Jan 09, 2012 at 04:10:58PM +1100, NeilBrown wrote:
> > 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.

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().

Now maybe we could catch the error and arrange to call driver_attach again,
but then we have to be careful of drives that call platform_driver_probe
which is explicitly designed to only try to find devices once - they don't
work first time, they don't get attached.

Presumably all this could be sorted out but it felt like the changes would be
very intrusive and easy to get wrong.

Be comparison I find a bit of parallelism which some simple locking quite
easy to follow :-)


> > 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.

GPIO and  IRQ use (number).

pwm_request() also used (number).

I don't much care what is used as long as everyone uses the same so we can
write shared code.
If everyone used number we would keep running into namespace allocation
problems.
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.

> 
> > > 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?
> 
> 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?


> 
> >  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?
> 
> > 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.


> 
> > 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.

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 ??

Or at worst, leave a thread waiting for the never-to-appear resource and let
the rest of the system boot.  Is there are scenario where there is a
dependency that we know about, that might not become available, but we want
to continue with normal boot anyway??


> 
> > '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.


> 
> > > 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.
> 
> > > > +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.

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

> 
> > 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.

When I look in the 
	if (init_data->supply_regulator) {
branch of regulator_register(), I don't see that.


So: what are the options for a way forward?

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?


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: [RFC/PATCH] Multithread initcalls to auto-resolve ordering issues.

[Mark Brown]

On Mon, Jan 09, 2012 at 06:28:00PM +1100, NeilBrown wrote:
> On Sun, 8 Jan 2012 22:22:31 -0800 Mark Brown
> > On Mon, Jan 09, 2012 at 04:10:58PM +1100, NeilBrown wrote:

> > 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 ???

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.

> 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.

> > > 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.

The things doing the requesting use the struct device.  The things doing
the mapping use the device name.  The two are equivalent, it's just that
it's hard to write a struct device for many buses prior to probe().

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

It's really not that helpful, it's got the same issues as numbers do as
soon as you get two devices of the same type or just two devices using a
common name (lots of devices have clock inputs called CLK or whatever).

> 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.

If we don't do this we have to go through every single driver that wants
to use the API adding platform data where there might've been none
before.  This winds up being a lot more code all round (same as for the
clock API and so on).

> > > 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.

No...

> 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?

...due to this you want the driver to block on (A || B) and not try A
then prefer B as you suggest.

> > > 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.

The general idea is to use regulators unconditionally, and there's also
some issues with the use of regulator_get_exclusive() which isn't
actually what's required.

> > > 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.

> 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.

That's not the case for USB, you often get soldered down USB devices
that have GPIOs and things.

> 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 ??

You're missing the point.  If we're enumerating the system at runtime
(for example, by reading ID information from the hardware) then there
may be substantial parts of the system that we don't know the expected
layout and connections of until some point during the boot.  This means
that we can't construct a list of the resources we know are going to
appear early in init and give it to the core as we're going to discover
resources during the boot.

> > > '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.

Oh, that seems a bit silly and for many resources would be no different
to just providing no functionality anyway as things like powering the
device on tend to be fairly fundamental.

> > > 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??

It might just be empty, and the overwhelming majority of regulators will
not supply other regulators and can be called anything that amuses the
system integrator for all the API cares.  The string might also be
satisfied from somewhere else, there's a fallback tree.

> 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.

We only have two schemes that exist right now in the APIs you've looked
at (plus at least ASoC and whatever V4L does), we certainly shouldn't be
open coding this in individual subsystems.

> 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.

> 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?

There are fixes needed, it's already caused problems for some systems I
believe and there's certainly breakage with things like the OMAP hsmmc
driver abuse of the API.

Re: [RFC/PATCH] Multithread initcalls to auto-resolve ordering issues.

[Grant Likely]

On Mon, Jan 9, 2012 at 1:08 AM, Mark Brown
<broonie@opensource.wolfsonmicro.com> wrote:
> On Mon, Jan 09, 2012 at 06:28:00PM +1100, NeilBrown wrote:
>> On Sun, 8 Jan 2012 22:22:31 -0800 Mark Brown
>> > On Mon, Jan 09, 2012 at 04:10:58PM +1100, NeilBrown wrote:
>
>> > 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 ???
>
> 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.

+1

>> 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.

I'm going to pick up the patch again next week and get it ready for
possible 3.4 merging.  I've gotten a lot of requests to get this work
finished.  The latest posted version of the patch can be found here[1]
and the lwn article is here[2]:

[1]https://lkml.org/lkml/2011/10/7/17
[2]http://lwn.net/Articles/450460/

I (obviously) prefer the deferred probe approach over using threaded
initcalls.  I originally did look at doing exactly what is proposed
here, but I didn't like that it required each subsystem to be
explicitly modified to provide blocking request calls, and I also
discovered that it's been tried and failed several times before.  It
appears that there are a lot of undeclared dependencies and
concurrency issues between device drivers that are pretty much
impossible to track down.

I like the deferred probe approach because it is conceptually simple,
it is minimally invasive, and it works for all subsystems without
needing to implement blocking infrastructure.

As far as the device tree aspects go, it is true that whether or not a
resource will exist is described by device tree data.  However, the
best place to interpret that data is not with the resource provider
driver, but with the resource consumer because the consumer's driver
understands how resources are bound for that specific device. (a
provider node generally doesn't have any information about or way to
determine which consumer nodes will be using it).

[...]
>> 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.

There is very little churn.  The driver model already did /almost/
everything that was needed.  I pretty much just needed to add the list
and an iterator for it.

g.