[RFC] power trees

[RFC] power trees

[Adam Belay]

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

Hi All,

I've been experimenting with a power object tree for handling power
state dependencies.  Many major bus specifications fit well in a
power-state based model.  They include PCI/Cardbus, ACPI, IDE, and
probably even USB.  More complex dependencies generally rely on out of
tree elements (e.g. power planes, clocks, processor states, etc.) or are
isolated to a specific parent and its child.  Therefore, I think a power
tree would be useful for a wide range of device drivers.  Nonetheless,
the power tree is provided as an optional library only.

My implementation has two primary goals:

1.) To help device drivers track and control their device's power state

2.) To bubble power state dependency changes from a leaf node to the
last affected parent node in the chain.

The basic unit of the tree is referred to as a "pm_node".  Each
"pm_node" has a list of states it supports, a current state, and a
driver to handle state transitions.  Any "pm_node" can have children and
therefore act as a power container.

struct pm_state {
	char			*name;
	unsigned long		index;
	unsigned long		link_req;
	void			*link_data;
};

"index" is a driver specific value that indicates the state.  "link_req"
is a set of flags that indicate requirements from the parent "pm_node".
"link_data" provides additional requirement information.

struct pm_node {
	struct semaphore	sem;
	struct list_head	children;
	struct list_head	child_list;
	struct pm_node		*parent;
	struct pm_node		*tmp_path;
	struct device		*dev;

	struct pm_node_driver	*drv;
	unsigned int		current_state;
	unsigned int		target_state;

	unsigned int		num_states;
	struct pm_state		*states;
};

"states" is a list of power states sorted from most functional to least
functional.  "current_state" and "target_state" are index values for
that list.

struct pm_node_driver {
	int (*set_state) 	(struct pm_node *node);
	int (*raise_event)	(struct pm_node *domain,
				 struct pm_node *child,
				 unsigned long *new_state);
	void (*lower_event)	(struct pm_node *domain);
};

"raise_event" notifies the power domain when a child has increased its
state.  "new_state" allows for a domain to pass an index of the new
state it would need in response to the new requirements.  "lower_event"
is called when power is decreased.  It is expected to return immediately
and defer any power transitions for later (generally with a timeout
value).

I apologize for the unpolished/untested state of the code as it's
primarily intended to illustrate a concept.  I'll need to look over the
problem more carefully if we decide this is the right direction.  Power
dependency notifications are entirely iterative in this implementation.
Locking is always from leaf nodes down.  The "iterative" requirement
seems to be a little inflexible with notifications, so we may want to
start with a recursive algorithm if this proves to be too difficult.
Are there any known cases of deep power trees?  I look forward to any
comments or suggestions.

Thanks,
Adam

--- a/drivers/base/power/Makefile	2005-06-17 19:48:29.000000000 +0000
+++ b/drivers/base/power/Makefile	2005-08-09 15:52:50.000000000 +0000
@@ -1,5 +1,5 @@
 obj-y			:= shutdown.o
-obj-$(CONFIG_PM)	+= main.o suspend.o resume.o runtime.o sysfs.o
+obj-$(CONFIG_PM)	+= main.o node.o suspend.o resume.o runtime.o sysfs.o
 
 ifeq ($(CONFIG_DEBUG_DRIVER),y)
 EXTRA_CFLAGS += -DDEBUG
--- a/drivers/base/power/node.c	1970-01-01 00:00:00.000000000 +0000
+++ b/drivers/base/power/node.c	2005-08-11 03:46:46.000000000 +0000
@@ -0,0 +1,188 @@
+/*
+ * drivers/base/power/node.c - power node registration and control
+ *
+ * This file is released under the GPLv2
+ */
+
+#include <linux/config.h>
+#include <linux/device.h>
+#include <linux/module.h>
+#include "power.h"
+
+
+/*
+ * Registration
+ */
+
+/**
+ * pm_register_node - registers a power management node with the driver core
+ * @node - the node
+ */
+int pm_register_node(struct pm_node *node)
+{
+	if (!node->drv || !node->current_state)
+		return -EINVAL;
+
+	init_MUTEX(&node->sem);
+	INIT_LIST_HEAD(&node->children);
+
+	if (node->parent) {
+		down(&node->parent->sem);
+		list_add_tail(&node->child_list, &node->parent->children);
+		up(&node->parent->sem);
+	}
+
+	return 0;
+}
+
+EXPORT_SYMBOL_GPL(pm_register_node);
+
+/**
+ * pm_unregister_node - removes a power management node from the driver core
+ * @node - the node
+ */
+void pm_unregister_node(struct pm_node *node)
+{
+	if (node->parent) {
+		down(&node->parent->sem);
+		list_del(&node->child_list);
+		up(&node->parent->sem);
+	}
+}
+
+EXPORT_SYMBOL_GPL(pm_unregister_node);
+
+
+/*
+ * Power State Control
+ */
+
+static int pm_set_target(struct pm_node *node, unsigned long state_index)
+{
+	int i;
+
+	for (i = 0; i < node->num_states; i++) {
+		struct pm_state *s = &node->states[i];
+		if (s->index == state_index) {
+			node->target_state = i;
+			return 0;
+		}
+	}
+
+	return -ENODEV;
+}
+
+static void pm_recover_nodes(struct pm_node *bottom)
+{
+	struct pm_node *next, *pos = bottom;
+
+	while (pos->tmp_path) {
+		next = pos->tmp_path;
+		pos->tmp_path = NULL;
+		pos->target_state = pos->current_state;
+		up(&pos->sem);
+		pos = next;
+	}
+}
+
+static int pm_raise_nodes(struct pm_node *node)
+{
+	int ret;
+	unsigned long state_index;
+	struct pm_node *prev = node;
+	struct pm_node *pos = node->parent;
+
+	for (;;) {
+		down(&pos->sem);
+		pos->tmp_path = prev;
+
+		ret = pos->drv->raise_event(pos, prev, &state_index);
+		if (ret)
+			goto fail;
+		
+		pm_set_target(pos, state_index);
+
+		if (pos->current_state == pos->target_state) {
+			pos = prev;
+			break;
+		}
+
+		if (!pos->parent)
+			break;
+
+		prev = pos;
+		pos = pos->parent;
+	}
+
+	while (pos) {
+		ret = node->drv->set_state(node);
+		if (ret)
+			goto fail;
+
+		if (pos->parent) {
+			pos->parent->tmp_path = NULL;
+			up(&pos->parent->sem);
+		}
+
+		pos = pos->tmp_path;
+	}
+
+	return 0;
+
+fail:
+	pm_recover_nodes(pos);
+	return ret;
+}
+
+static int pm_lower_nodes(struct pm_node *node)
+{
+	int ret;
+	struct pm_node *pos = node->parent;
+
+	ret = node->drv->set_state(node);
+	if (ret)
+		return ret;
+
+	down(&pos->sem);
+	pos->drv->lower_event(pos);
+	up(&pos->sem);
+
+	return 0;
+}
+ 
+/**
+ * pm_set_state - sets the power state of a pm_node
+ * @node - the node
+ * @state - the index value of the target power state
+ */
+int pm_set_state(struct pm_node *node, unsigned long state)
+{
+	int ret;
+
+	down(&node->sem);
+
+	if (!pm_set_target(node, state)) {
+		up(&node->sem);
+		return -EINVAL;
+	}
+	
+	if (node->target_state == node->current_state) {
+		up(&node->sem);
+		return 0;
+	}
+
+	if (!node->parent)
+		ret = node->drv->set_state(node);
+	else if (node->target_state > node->current_state) 
+		ret = pm_raise_nodes(node);
+	else
+		ret = pm_lower_nodes(node);
+
+	up(&node->sem);
+	return ret;
+}
+
+EXPORT_SYMBOL_GPL(pm_set_state);
--- a/include/linux/pm.h	2005-08-09 17:49:51.000000000 +0000
+++ b/include/linux/pm.h	2005-08-11 03:16:13.000000000 +0000
@@ -14,6 +14,7 @@
 #include <linux/config.h>
 #include <linux/list.h>
 #include <asm/atomic.h>
+#include <asm/semaphore.h>
 
 #include <linux/pm_legacy.h>
 
@@ -108,6 +109,58 @@
 }
 #endif
 
+
+/*
+ * Power Nodes
+ */
+
+struct pm_state {
+	char			*name;
+	unsigned long		index;
+	unsigned long		link_req;
+	void			*link_data;
+};
+
+struct pm_node;
+
+struct pm_node_driver {
+	int (*set_state) 	(struct pm_node *node);
+	int (*raise_event)	(struct pm_node *domain,
+				 struct pm_node *child,
+				 unsigned long *new_state);
+	void (*lower_event)	(struct pm_node *domain);
+};
+
+struct pm_node {
+	struct semaphore	sem;
+	struct list_head	children;
+	struct list_head	child_list;
+	struct pm_node		*parent;
+	struct pm_node		*tmp_path;
+	struct device		*dev;
+
+	struct pm_node_driver	*drv;
+	unsigned int		current_state;
+	unsigned int		target_state;
+
+	unsigned int		num_states;
+	struct pm_state		*states;
+};
+
+static inline struct pm_state * __pm_get_state(struct pm_node *node)
+{
+	return &node->states[node->current_state];
+}
+
+static inline struct pm_state * __pm_get_target_state(struct pm_node *node)
+{
+	return &node->states[node->target_state];
+}
+
+extern int pm_register_node(struct pm_node *node);
+extern void pm_unregister_node(struct pm_node *node);
+extern int pm_set_state(struct pm_node *node, unsigned long state);
+
 #endif /* __KERNEL__ */
 
 #endif /* _LINUX_PM_H */





[-- Attachment #2: Type: text/plain, Size: 0 bytes --]

Re: [RFC] power trees

[Greg KH]

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

On Thu, Aug 11, 2005 at 04:50:41AM +0000, Adam Belay wrote:
> struct pm_node {
> 	struct semaphore	sem;
> 	struct list_head	children;
> 	struct list_head	child_list;
> 	struct pm_node		*parent;
> 	struct pm_node		*tmp_path;
> 	struct device		*dev;
> 
> 	struct pm_node_driver	*drv;
> 	unsigned int		current_state;
> 	unsigned int		target_state;
> 
> 	unsigned int		num_states;
> 	struct pm_state		*states;
> };

Shouldn't this structure contain a kobject?  Or do you not want to
represent the power node tree in sysfs?

thanks,

greg k-h

[-- Attachment #2: Type: text/plain, Size: 0 bytes --]

Re: [RFC] power trees

[Pavel Machek]

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

Hi!

> My implementation has two primary goals:
> 
> 1.) To help device drivers track and control their device's power state
> 
> 2.) To bubble power state dependency changes from a leaf node to the
> last affected parent node in the chain.
> 
> The basic unit of the tree is referred to as a "pm_node".  Each
> "pm_node" has a list of states it supports, a current state, and a
> driver to handle state transitions.  Any "pm_node" can have children and
> therefore act as a power container.
> 
> struct pm_state {
> 	char			*name;
> 	unsigned long		index;
> 	unsigned long		link_req;
> 	void			*link_data;
> };
> 
> "index" is a driver specific value that indicates the state.  "link_req"
> is a set of flags that indicate requirements from the parent "pm_node".
> "link_data" provides additional requirement information.
> 
> struct pm_node {
> 	struct semaphore	sem;
> 	struct list_head	children;
> 	struct list_head	child_list;
> 	struct pm_node		*parent;
> 	struct pm_node		*tmp_path;
> 	struct device		*dev;
> 
> 	struct pm_node_driver	*drv;
> 	unsigned int		current_state;
> 	unsigned int		target_state;

Would not it be cleaner to have struct pm_state *current_state, target state?

> "states" is a list of power states sorted from most functional to least
> functional.  "current_state" and "target_state" are index values for
> that list.
> 
> struct pm_node_driver {
> 	int (*set_state) 	(struct pm_node *node);
> 	int (*raise_event)	(struct pm_node *domain,
> 				 struct pm_node *child,
> 				 unsigned long *new_state);

struct pm_state here, too?

> 	void (*lower_event)	(struct pm_node *domain);
> };
> 
> "raise_event" notifies the power domain when a child has increased its

"Increase" == went more power hungry?

> I apologize for the unpolished/untested state of the code as it's
> primarily intended to illustrate a concept.  I'll need to look over the
> problem more carefully if we decide this is the right direction.  Power

Seems ok to me.

-- 
64 bytes from 195.113.31.123: icmp_seq=28 ttl=51 time=448769.1 ms         


[-- Attachment #2: Type: text/plain, Size: 0 bytes --]

Re: [RFC] power trees

[Alan Stern]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2834 bytes --]

Sorry it's taken me so long to respond to this.

> > My implementation has two primary goals:
> > 
> > 1.) To help device drivers track and control their device's power state
> > 
> > 2.) To bubble power state dependency changes from a leaf node to the
> > last affected parent node in the chain.
> > 
> > The basic unit of the tree is referred to as a "pm_node".  Each
> > "pm_node" has a list of states it supports, a current state, and a
> > driver to handle state transitions.  Any "pm_node" can have children and
> > therefore act as a power container.

I think it's a mistake to make this a tree.  The natural structure is a 
DAG, where nodes can have multiple parents.  It might not be worthwhile 
trying to store the parent/child/sibling pointers in the structures.

> > struct pm_state {
> > 	char			*name;
> > 	unsigned long		index;
> > 	unsigned long		link_req;
> > 	void			*link_data;
> > };
> > 
> > "index" is a driver specific value that indicates the state.  "link_req"
> > is a set of flags that indicate requirements from the parent "pm_node".
> > "link_data" provides additional requirement information.

Given that there can be multiple parents, the link_* members of this 
structure won't be useful.  Also, I don't see that index expresses any 
information not already present in name.

> > struct pm_node {
> > 	struct semaphore	sem;
> > 	struct list_head	children;
> > 	struct list_head	child_list;
> > 	struct pm_node		*parent;
> > 	struct pm_node		*tmp_path;
> > 	struct device		*dev;
> > 
> > 	struct pm_node_driver	*drv;
> > 	unsigned int		current_state;
> > 	unsigned int		target_state;
> 
> Would not it be cleaner to have struct pm_state *current_state, target state?

I don't see the point of having target_state at all.

> > "states" is a list of power states sorted from most functional to least
> > functional.

In general it's not possible to sort states in that way.  Some states 
might permit one subset of the complete set of functions while other 
states permit a different, partially overlapping, subset.

> >   "current_state" and "target_state" are index values for
> > that list.
> > 
> > struct pm_node_driver {
> > 	int (*set_state) 	(struct pm_node *node);
> > 	int (*raise_event)	(struct pm_node *domain,
> > 				 struct pm_node *child,
> > 				 unsigned long *new_state);
> 
> struct pm_state here, too?
> 
> > 	void (*lower_event)	(struct pm_node *domain);
> > };
> > 
> > "raise_event" notifies the power domain when a child has increased its
> 
> "Increase" == went more power hungry?

There's no need to have separate raise_event and lower_event entry points.  
In fact you might not want to have those entry points at all, since the 
information they convey will be so bus-specific.  It might be better to 
rely on bus-specific entry points.  I'm not sure about this.

Alan Stern


[-- Attachment #2: Type: text/plain, Size: 0 bytes --]

Re: [RFC] power trees

[Pavel Machek]

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

Hi!



> > > "states" is a list of power states sorted from most functional to least
> > > functional.
> 
> In general it's not possible to sort states in that way.  Some states 
> might permit one subset of the complete set of functions while other 
> states permit a different, partially overlapping, subset.

How common is that? We should probably treat that as two different
devices...

				Pavel

-- 
64 bytes from 195.113.31.123: icmp_seq=28 ttl=51 time=448769.1 ms         


[-- Attachment #2: Type: text/plain, Size: 0 bytes --]

Re: [RFC] power trees

[Alan Stern]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 492 bytes --]

On Sun, 21 Aug 2005, Pavel Machek wrote:

> > In general it's not possible to sort states in that way.  Some states 
> > might permit one subset of the complete set of functions while other 
> > states permit a different, partially overlapping, subset.
> 
> How common is that? We should probably treat that as two different
> devices...

I don't have any examples.  Such things occur more in the embedded world
than among regular PCs.  Can anyone else provide some information?

Alan Stern


[-- Attachment #2: Type: text/plain, Size: 0 bytes --]

Re: [RFC] power trees

[David Brownell]

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

> > > My implementation has two primary goals:
> > > 
> > > 1.) To help device drivers track and control their device's power state

What do you see happening with "struct dev_pm_info", which is the current
(and needs-work) approach for this?


> > > 2.) To bubble power state dependency changes from a leaf node to the
> > > last affected parent node in the chain.
> > > 
> > > The basic unit of the tree is referred to as a "pm_node".  Each
> > > "pm_node" has a list of states it supports, a current state, and a
> > > driver to handle state transitions.  Any "pm_node" can have children and
> > > therefore act as a power container.
>
> I think it's a mistake to make this a tree.  The natural structure is a 
> DAG, where nodes can have multiple parents.  It might not be worthwhile 
> trying to store the parent/child/sibling pointers in the structures.

Plus, the current driver model already builds a power tree, with node
type "struct dev_pm_info".  What would be the goal of adding another,
normally parallel, tree?  Rather than just sorting out how to use
that one, and dev_pm_info.pm_parent.  (Which we need to do anyway!)

My pet problem case can best be called "multiple parents".  That's pretty
common; one subassembly (part of a board, chip, etc) has PM interactions
with a bunch of other components.  For discussion, I'll say that uses a
"composite driver" ... it's usually built out of a few other drivers.
(One real-world example would be a USB OTG subsystem.  Typically that
combines drivers for an I2C transceiver, USB host, USB peripheral, OTG
controller, and parts of a battery charger.  They work together.)


The interesting question to me is then how to fit composite drivers into
today's driver/PM core code ... such subassemblies will show up in more
than one place in the driver model (e.g. four drivers, on platform and
I2C busses), plus elsewhere (e.g. the clock tree), and per-device driver
model PM calls normally need to access composite driver state ...

Maybe if the dev_pm_info.pm_parent pointed to a

	struct composite_device {
		struct device		container;
		struct list_head	components;
		/* plus private device-wide state */

		/* didn't someone propose a call like this recently?
		 * it'd be the child notifiying the container.
		 * container used component->{suspend,resume}?
		 */
		int (*notify_state_change)(
				struct composite_device *container,
				struct device *component,
				void *data);
	};

on some bus or other, would offer the right kind of structure.  Especially
if the PM core morphed component->suspend() to pm_parent->suspend(), and
likewise for resume(), so individual components wouldn't need their own PM code.



> > > struct pm_state {
> > > 	char			*name;
> > > 	unsigned long		index;
> > > 	unsigned long		link_req;
> > > 	void			*link_data;
> > > };
> > > 
> > > "index" is a driver specific value that indicates the state.  "link_req"
> > > is a set of flags that indicate requirements from the parent "pm_node".
> > > "link_data" provides additional requirement information.
>
> Given that there can be multiple parents, the link_* members of this 
> structure won't be useful.  Also, I don't see that index expresses any 
> information not already present in name.

Better yet, the "struct pm_state" pointer could itself be the state
identifier.  We don't need to keep creating more of those.  :)

Who would use these state cookies though?  I think I'd like to see
a "roles and responsibilities" description of these API components.

I consider defining PM states to be the responsibility of the device;
and in some standardized environments (like PCI or USB), they may also
be constrained by the bus.  And while a bus may have some role in
managing power for its devices, that's not always the case.  (Example:
switching power for a platform device may involve some i2c requests.
Neither bus -- platform or i2c -- has PM responsibilties there.)


> > > struct pm_node {
> > > 	struct semaphore	sem;
> > > 	struct list_head	children;
> > > 	struct list_head	child_list;
> > > 	struct pm_node		*parent;
> > > 	struct pm_node		*tmp_path;
> > > 	struct device		*dev;
> > > 
> > > 	struct pm_node_driver	*drv;
> > > 	unsigned int		current_state;
> > > 	unsigned int		target_state;
> > 
> > Would not it be cleaner to have struct pm_state *current_state, target state?
>
> I don't see the point of having target_state at all.

In fact, I don't see any reason not to pass the "struct pm_state" pointer
directly from whatever code has the "chooses device state transitions" role.


> > > "states" is a list of power states sorted from most functional to least
> > > functional.
>
> In general it's not possible to sort states in that way.  Some states 
> might permit one subset of the complete set of functions while other 
> states permit a different, partially overlapping, subset.

Why would you want to expose one particular ordering of states at the
API level?  Any code responsible for such states is going to know what
the states mean, and how to order them for the task at hand.  If it
won't work with a randomized ordering, it's broken.  :)

With multiple variables (start with two voltages, three frequencies, and
four subcomponents to turn on/off) it's easy to see there can be multiple
orderings that may be meaningful from a given state ... including states
that can't currently be entered.

- Dave



[-- Attachment #2: Type: text/plain, Size: 0 bytes --]

Re: [RFC] power trees

[Tony Lindgren]

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

* David Brownell <david-b@pacbell.net> [050827 05:43]:
> > > > My implementation has two primary goals:
> > > > 
> > > > 1.) To help device drivers track and control their device's power state
> 
> What do you see happening with "struct dev_pm_info", which is the current
> (and needs-work) approach for this?
> 
> 
> > > > 2.) To bubble power state dependency changes from a leaf node to the
> > > > last affected parent node in the chain.
> > > > 
> > > > The basic unit of the tree is referred to as a "pm_node".  Each
> > > > "pm_node" has a list of states it supports, a current state, and a
> > > > driver to handle state transitions.  Any "pm_node" can have children and
> > > > therefore act as a power container.
> >
> > I think it's a mistake to make this a tree.  The natural structure is a 
> > DAG, where nodes can have multiple parents.  It might not be worthwhile 
> > trying to store the parent/child/sibling pointers in the structures.
> 
> Plus, the current driver model already builds a power tree, with node
> type "struct dev_pm_info".  What would be the goal of adding another,
> normally parallel, tree?  Rather than just sorting out how to use
> that one, and dev_pm_info.pm_parent.  (Which we need to do anyway!)

I agree. I think we should do this in the driver model. And considering
that a lot of the PM device states are machine specific, we should register
the driver specific PM states and limitations as resources.

This allows defining machine specific driver PM states and limitations
withouth having to shove them into the driver code. And it should be
also easy to add new PM states via sysfs if needed.

Regards,

Tony

[-- Attachment #2: Type: text/plain, Size: 0 bytes --]