On Mon, 31 May 2010 16:26:17 -0700
mark gross <[email protected]> wrote:
> On Mon, May 31, 2010 at 11:38:55PM +0200, Rafael J. Wysocki wrote:
> > On Monday 31 May 2010, Arve Hj?nnev?g wrote:
> > > 2010/5/29 Alan Stern <[email protected]>:
> > > > On Sat, 29 May 2010, Arve Hj?nnev?g wrote:
> > > >
> > > >> > In place of in-kernel suspend blockers, there will be a new type of QoS
> > > >> > constraint -- call it QOS_EVENTUALLY. It's a very weak constraint,
> > > >> > compatible with all cpuidle modes in which runnable threads are allowed
> > > >> > to run (which is all of them), but not compatible with suspend.
> > > >> >
> > > >> This sound just like another API rename. It will work, but given that
> > > >> suspend blockers was the name least objectionable last time around,
> > > >> I'm not sure what this would solve.
> > > >
> > > > It's not just a rename. By changing this into a QoS constraint, we
> > > > make it more generally useful. Instead of standing on its own, it
> > > > becomes part of the PM-QOS framework.
> > > >
> > >
> > > We cannot use the existing pm-qos framework. It is not safe to call
> > > from atomic context.
> >
> > We've just merged a patch that fixed that if I'm not mistaken. Mark, did your
> > PM QoS update fix that?
> >
>
> I'm pretty sure it can be called in atomic context, and if its not I'm
> sure we can fix that. It can be called in atomic context. I don't
> think it was ever a problem to call it in atomic context. The problem it
> had was that crappy list of string compares. Thats been fixed.
>
> --mgross
>
Well, the register call uses kzalloc. Apart from that I
think we're good.
The outstanding list traversals can be fixed also. (see below)
Cheers,
Flo
>From 66fdd76f8cc4be722dba3859ddadfe07e7a4b755 Mon Sep 17 00:00:00 2001
From: Florian Mickler <[email protected]>
Date: Tue, 1 Jun 2010 09:04:26 +0200
Subject: [PATCH] pm_qos: remove unnecessary list-traversal
The new extreme_value is only depending on the old extreme_value and
the changing value.
Signed-off-by: Florian Mickler <[email protected]>
---
kernel/pm_qos_params.c | 20 ++++++++++++++------
1 files changed, 14 insertions(+), 6 deletions(-)
diff --git a/kernel/pm_qos_params.c b/kernel/pm_qos_params.c
index f42d3f7..6618e2c 100644
--- a/kernel/pm_qos_params.c
+++ b/kernel/pm_qos_params.c
@@ -136,6 +136,16 @@ static s32 min_compare(s32 v1, s32 v2)
}
+static void update_target_val(int pm_qos_class, s32 val)
+{
+ s32 extreme_value;
+ s32 new_value;
+ extreme_value = atomic_read(&pm_qos_array[pm_qos_class]->target_value);
+ new_value = pm_qos_array[pm_qos_class]->comparitor(val,extreme_value);
+ if (extreme_value != new_value)
+ atomic_set(&pm_qos_array[pm_qos_class]->target_value,new_value);
+}
+
static void update_target(int pm_qos_class)
{
s32 extreme_value;
@@ -227,8 +237,8 @@ struct pm_qos_request_list *pm_qos_add_request(int pm_qos_class, s32 value)
spin_lock_irqsave(&pm_qos_lock, flags);
list_add(&dep->list,
&pm_qos_array[pm_qos_class]->requests.list);
+ update_target_val(pm_qos_class,dep->value);
spin_unlock_irqrestore(&pm_qos_lock, flags);
- update_target(pm_qos_class);
}
return dep;
@@ -249,23 +259,21 @@ void pm_qos_update_request(struct pm_qos_request_list *pm_qos_req,
s32 new_value)
{
unsigned long flags;
- int pending_update = 0;
s32 temp;
if (pm_qos_req) { /*guard against callers passing in null */
+ int target = pm_qos_req->pm_qos_class;
spin_lock_irqsave(&pm_qos_lock, flags);
if (new_value == PM_QOS_DEFAULT_VALUE)
- temp = pm_qos_array[pm_qos_req->pm_qos_class]->default_value;
+ temp = pm_qos_array[target]->default_value;
else
temp = new_value;
if (temp != pm_qos_req->value) {
- pending_update = 1;
pm_qos_req->value = temp;
+ update_target_val(target,temp);
}
spin_unlock_irqrestore(&pm_qos_lock, flags);
- if (pending_update)
- update_target(pm_qos_req->pm_qos_class);
}
}
EXPORT_SYMBOL_GPL(pm_qos_update_request);
--
1.7.1
The new extreme value is only depending on the old extreme value and
the changed value.
Signed-off-by: Florian Mickler <[email protected]>
---
kernel/pm_qos_params.c | 19 +++++++++++++++++--
1 files changed, 17 insertions(+), 2 deletions(-)
diff --git a/kernel/pm_qos_params.c b/kernel/pm_qos_params.c
index f42d3f7..5d71c12 100644
--- a/kernel/pm_qos_params.c
+++ b/kernel/pm_qos_params.c
@@ -136,6 +136,16 @@ static s32 min_compare(s32 v1, s32 v2)
}
+static void update_target_val(int pm_qos_class, s32 val)
+{
+ s32 extreme_value;
+ s32 new_value;
+ extreme_value = atomic_read(&pm_qos_array[pm_qos_class]->target_value);
+ new_value = pm_qos_array[pm_qos_class]->comparitor(val,extreme_value);
+ if (extreme_value != new_value)
+ atomic_set(&pm_qos_array[pm_qos_class]->target_value,new_value);
+}
+
static void update_target(int pm_qos_class)
{
s32 extreme_value;
@@ -253,19 +263,24 @@ void pm_qos_update_request(struct pm_qos_request_list *pm_qos_req,
s32 temp;
if (pm_qos_req) { /*guard against callers passing in null */
+ int target = pm_qos_req->pm_qos_class;
spin_lock_irqsave(&pm_qos_lock, flags);
if (new_value == PM_QOS_DEFAULT_VALUE)
- temp = pm_qos_array[pm_qos_req->pm_qos_class]->default_value;
+ temp = pm_qos_array[target]->default_value;
else
temp = new_value;
if (temp != pm_qos_req->value) {
pending_update = 1;
pm_qos_req->value = temp;
+ update_target_val(target,temp);
}
spin_unlock_irqrestore(&pm_qos_lock, flags);
+
if (pending_update)
- update_target(pm_qos_req->pm_qos_class);
+ blocking_notifier_call_chain(
+ pm_qos_array[pm_qos_class]->notifiers,
+ (unsigned long) temp, NULL);
}
}
EXPORT_SYMBOL_GPL(pm_qos_update_request);
--
1.7.1
The new extreme value is only depending on the old extreme value and
the changed value.
Signed-off-by: Florian Mickler <[email protected]>
---
This version actually compiles... :)
kernel/pm_qos_params.c | 19 +++++++++++++++++--
1 files changed, 17 insertions(+), 2 deletions(-)
diff --git a/kernel/pm_qos_params.c b/kernel/pm_qos_params.c
index f42d3f7..3ae94e1 100644
--- a/kernel/pm_qos_params.c
+++ b/kernel/pm_qos_params.c
@@ -136,6 +136,16 @@ static s32 min_compare(s32 v1, s32 v2)
}
+static void update_target_val(int pm_qos_class, s32 val)
+{
+ s32 extreme_value;
+ s32 new_value;
+ extreme_value = atomic_read(&pm_qos_array[pm_qos_class]->target_value);
+ new_value = pm_qos_array[pm_qos_class]->comparitor(val,extreme_value);
+ if (extreme_value != new_value)
+ atomic_set(&pm_qos_array[pm_qos_class]->target_value,new_value);
+}
+
static void update_target(int pm_qos_class)
{
s32 extreme_value;
@@ -253,19 +263,24 @@ void pm_qos_update_request(struct pm_qos_request_list *pm_qos_req,
s32 temp;
if (pm_qos_req) { /*guard against callers passing in null */
+ int target = pm_qos_req->pm_qos_class;
spin_lock_irqsave(&pm_qos_lock, flags);
if (new_value == PM_QOS_DEFAULT_VALUE)
- temp = pm_qos_array[pm_qos_req->pm_qos_class]->default_value;
+ temp = pm_qos_array[target]->default_value;
else
temp = new_value;
if (temp != pm_qos_req->value) {
pending_update = 1;
pm_qos_req->value = temp;
+ update_target_val(target,temp);
}
spin_unlock_irqrestore(&pm_qos_lock, flags);
+
if (pending_update)
- update_target(pm_qos_req->pm_qos_class);
+ blocking_notifier_call_chain(
+ pm_qos_array[target]->notifiers,
+ (unsigned long) temp, NULL);
}
}
EXPORT_SYMBOL_GPL(pm_qos_update_request);
--
1.7.1
On Tue, 1 Jun 2010, [email protected] wrote:
> The new extreme value is only depending on the old extreme value and
> the changed value.
And how does that update to the next applicable constraint when the
current constraint is removed ? Your patch is creating a one way
decision.
> Signed-off-by: Florian Mickler <[email protected]>
> ---
> This version actually compiles... :)
That does not make it work.
tglx
On Tue, Jun 01, 2010 at 09:07:37AM +0200, Florian Mickler wrote:
> On Mon, 31 May 2010 16:26:17 -0700
> mark gross <[email protected]> wrote:
>
> > On Mon, May 31, 2010 at 11:38:55PM +0200, Rafael J. Wysocki wrote:
> > > On Monday 31 May 2010, Arve Hj?nnev?g wrote:
> > > > 2010/5/29 Alan Stern <[email protected]>:
> > > > > On Sat, 29 May 2010, Arve Hj?nnev?g wrote:
> > > > >
> > > > >> > In place of in-kernel suspend blockers, there will be a new type of QoS
> > > > >> > constraint -- call it QOS_EVENTUALLY. It's a very weak constraint,
> > > > >> > compatible with all cpuidle modes in which runnable threads are allowed
> > > > >> > to run (which is all of them), but not compatible with suspend.
> > > > >> >
> > > > >> This sound just like another API rename. It will work, but given that
> > > > >> suspend blockers was the name least objectionable last time around,
> > > > >> I'm not sure what this would solve.
> > > > >
> > > > > It's not just a rename. By changing this into a QoS constraint, we
> > > > > make it more generally useful. Instead of standing on its own, it
> > > > > becomes part of the PM-QOS framework.
> > > > >
> > > >
> > > > We cannot use the existing pm-qos framework. It is not safe to call
> > > > from atomic context.
> > >
> > > We've just merged a patch that fixed that if I'm not mistaken. Mark, did your
> > > PM QoS update fix that?
> > >
> >
> > I'm pretty sure it can be called in atomic context, and if its not I'm
> > sure we can fix that. It can be called in atomic context. I don't
> > think it was ever a problem to call it in atomic context. The problem it
> > had was that crappy list of string compares. Thats been fixed.
> >
> > --mgross
> >
>
> Well, the register call uses kzalloc. Apart from that I
> think we're good.
>
> The outstanding list traversals can be fixed also. (see below)
>
> Cheers,
> Flo
>
> From 66fdd76f8cc4be722dba3859ddadfe07e7a4b755 Mon Sep 17 00:00:00 2001
> From: Florian Mickler <[email protected]>
> Date: Tue, 1 Jun 2010 09:04:26 +0200
> Subject: [PATCH] pm_qos: remove unnecessary list-traversal
>
> The new extreme_value is only depending on the old extreme_value and
> the changing value.
>
> Signed-off-by: Florian Mickler <[email protected]>
> ---
> kernel/pm_qos_params.c | 20 ++++++++++++++------
> 1 files changed, 14 insertions(+), 6 deletions(-)
>
> diff --git a/kernel/pm_qos_params.c b/kernel/pm_qos_params.c
> index f42d3f7..6618e2c 100644
> --- a/kernel/pm_qos_params.c
> +++ b/kernel/pm_qos_params.c
> @@ -136,6 +136,16 @@ static s32 min_compare(s32 v1, s32 v2)
> }
>
>
> +static void update_target_val(int pm_qos_class, s32 val)
> +{
> + s32 extreme_value;
> + s32 new_value;
> + extreme_value = atomic_read(&pm_qos_array[pm_qos_class]->target_value);
> + new_value = pm_qos_array[pm_qos_class]->comparitor(val,extreme_value);
> + if (extreme_value != new_value)
> + atomic_set(&pm_qos_array[pm_qos_class]->target_value,new_value);
> +}
> +
Only works 1/2 the time, but I like the idea!
It fails to get the righ answer when constraints are reduced. But, this
idea is a good improvement i'll roll into the next pm_qos update!
thanks!
--mgross
> static void update_target(int pm_qos_class)
> {
> s32 extreme_value;
> @@ -227,8 +237,8 @@ struct pm_qos_request_list *pm_qos_add_request(int pm_qos_class, s32 value)
> spin_lock_irqsave(&pm_qos_lock, flags);
> list_add(&dep->list,
> &pm_qos_array[pm_qos_class]->requests.list);
> + update_target_val(pm_qos_class,dep->value);
> spin_unlock_irqrestore(&pm_qos_lock, flags);
> - update_target(pm_qos_class);
> }
>
> return dep;
> @@ -249,23 +259,21 @@ void pm_qos_update_request(struct pm_qos_request_list *pm_qos_req,
> s32 new_value)
> {
> unsigned long flags;
> - int pending_update = 0;
> s32 temp;
>
> if (pm_qos_req) { /*guard against callers passing in null */
> + int target = pm_qos_req->pm_qos_class;
> spin_lock_irqsave(&pm_qos_lock, flags);
> if (new_value == PM_QOS_DEFAULT_VALUE)
> - temp = pm_qos_array[pm_qos_req->pm_qos_class]->default_value;
> + temp = pm_qos_array[target]->default_value;
> else
> temp = new_value;
>
> if (temp != pm_qos_req->value) {
> - pending_update = 1;
> pm_qos_req->value = temp;
> + update_target_val(target,temp);
> }
> spin_unlock_irqrestore(&pm_qos_lock, flags);
> - if (pending_update)
> - update_target(pm_qos_req->pm_qos_class);
> }
> }
> EXPORT_SYMBOL_GPL(pm_qos_update_request);
> --
> 1.7.1
>
On Tue, Jun 01, 2010 at 10:46:54AM +0200, [email protected] wrote:
> The new extreme value is only depending on the old extreme value and
> the changed value.
>
> Signed-off-by: Florian Mickler <[email protected]>
> ---
> kernel/pm_qos_params.c | 19 +++++++++++++++++--
> 1 files changed, 17 insertions(+), 2 deletions(-)
>
> diff --git a/kernel/pm_qos_params.c b/kernel/pm_qos_params.c
> index f42d3f7..5d71c12 100644
> --- a/kernel/pm_qos_params.c
> +++ b/kernel/pm_qos_params.c
> @@ -136,6 +136,16 @@ static s32 min_compare(s32 v1, s32 v2)
> }
>
>
> +static void update_target_val(int pm_qos_class, s32 val)
> +{
> + s32 extreme_value;
> + s32 new_value;
> + extreme_value = atomic_read(&pm_qos_array[pm_qos_class]->target_value);
> + new_value = pm_qos_array[pm_qos_class]->comparitor(val,extreme_value);
> + if (extreme_value != new_value)
> + atomic_set(&pm_qos_array[pm_qos_class]->target_value,new_value);
> +}
> +
only works right when the new val is a more stringent constraint
(request) than what is already there. When removing or reducing a
constraint (request) the list still needs to be walked to get the new
aggregate request.
But its a really good optimization for 1/2 of the calls to pm_qos I
should have seen and included a long time ago! Thanks!
--mgross
> static void update_target(int pm_qos_class)
> {
> s32 extreme_value;
> @@ -253,19 +263,24 @@ void pm_qos_update_request(struct pm_qos_request_list *pm_qos_req,
> s32 temp;
>
> if (pm_qos_req) { /*guard against callers passing in null */
> + int target = pm_qos_req->pm_qos_class;
> spin_lock_irqsave(&pm_qos_lock, flags);
> if (new_value == PM_QOS_DEFAULT_VALUE)
> - temp = pm_qos_array[pm_qos_req->pm_qos_class]->default_value;
> + temp = pm_qos_array[target]->default_value;
> else
> temp = new_value;
>
> if (temp != pm_qos_req->value) {
> pending_update = 1;
> pm_qos_req->value = temp;
> + update_target_val(target,temp);
> }
> spin_unlock_irqrestore(&pm_qos_lock, flags);
> +
> if (pending_update)
> - update_target(pm_qos_req->pm_qos_class);
> + blocking_notifier_call_chain(
> + pm_qos_array[pm_qos_class]->notifiers,
> + (unsigned long) temp, NULL);
> }
> }
> EXPORT_SYMBOL_GPL(pm_qos_update_request);
> --
> 1.7.1
>
On Tue, 1 Jun 2010 07:05:19 -0700
mark gross <[email protected]> wrote:
>
> Only works 1/2 the time, but I like the idea!
> It fails to get the righ answer when constraints are reduced. But, this
> idea is a good improvement i'll roll into the next pm_qos update!
>
> thanks!
>
> --mgross
outch. shure. i had the binary block/unblock case in my mind. (where
the comparitor would be just the logical &&)
cheers,
Flo
On Tue, 1 Jun 2010 22:00:35 +0200
Florian Mickler <[email protected]> wrote:
> On Tue, 1 Jun 2010 07:05:19 -0700
> mark gross <[email protected]> wrote:
>
> >
> > Only works 1/2 the time, but I like the idea!
> > It fails to get the righ answer when constraints are reduced. But, this
> > idea is a good improvement i'll roll into the next pm_qos update!
> >
> > thanks!
> >
> > --mgross
>
> outch. shure. i had the binary block/unblock case in my mind. (where
> the comparitor would be just the logical &&)
And even there it wouldn't work in general. What about keeping the list
sorted? (Or using the rbtree implementation). Well, I'm getting some
sleep and tomorrow I will think about it some more.
> cheers,
> Flo
>
On Tue, Jun 01, 2010 at 09:07:37AM +0200, Florian Mickler wrote:
> On Mon, 31 May 2010 16:26:17 -0700
> mark gross <[email protected]> wrote:
>
> > On Mon, May 31, 2010 at 11:38:55PM +0200, Rafael J. Wysocki wrote:
> > > On Monday 31 May 2010, Arve Hj?nnev?g wrote:
> > > > 2010/5/29 Alan Stern <[email protected]>:
> > > > > On Sat, 29 May 2010, Arve Hj?nnev?g wrote:
> > > > >
> > > > >> > In place of in-kernel suspend blockers, there will be a new type of QoS
> > > > >> > constraint -- call it QOS_EVENTUALLY. It's a very weak constraint,
> > > > >> > compatible with all cpuidle modes in which runnable threads are allowed
> > > > >> > to run (which is all of them), but not compatible with suspend.
> > > > >> >
> > > > >> This sound just like another API rename. It will work, but given that
> > > > >> suspend blockers was the name least objectionable last time around,
> > > > >> I'm not sure what this would solve.
> > > > >
> > > > > It's not just a rename. By changing this into a QoS constraint, we
> > > > > make it more generally useful. Instead of standing on its own, it
> > > > > becomes part of the PM-QOS framework.
> > > > >
> > > >
> > > > We cannot use the existing pm-qos framework. It is not safe to call
> > > > from atomic context.
> > >
> > > We've just merged a patch that fixed that if I'm not mistaken. Mark, did your
> > > PM QoS update fix that?
> > >
> >
> > I'm pretty sure it can be called in atomic context, and if its not I'm
> > sure we can fix that. It can be called in atomic context. I don't
> > think it was ever a problem to call it in atomic context. The problem it
> > had was that crappy list of string compares. Thats been fixed.
> >
> > --mgross
> >
>
> Well, the register call uses kzalloc. Apart from that I
> think we're good.
registering shouldn't need to be called in atomic context. Its the
update_request that needs to be callible form atomic context.
--mgross
On Tue, Jun 1, 2010 at 7:05 AM, mark gross <[email protected]> wrote:
> On Tue, Jun 01, 2010 at 09:07:37AM +0200, Florian Mickler wrote:
...
>> +static void update_target_val(int pm_qos_class, s32 val)
>> +{
>> + ? ? s32 extreme_value;
>> + ? ? s32 new_value;
>> + ? ? extreme_value = atomic_read(&pm_qos_array[pm_qos_class]->target_value);
>> + ? ? new_value = pm_qos_array[pm_qos_class]->comparitor(val,extreme_value);
>> + ? ? if (extreme_value != new_value)
>> + ? ? ? ? ? ? atomic_set(&pm_qos_array[pm_qos_class]->target_value,new_value);
>> +}
>> +
>
> Only works 1/2 the time, but I like the idea!
> It fails to get the righ answer when constraints are reduced. ?But, this
> idea is a good improvement i'll roll into the next pm_qos update!
>
I think it would be a better idea to track your constraints with a
sorted data structure. That way you can to better than O(n) for both
directions. If you have a lot of constraints with the same value, it
may even be worthwhile to have a two stage structure where for
instance you use a rbtree for the unique values and list for identical
constraints.
--
Arve Hj?nnev?g
On Tue, 1 Jun 2010 12:43:21 +0200 (CEST)
Thomas Gleixner <[email protected]> wrote:
> On Tue, 1 Jun 2010, [email protected] wrote:
>
> > The new extreme value is only depending on the old extreme value and
> > the changed value.
>
> And how does that update to the next applicable constraint when the
> current constraint is removed ? Your patch is creating a one way
> decision.
keeping the list sorted or using an rbtree is the answer then.
if O(1) behaviour is needed maybe another constraint type could be
implemented. Maybe using a bool or even a bitmap (to allow for 32
constraint-values).
Is another constraint-type worthwile?
>
> > Signed-off-by: Florian Mickler <[email protected]>
> > ---
> > This version actually compiles... :)
>
> That does not make it work.
>
> tglx
indeed.
Cheers,
Flo
On Tue, Jun 01, 2010 at 08:50:02PM -0700, Arve Hj?nnev?g wrote:
> On Tue, Jun 1, 2010 at 7:05 AM, mark gross <[email protected]> wrote:
> > On Tue, Jun 01, 2010 at 09:07:37AM +0200, Florian Mickler wrote:
> ...
> >> +static void update_target_val(int pm_qos_class, s32 val)
> >> +{
> >> + ? ? s32 extreme_value;
> >> + ? ? s32 new_value;
> >> + ? ? extreme_value = atomic_read(&pm_qos_array[pm_qos_class]->target_value);
> >> + ? ? new_value = pm_qos_array[pm_qos_class]->comparitor(val,extreme_value);
> >> + ? ? if (extreme_value != new_value)
> >> + ? ? ? ? ? ? atomic_set(&pm_qos_array[pm_qos_class]->target_value,new_value);
> >> +}
> >> +
> >
> > Only works 1/2 the time, but I like the idea!
> > It fails to get the righ answer when constraints are reduced. ?But, this
> > idea is a good improvement i'll roll into the next pm_qos update!
> >
>
> I think it would be a better idea to track your constraints with a
> sorted data structure. That way you can to better than O(n) for both
> directions. If you have a lot of constraints with the same value, it
> may even be worthwhile to have a two stage structure where for
> instance you use a rbtree for the unique values and list for identical
> constraints.
I don't agree, we went through this tree vrs list discussion a few times
before in other areas of the kernel. Wherever the list tended to be
short, a simple list wins. However; we can try it, after we have some
metrics and stress test cases identified we can measure its effectivenes
against.
--mgross
2010/6/2 mark gross <[email protected]>:
> On Tue, Jun 01, 2010 at 08:50:02PM -0700, Arve Hj?nnev?g wrote:
>> On Tue, Jun 1, 2010 at 7:05 AM, mark gross <[email protected]> wrote:
>> > On Tue, Jun 01, 2010 at 09:07:37AM +0200, Florian Mickler wrote:
>> ...
>> >> +static void update_target_val(int pm_qos_class, s32 val)
>> >> +{
>> >> + ? ? s32 extreme_value;
>> >> + ? ? s32 new_value;
>> >> + ? ? extreme_value = atomic_read(&pm_qos_array[pm_qos_class]->target_value);
>> >> + ? ? new_value = pm_qos_array[pm_qos_class]->comparitor(val,extreme_value);
>> >> + ? ? if (extreme_value != new_value)
>> >> + ? ? ? ? ? ? atomic_set(&pm_qos_array[pm_qos_class]->target_value,new_value);
>> >> +}
>> >> +
>> >
>> > Only works 1/2 the time, but I like the idea!
>> > It fails to get the righ answer when constraints are reduced. ?But, this
>> > idea is a good improvement i'll roll into the next pm_qos update!
>> >
>>
>> I think it would be a better idea to track your constraints with a
>> sorted data structure. That way you can to better than O(n) for both
>> directions. If you have a lot of constraints with the same value, it
>> may even be worthwhile to have a two stage structure where for
>> instance you use a rbtree for the unique values and list for identical
>> constraints.
>
> I don't agree, we went through this tree vrs list discussion a few times
> before in other areas of the kernel. ?Wherever the list tended to be
> short, a simple list wins. ?However; we can try it, after we have some
> metrics and stress test cases identified we can measure its effectivenes
> against.
>
The list is not short. You have all the inactive and active
constraints on the same list. If you change it to a two level list
though, the list of unique values (which is the list you have to walk)
may be short enough for a tree to be overkill.
--
Arve Hj?nnev?g
On Wednesday 02 June 2010, mark gross wrote:
> On Tue, Jun 01, 2010 at 08:50:02PM -0700, Arve Hj?nnev?g wrote:
> > On Tue, Jun 1, 2010 at 7:05 AM, mark gross <[email protected]> wrote:
> > > On Tue, Jun 01, 2010 at 09:07:37AM +0200, Florian Mickler wrote:
> > ...
> > >> +static void update_target_val(int pm_qos_class, s32 val)
> > >> +{
> > >> + s32 extreme_value;
> > >> + s32 new_value;
> > >> + extreme_value = atomic_read(&pm_qos_array[pm_qos_class]->target_value);
> > >> + new_value = pm_qos_array[pm_qos_class]->comparitor(val,extreme_value);
> > >> + if (extreme_value != new_value)
> > >> + atomic_set(&pm_qos_array[pm_qos_class]->target_value,new_value);
> > >> +}
> > >> +
> > >
> > > Only works 1/2 the time, but I like the idea!
> > > It fails to get the righ answer when constraints are reduced. But, this
> > > idea is a good improvement i'll roll into the next pm_qos update!
> > >
> >
> > I think it would be a better idea to track your constraints with a
> > sorted data structure. That way you can to better than O(n) for both
> > directions. If you have a lot of constraints with the same value, it
> > may even be worthwhile to have a two stage structure where for
> > instance you use a rbtree for the unique values and list for identical
> > constraints.
>
> I don't agree, we went through this tree vrs list discussion a few times
> before in other areas of the kernel. Wherever the list tended to be
> short, a simple list wins. However; we can try it, after we have some
> metrics and stress test cases identified we can measure its effectivenes
> against.
How many different values are there to handle?
Rafael
On Thu, Jun 03, 2010 at 12:03:49AM +0200, Rafael J. Wysocki wrote:
> On Wednesday 02 June 2010, mark gross wrote:
> > On Tue, Jun 01, 2010 at 08:50:02PM -0700, Arve Hj?nnev?g wrote:
> > > On Tue, Jun 1, 2010 at 7:05 AM, mark gross <[email protected]> wrote:
> > > > On Tue, Jun 01, 2010 at 09:07:37AM +0200, Florian Mickler wrote:
> > > ...
> > > >> +static void update_target_val(int pm_qos_class, s32 val)
> > > >> +{
> > > >> + s32 extreme_value;
> > > >> + s32 new_value;
> > > >> + extreme_value = atomic_read(&pm_qos_array[pm_qos_class]->target_value);
> > > >> + new_value = pm_qos_array[pm_qos_class]->comparitor(val,extreme_value);
> > > >> + if (extreme_value != new_value)
> > > >> + atomic_set(&pm_qos_array[pm_qos_class]->target_value,new_value);
> > > >> +}
> > > >> +
> > > >
> > > > Only works 1/2 the time, but I like the idea!
> > > > It fails to get the righ answer when constraints are reduced. But, this
> > > > idea is a good improvement i'll roll into the next pm_qos update!
> > > >
> > >
> > > I think it would be a better idea to track your constraints with a
> > > sorted data structure. That way you can to better than O(n) for both
> > > directions. If you have a lot of constraints with the same value, it
> > > may even be worthwhile to have a two stage structure where for
> > > instance you use a rbtree for the unique values and list for identical
> > > constraints.
> >
> > I don't agree, we went through this tree vrs list discussion a few times
> > before in other areas of the kernel. Wherever the list tended to be
> > short, a simple list wins. However; we can try it, after we have some
> > metrics and stress test cases identified we can measure its effectivenes
> > against.
>
> How many different values are there to handle?
>
for the current pm_qos users its tiny. I've never heard of more than a
few < 10. However; for the new "interactive" class to provide suspend
blocker functionality, I expect the number to be up to 20.
but realistically I bet we never get more than 10ish.
One constraint constraint request per module from isr to user mode.
Once in user mode there would be only a few (assuming Android user
space) I think just from the power HAL, input HAL, and the RIL.
Still a pretty small number I don't think we need to worry about scaling
as much as we need to worry about performance.
--mgross
On Wed, Jun 02, 2010 at 02:58:30PM -0700, Arve Hj?nnev?g wrote:
> 2010/6/2 mark gross <[email protected]>:
> > On Tue, Jun 01, 2010 at 08:50:02PM -0700, Arve Hj?nnev?g wrote:
> >> On Tue, Jun 1, 2010 at 7:05 AM, mark gross <[email protected]> wrote:
> >> > On Tue, Jun 01, 2010 at 09:07:37AM +0200, Florian Mickler wrote:
> >> ...
> >> >> +static void update_target_val(int pm_qos_class, s32 val)
> >> >> +{
> >> >> + ? ? s32 extreme_value;
> >> >> + ? ? s32 new_value;
> >> >> + ? ? extreme_value = atomic_read(&pm_qos_array[pm_qos_class]->target_value);
> >> >> + ? ? new_value = pm_qos_array[pm_qos_class]->comparitor(val,extreme_value);
> >> >> + ? ? if (extreme_value != new_value)
> >> >> + ? ? ? ? ? ? atomic_set(&pm_qos_array[pm_qos_class]->target_value,new_value);
> >> >> +}
> >> >> +
> >> >
> >> > Only works 1/2 the time, but I like the idea!
> >> > It fails to get the righ answer when constraints are reduced. ?But, this
> >> > idea is a good improvement i'll roll into the next pm_qos update!
> >> >
> >>
> >> I think it would be a better idea to track your constraints with a
> >> sorted data structure. That way you can to better than O(n) for both
> >> directions. If you have a lot of constraints with the same value, it
> >> may even be worthwhile to have a two stage structure where for
> >> instance you use a rbtree for the unique values and list for identical
> >> constraints.
> >
> > I don't agree, we went through this tree vrs list discussion a few times
> > before in other areas of the kernel. ?Wherever the list tended to be
> > short, a simple list wins. ?However; we can try it, after we have some
> > metrics and stress test cases identified we can measure its effectivenes
> > against.
> >
>
> The list is not short. You have all the inactive and active
> constraints on the same list. If you change it to a two level list
> though, the list of unique values (which is the list you have to walk)
> may be short enough for a tree to be overkill.
what have you seen in practice from the wake-lock stats?
I'm having a hard time seeing where you could get more than just a
handfull. However; one could go to a dual list (like the scheduler) and
move inactive nodes from an active to inactive list, or we could simply
remove them from the list uppon inactivity. which would would well
after I change the api to have the client allocate the memory for the
nodes... BUT, if your moving things in and out of a list a lot, I'm not
sure the break even point where changing the structure helps.
We'll need to try it.
I think we will almost never see more than 10 list elements.
--mgross
On Wed, Jun 2, 2010 at 8:18 PM, mark gross <[email protected]> wrote:
> On Wed, Jun 02, 2010 at 02:58:30PM -0700, Arve Hjønnevåg wrote:
>>
>> The list is not short. You have all the inactive and active
>> constraints on the same list. If you change it to a two level list
>> though, the list of unique values (which is the list you have to walk)
>> may be short enough for a tree to be overkill.
>
> what have you seen in practice from the wake-lock stats?
>
> I'm having a hard time seeing where you could get more than just a
> handfull. However; one could go to a dual list (like the scheduler) and
> move inactive nodes from an active to inactive list, or we could simply
> remove them from the list uppon inactivity. which would would well
> after I change the api to have the client allocate the memory for the
> nodes... BUT, if your moving things in and out of a list a lot, I'm not
> sure the break even point where changing the structure helps.
>
> We'll need to try it.
>
> I think we will almost never see more than 10 list elements.
>
> --mgross
>
>
I see about 80 (based on the batteryinfo dump) on my Nexus One
(QSD8250, Android Froyo):
Kernel Wake lock "event5-86": (nothing executed)
Kernel Wake lock "PowerManagerService": 4m 27s 994ms (453 times) realtime
Kernel Wake lock "event4-92": 72ms (10 times) realtime
Kernel Wake lock "AudioHardwareQSDIn": (nothing executed)
Kernel Wake lock "event4-87": (nothing executed)
Kernel Wake lock "event5-82": (nothing executed)
Kernel Wake lock "event2-87": (nothing executed)
Kernel Wake lock "alarm_rtc": 21s 882ms (186 times) realtime
Kernel Wake lock "vdec_suspend": (nothing executed)
Kernel Wake lock "event6-87": (nothing executed)
Kernel Wake lock "event0-91": (nothing executed)
Kernel Wake lock "SMD_DS": 30s 938ms (53 times) realtime
Kernel Wake lock "event6-91": (nothing executed)
Kernel Wake lock "KeyEvents": 398ms (3226 times) realtime
Kernel Wake lock "qmi1": (nothing executed)
Kernel Wake lock "mmc_delayed_work": (nothing executed)
Kernel Wake lock "event3-82": (nothing executed)
Kernel Wake lock "event3-92": 58ms (6 times) realtime
Kernel Wake lock "SMD_RPCCALL": 295ms (1756 times) realtime
Kernel Wake lock "SMD_DATA6": (nothing executed)
Kernel Wake lock "audio_pcm_idle": 3s 99ms (1 times) realtime
Kernel Wake lock "serial-debug": (nothing executed)
Kernel Wake lock "event6-82": (nothing executed)
Kernel Wake lock "event3-86": (nothing executed)
Kernel Wake lock "event2-82": (nothing executed)
Kernel Wake lock "i2c": (nothing executed)
Kernel Wake lock "event2-86": (nothing executed)
Kernel Wake lock "event5-87": (nothing executed)
Kernel Wake lock "event4-86": (nothing executed)
Kernel Wake lock "event5-92": 4ms (21 times) realtime
Kernel Wake lock "rpc_server": (nothing executed)
Kernel Wake lock "power-supply": 527ms (8 times) realtime
Kernel Wake lock "radio-interface": 10s 11ms (10 times) realtime
Kernel Wake lock "event6-86": (nothing executed)
Kernel Wake lock "deleted_wake_locks": 203ms (214 times) realtime
Kernel Wake lock "qmi0": (nothing executed)
Kernel Wake lock "event2-91": (nothing executed)
Kernel Wake lock "event4-82": (nothing executed)
Kernel Wake lock "event7-82": (nothing executed)
Kernel Wake lock "dock": 27ms (1 times) realtime
Kernel Wake lock "SMD_DATA5": 1m 45s 121ms (158 times) realtime
Kernel Wake lock "event1-92": (nothing executed)
Kernel Wake lock "gpio_kp": (nothing executed)
Kernel Wake lock "event3-87": (nothing executed)
Kernel Wake lock "event7-92": (nothing executed)
Kernel Wake lock "msm_serial_hs_dma": (nothing executed)
Kernel Wake lock "event5-91": (nothing executed)
Kernel Wake lock "vbus_present": 517ms (1 times) realtime
Kernel Wake lock "alarm": 3s 229ms (249 times) realtime
Kernel Wake lock "event1-82": (nothing executed)
Kernel Wake lock "venc_suspend": (nothing executed)
Kernel Wake lock "event1-86": (nothing executed)
Kernel Wake lock "AudioHardwareQSDOut": 3s 98ms (1 times) realtime
Kernel Wake lock "event0-87": (nothing executed)
Kernel Wake lock "event2-92": 169ms (687 times) realtime
Kernel Wake lock "ds2784-battery": 12s 846ms (158 times) realtime
Kernel Wake lock "ApmCommandThread": 564ms (2 times) realtime
Kernel Wake lock "msmfb_idle_lock": 1s 495ms (715 times) realtime
Kernel Wake lock "headset": (nothing executed)
Kernel Wake lock "kgsl": 26s 473ms (123 times) realtime
Kernel Wake lock "venc_idle": (nothing executed)
Kernel Wake lock "event1-91": (nothing executed)
Kernel Wake lock "s5k3e2fx": (nothing executed)
Kernel Wake lock "usb_mass_storage": (nothing executed)
Kernel Wake lock "unknown_wakeups": (nothing executed)
Kernel Wake lock "vdec_idle": (nothing executed)
Kernel Wake lock "audio_pcm_suspend": 3s 99ms (1 times) realtime
Kernel Wake lock "microp_i2c_present": (nothing executed)
Kernel Wake lock "event4-91": (nothing executed)
Kernel Wake lock "event6-92": 182ms (86 times) realtime
Kernel Wake lock "event0-82": (nothing executed)
Kernel Wake lock "event0-92": 8ms (37 times) realtime
Kernel Wake lock "rpc_read": 112ms (1540 times) realtime
Kernel Wake lock "event0-86": (nothing executed)
Kernel Wake lock "msm_serial_hs_rx": (nothing executed)
Kernel Wake lock "qmi2": (nothing executed)
Kernel Wake lock "event1-87": (nothing executed)
Kernel Wake lock "msm_camera": (nothing executed)
Kernel Wake lock "rpc-interface": 2ms (1 times) realtime
Kernel Wake lock "main": 1m 38s 314ms (5 times) realtime
Kernel Wake lock "gpio_input": (nothing executed)
Kernel Wake lock "event3-91": (nothing executed)
Kernel Wake lock "SMD_DATA7": (nothing executed)
On Wed, Jun 02, 2010 at 09:54:15PM -0700, Brian Swetland wrote:
> On Wed, Jun 2, 2010 at 8:18 PM, mark gross <[email protected]> wrote:
> > On Wed, Jun 02, 2010 at 02:58:30PM -0700, Arve Hj?nnev?g wrote:
> >>
> >> The list is not short. You have all the inactive and active
> >> constraints on the same list. If you change it to a two level list
> >> though, the list of unique values (which is the list you have to walk)
> >> may be short enough for a tree to be overkill.
> >
> > what have you seen in practice from the wake-lock stats?
> >
> > I'm having a hard time seeing where you could get more than just a
> > handfull. ?However; one could go to a dual list (like the scheduler) and
> > move inactive nodes from an active to inactive list, or we could simply
> > remove them from the list uppon inactivity. ?which would would well
> > after I change the api to have the client allocate the memory for the
> > nodes... ?BUT, if your moving things in and out of a list a lot, I'm not
> > sure the break even point where changing the structure helps.
> >
> > We'll need to try it.
> >
> > I think we will almost never see more than 10 list elements.
> >
> > --mgross
> >
> >
>
> I see about 80 (based on the batteryinfo dump) on my Nexus One
> (QSD8250, Android Froyo):
shucks.
well I think for a pm_qos class that has boolean dynamic range we can
get away with not walking the list on every request update. we can use
a counter, and the list will be for mostly for stats.
> Kernel Wake lock "event5-86": (nothing executed)
> Kernel Wake lock "PowerManagerService": 4m 27s 994ms (453 times) realtime
> Kernel Wake lock "event4-92": 72ms (10 times) realtime
> Kernel Wake lock "AudioHardwareQSDIn": (nothing executed)
> Kernel Wake lock "event4-87": (nothing executed)
> Kernel Wake lock "event5-82": (nothing executed)
> Kernel Wake lock "event2-87": (nothing executed)
> Kernel Wake lock "alarm_rtc": 21s 882ms (186 times) realtime
> Kernel Wake lock "vdec_suspend": (nothing executed)
> Kernel Wake lock "event6-87": (nothing executed)
> Kernel Wake lock "event0-91": (nothing executed)
> Kernel Wake lock "SMD_DS": 30s 938ms (53 times) realtime
> Kernel Wake lock "event6-91": (nothing executed)
> Kernel Wake lock "KeyEvents": 398ms (3226 times) realtime
> Kernel Wake lock "qmi1": (nothing executed)
> Kernel Wake lock "mmc_delayed_work": (nothing executed)
> Kernel Wake lock "event3-82": (nothing executed)
> Kernel Wake lock "event3-92": 58ms (6 times) realtime
> Kernel Wake lock "SMD_RPCCALL": 295ms (1756 times) realtime
> Kernel Wake lock "SMD_DATA6": (nothing executed)
> Kernel Wake lock "audio_pcm_idle": 3s 99ms (1 times) realtime
> Kernel Wake lock "serial-debug": (nothing executed)
> Kernel Wake lock "event6-82": (nothing executed)
> Kernel Wake lock "event3-86": (nothing executed)
> Kernel Wake lock "event2-82": (nothing executed)
> Kernel Wake lock "i2c": (nothing executed)
> Kernel Wake lock "event2-86": (nothing executed)
> Kernel Wake lock "event5-87": (nothing executed)
> Kernel Wake lock "event4-86": (nothing executed)
> Kernel Wake lock "event5-92": 4ms (21 times) realtime
> Kernel Wake lock "rpc_server": (nothing executed)
> Kernel Wake lock "power-supply": 527ms (8 times) realtime
> Kernel Wake lock "radio-interface": 10s 11ms (10 times) realtime
> Kernel Wake lock "event6-86": (nothing executed)
> Kernel Wake lock "deleted_wake_locks": 203ms (214 times) realtime
> Kernel Wake lock "qmi0": (nothing executed)
> Kernel Wake lock "event2-91": (nothing executed)
> Kernel Wake lock "event4-82": (nothing executed)
> Kernel Wake lock "event7-82": (nothing executed)
> Kernel Wake lock "dock": 27ms (1 times) realtime
> Kernel Wake lock "SMD_DATA5": 1m 45s 121ms (158 times) realtime
> Kernel Wake lock "event1-92": (nothing executed)
> Kernel Wake lock "gpio_kp": (nothing executed)
> Kernel Wake lock "event3-87": (nothing executed)
> Kernel Wake lock "event7-92": (nothing executed)
> Kernel Wake lock "msm_serial_hs_dma": (nothing executed)
> Kernel Wake lock "event5-91": (nothing executed)
> Kernel Wake lock "vbus_present": 517ms (1 times) realtime
> Kernel Wake lock "alarm": 3s 229ms (249 times) realtime
> Kernel Wake lock "event1-82": (nothing executed)
> Kernel Wake lock "venc_suspend": (nothing executed)
> Kernel Wake lock "event1-86": (nothing executed)
> Kernel Wake lock "AudioHardwareQSDOut": 3s 98ms (1 times) realtime
> Kernel Wake lock "event0-87": (nothing executed)
> Kernel Wake lock "event2-92": 169ms (687 times) realtime
> Kernel Wake lock "ds2784-battery": 12s 846ms (158 times) realtime
> Kernel Wake lock "ApmCommandThread": 564ms (2 times) realtime
> Kernel Wake lock "msmfb_idle_lock": 1s 495ms (715 times) realtime
> Kernel Wake lock "headset": (nothing executed)
> Kernel Wake lock "kgsl": 26s 473ms (123 times) realtime
> Kernel Wake lock "venc_idle": (nothing executed)
> Kernel Wake lock "event1-91": (nothing executed)
> Kernel Wake lock "s5k3e2fx": (nothing executed)
> Kernel Wake lock "usb_mass_storage": (nothing executed)
> Kernel Wake lock "unknown_wakeups": (nothing executed)
> Kernel Wake lock "vdec_idle": (nothing executed)
> Kernel Wake lock "audio_pcm_suspend": 3s 99ms (1 times) realtime
> Kernel Wake lock "microp_i2c_present": (nothing executed)
> Kernel Wake lock "event4-91": (nothing executed)
> Kernel Wake lock "event6-92": 182ms (86 times) realtime
> Kernel Wake lock "event0-82": (nothing executed)
> Kernel Wake lock "event0-92": 8ms (37 times) realtime
> Kernel Wake lock "rpc_read": 112ms (1540 times) realtime
> Kernel Wake lock "event0-86": (nothing executed)
> Kernel Wake lock "msm_serial_hs_rx": (nothing executed)
> Kernel Wake lock "qmi2": (nothing executed)
> Kernel Wake lock "event1-87": (nothing executed)
> Kernel Wake lock "msm_camera": (nothing executed)
> Kernel Wake lock "rpc-interface": 2ms (1 times) realtime
> Kernel Wake lock "main": 1m 38s 314ms (5 times) realtime
> Kernel Wake lock "gpio_input": (nothing executed)
> Kernel Wake lock "event3-91": (nothing executed)
> Kernel Wake lock "SMD_DATA7": (nothing executed)
How much of this is portable to your next phone? I bet it was a big
effort to get these right too. FWIW I don't think most of these will
map into the moorestown port of android I'm working on.
This is why I really think a low power event framework would be cleaner
but, lets make everyone happy and expand pm_qos into a wake lock
re-implementation first.
--mgross
On Wed, Jun 2, 2010 at 10:40 PM, mark gross <[email protected]> wrote:
> On Wed, Jun 02, 2010 at 09:54:15PM -0700, Brian Swetland wrote:
>> On Wed, Jun 2, 2010 at 8:18 PM, mark gross <[email protected]> wrote:
>> > On Wed, Jun 02, 2010 at 02:58:30PM -0700, Arve Hj?nnev?g wrote:
>> >>
>> >> The list is not short. You have all the inactive and active
>> >> constraints on the same list. If you change it to a two level list
>> >> though, the list of unique values (which is the list you have to walk)
>> >> may be short enough for a tree to be overkill.
>> >
>> > what have you seen in practice from the wake-lock stats?
>> >
>> > I'm having a hard time seeing where you could get more than just a
>> > handfull. ?However; one could go to a dual list (like the scheduler) and
>> > move inactive nodes from an active to inactive list, or we could simply
>> > remove them from the list uppon inactivity. ?which would would well
>> > after I change the api to have the client allocate the memory for the
>> > nodes... ?BUT, if your moving things in and out of a list a lot, I'm not
>> > sure the break even point where changing the structure helps.
>> >
>> > We'll need to try it.
>> >
>> > I think we will almost never see more than 10 list elements.
>> >
>> > --mgross
>> >
>> >
>>
>> I see about 80 (based on the batteryinfo dump) on my Nexus One
>> (QSD8250, Android Froyo):
>
> shucks.
>
> well I think for a pm_qos class that has boolean dynamic range we can
> get away with not walking the list on every request update. ?we can use
> a counter, and the list will be for mostly for stats.
>
Did you give any thought to my suggestion to only use one entry per
unique value on the first level list and then use secondary lists of
identical values. That way if you only have two constraints values the
list you have to walk when updating a request will never have more
than two entries regardless of how many total request you have.
A request update then becomes something like this:
if on primary list {
unlink from primary list
if secondary list is not empty
get next secondary entry and add in same spot on primary list
}
unlink from secondary list
find new spot on primary list
if already there
add to secondary list
else
add to primary list
--
Arve Hj?nnev?g
On Wed, 2010-06-02 at 20:18 -0700, mark gross wrote:
> However; one could go to a dual list (like the scheduler) and
> move inactive nodes from an active to inactive list,
/me suggests you take a new look at the scheduler, those lists
disappeared more than 10 releases ago. We use RB-trees these days.
On Thu, Jun 03, 2010 at 12:10:03AM -0700, Arve Hj?nnev?g wrote:
> On Wed, Jun 2, 2010 at 10:40 PM, mark gross <[email protected]> wrote:
> > On Wed, Jun 02, 2010 at 09:54:15PM -0700, Brian Swetland wrote:
> >> On Wed, Jun 2, 2010 at 8:18 PM, mark gross <[email protected]> wrote:
> >> > On Wed, Jun 02, 2010 at 02:58:30PM -0700, Arve Hj?nnev?g wrote:
> >> >>
> >> >> The list is not short. You have all the inactive and active
> >> >> constraints on the same list. If you change it to a two level list
> >> >> though, the list of unique values (which is the list you have to walk)
> >> >> may be short enough for a tree to be overkill.
> >> >
> >> > what have you seen in practice from the wake-lock stats?
> >> >
> >> > I'm having a hard time seeing where you could get more than just a
> >> > handfull. ?However; one could go to a dual list (like the scheduler) and
> >> > move inactive nodes from an active to inactive list, or we could simply
> >> > remove them from the list uppon inactivity. ?which would would well
> >> > after I change the api to have the client allocate the memory for the
> >> > nodes... ?BUT, if your moving things in and out of a list a lot, I'm not
> >> > sure the break even point where changing the structure helps.
> >> >
> >> > We'll need to try it.
> >> >
> >> > I think we will almost never see more than 10 list elements.
> >> >
> >> > --mgross
> >> >
> >> >
> >>
> >> I see about 80 (based on the batteryinfo dump) on my Nexus One
> >> (QSD8250, Android Froyo):
> >
> > shucks.
> >
> > well I think for a pm_qos class that has boolean dynamic range we can
> > get away with not walking the list on every request update. ?we can use
> > a counter, and the list will be for mostly for stats.
> >
>
> Did you give any thought to my suggestion to only use one entry per
> unique value on the first level list and then use secondary lists of
> identical values. That way if you only have two constraints values the
I thought you where talking about a active + inactive queue. Sorry, I
didn't get what you where talking about.
> list you have to walk when updating a request will never have more
> than two entries regardless of how many total request you have.
>
> A request update then becomes something like this:
> if on primary list {
> unlink from primary list
> if secondary list is not empty
> get next secondary entry and add in same spot on primary list
> }
> unlink from secondary list
> find new spot on primary list
> if already there
> add to secondary list
> else
> add to primary list
>
I'm still no getting how this will allow me to reduce any aggregated
constratint re-computation to a list walk of at most 2 nodes. But, from
a more specific point of view are you saying:
change the request struct to be something like:
struct dual_list_constriaint {
struct list primary;
struct list secondar;
s32 value;
...
}
then uppon constraint foo update:
if foo->primary not empty:
remove foor from primary list
if gsecondary is not empty:
ordered insert of foo into secondary list
? ordered on constraint value?
? Arn't the constraints boolean?
remove foo from secondary list
ordered search for insert point of foo into primary list
if foo in primary:
insert foo into secondary list
else
insert foo into primary list
ok I'm not getting it.
is this a fancy com-sci algorithm I should know about?
--mgross
On Thu, Jun 03, 2010 at 10:04:29AM +0200, Peter Zijlstra wrote:
> On Wed, 2010-06-02 at 20:18 -0700, mark gross wrote:
> > However; one could go to a dual list (like the scheduler) and
> > move inactive nodes from an active to inactive list,
>
> /me suggests you take a new look at the scheduler, those lists
> disappeared more than 10 releases ago. We use RB-trees these days.
your dating me ;)
I haven't taken a hard look at the scheduler for a while.
/me hides.
--mgross
On Thu, 3 Jun 2010 00:10:03 -0700
Arve Hj?nnev?g <[email protected]> wrote:
> On Wed, Jun 2, 2010 at 10:40 PM, mark gross <[email protected]> wrote:
> > well I think for a pm_qos class that has boolean dynamic range we can
> > get away with not walking the list on every request update. ?we can use
> > a counter, and the list will be for mostly for stats.
> >
>
> Did you give any thought to my suggestion to only use one entry per
> unique value on the first level list and then use secondary lists of
> identical values. That way if you only have two constraints values the
> list you have to walk when updating a request will never have more
> than two entries regardless of how many total request you have.
>
> A request update then becomes something like this:
> if on primary list {
> unlink from primary list
> if secondary list is not empty
> get next secondary entry and add in same spot on primary list
> }
> unlink from secondary list
> find new spot on primary list
> if already there
> add to secondary list
> else
> add to primary list
>
Yes. I think that would be good. If we keep the primary list sorted,
then this becomes a nice priority queue implementation which does
GetMax in constant time and Insert and Delete in logarithmic
complexity to the number of different values.
Cheers,
Flo
On Thu, 3 Jun 2010 06:24:49 -0700
mark gross <[email protected]> wrote:
> On Thu, Jun 03, 2010 at 12:10:03AM -0700, Arve Hj?nnev?g wrote:
> ok I'm not getting it.
> is this a fancy com-sci algorithm I should know about?
>
> --mgross
I think you are at an advantage if you have studied fancy com-sci for
this? Here is an example:
say you have 5 constraints:
qos1 with a value of 10
qos2 with 5
qos3 with 10
qos4 with 11
Now, you hash that list by the qos-values:
11 ---- 10 ----- 5
| | |
qos4 qos3 qos2
|
qos1
To compute the maximum you just walk the "----" list.
To reduce qos4 from 11 to 5 you remove it from its "|" list and
prepend it to the corresponding "|" list. (4 Pointer adjustments +
searching the "-----" list for the right place to insert.
result:
10 ---- 5
| |
qos3 qos4
| |
qos1 qos2
Cheers,
Flo
On Thu, 2010-06-03 at 00:10 -0700, Arve Hjønnevåg wrote:
> On Wed, Jun 2, 2010 at 10:40 PM, mark gross <[email protected]> wrote:
> > On Wed, Jun 02, 2010 at 09:54:15PM -0700, Brian Swetland wrote:
> >> On Wed, Jun 2, 2010 at 8:18 PM, mark gross <[email protected]> wrote:
> >> > On Wed, Jun 02, 2010 at 02:58:30PM -0700, Arve Hjønnevåg wrote:
> >> >>
> >> >> The list is not short. You have all the inactive and active
> >> >> constraints on the same list. If you change it to a two level list
> >> >> though, the list of unique values (which is the list you have to walk)
> >> >> may be short enough for a tree to be overkill.
> >> >
> >> > what have you seen in practice from the wake-lock stats?
> >> >
> >> > I'm having a hard time seeing where you could get more than just a
> >> > handfull. However; one could go to a dual list (like the scheduler) and
> >> > move inactive nodes from an active to inactive list, or we could simply
> >> > remove them from the list uppon inactivity. which would would well
> >> > after I change the api to have the client allocate the memory for the
> >> > nodes... BUT, if your moving things in and out of a list a lot, I'm not
> >> > sure the break even point where changing the structure helps.
> >> >
> >> > We'll need to try it.
> >> >
> >> > I think we will almost never see more than 10 list elements.
> >> >
> >> > --mgross
> >> >
> >> >
> >>
> >> I see about 80 (based on the batteryinfo dump) on my Nexus One
> >> (QSD8250, Android Froyo):
> >
> > shucks.
> >
> > well I think for a pm_qos class that has boolean dynamic range we can
> > get away with not walking the list on every request update. we can use
> > a counter, and the list will be for mostly for stats.
> >
>
> Did you give any thought to my suggestion to only use one entry per
> unique value on the first level list and then use secondary lists of
> identical values. That way if you only have two constraints values the
> list you have to walk when updating a request will never have more
> than two entries regardless of how many total request you have.
>
> A request update then becomes something like this:
> if on primary list {
> unlink from primary list
> if secondary list is not empty
> get next secondary entry and add in same spot on primary list
> }
> unlink from secondary list
> find new spot on primary list
> if already there
> add to secondary list
> else
> add to primary list
This is just reinventing hash bucketed lists. To get the benefits, all
we do is implement an N state constraint as backed by an N bucketed hash
list, which the kernel already has all the internal mechanics for.
James
On Thu, 03 Jun 2010 09:36:34 -0500
James Bottomley <[email protected]> wrote:
> On Thu, 2010-06-03 at 00:10 -0700, Arve Hj?nnev?g wrote:
> > On Wed, Jun 2, 2010 at 10:40 PM, mark gross <[email protected]> wrote:
> > > On Wed, Jun 02, 2010 at 09:54:15PM -0700, Brian Swetland wrote:
> > >> On Wed, Jun 2, 2010 at 8:18 PM, mark gross <[email protected]> wrote:
> > >> > On Wed, Jun 02, 2010 at 02:58:30PM -0700, Arve Hj?nnev?g wrote:
> > >> >>
> > >> >> The list is not short. You have all the inactive and active
> > >> >> constraints on the same list. If you change it to a two level list
> > >> >> though, the list of unique values (which is the list you have to walk)
> > >> >> may be short enough for a tree to be overkill.
> > >> >
> > >> > what have you seen in practice from the wake-lock stats?
> > >> >
> > >> > I'm having a hard time seeing where you could get more than just a
> > >> > handfull. However; one could go to a dual list (like the scheduler) and
> > >> > move inactive nodes from an active to inactive list, or we could simply
> > >> > remove them from the list uppon inactivity. which would would well
> > >> > after I change the api to have the client allocate the memory for the
> > >> > nodes... BUT, if your moving things in and out of a list a lot, I'm not
> > >> > sure the break even point where changing the structure helps.
> > >> >
> > >> > We'll need to try it.
> > >> >
> > >> > I think we will almost never see more than 10 list elements.
> > >> >
> > >> > --mgross
> > >> >
> > >> >
> > >>
> > >> I see about 80 (based on the batteryinfo dump) on my Nexus One
> > >> (QSD8250, Android Froyo):
> > >
> > > shucks.
> > >
> > > well I think for a pm_qos class that has boolean dynamic range we can
> > > get away with not walking the list on every request update. we can use
> > > a counter, and the list will be for mostly for stats.
> > >
> >
> > Did you give any thought to my suggestion to only use one entry per
> > unique value on the first level list and then use secondary lists of
> > identical values. That way if you only have two constraints values the
> > list you have to walk when updating a request will never have more
> > than two entries regardless of how many total request you have.
> >
> > A request update then becomes something like this:
> > if on primary list {
> > unlink from primary list
> > if secondary list is not empty
> > get next secondary entry and add in same spot on primary list
> > }
> > unlink from secondary list
> > find new spot on primary list
> > if already there
> > add to secondary list
> > else
> > add to primary list
>
> This is just reinventing hash bucketed lists. To get the benefits, all
> we do is implement an N state constraint as backed by an N bucketed hash
> list, which the kernel already has all the internal mechanics for.
>
> James
>
http://www.itl.nist.gov/div897/sqg/dads/HTML/priorityque.html
So no reinvention. Just using a common scheme.
Cheers,
Flo
On Thu, 2010-06-03 at 17:17 +0200, Florian Mickler wrote:
> On Thu, 03 Jun 2010 09:36:34 -0500
> James Bottomley <[email protected]> wrote:
>
> > On Thu, 2010-06-03 at 00:10 -0700, Arve Hjønnevåg wrote:
> > > On Wed, Jun 2, 2010 at 10:40 PM, mark gross <[email protected]> wrote:
> > > > On Wed, Jun 02, 2010 at 09:54:15PM -0700, Brian Swetland wrote:
> > > >> On Wed, Jun 2, 2010 at 8:18 PM, mark gross <[email protected]> wrote:
> > > >> > On Wed, Jun 02, 2010 at 02:58:30PM -0700, Arve Hjønnevåg wrote:
> > > >> >>
> > > >> >> The list is not short. You have all the inactive and active
> > > >> >> constraints on the same list. If you change it to a two level list
> > > >> >> though, the list of unique values (which is the list you have to walk)
> > > >> >> may be short enough for a tree to be overkill.
> > > >> >
> > > >> > what have you seen in practice from the wake-lock stats?
> > > >> >
> > > >> > I'm having a hard time seeing where you could get more than just a
> > > >> > handfull. However; one could go to a dual list (like the scheduler) and
> > > >> > move inactive nodes from an active to inactive list, or we could simply
> > > >> > remove them from the list uppon inactivity. which would would well
> > > >> > after I change the api to have the client allocate the memory for the
> > > >> > nodes... BUT, if your moving things in and out of a list a lot, I'm not
> > > >> > sure the break even point where changing the structure helps.
> > > >> >
> > > >> > We'll need to try it.
> > > >> >
> > > >> > I think we will almost never see more than 10 list elements.
> > > >> >
> > > >> > --mgross
> > > >> >
> > > >> >
> > > >>
> > > >> I see about 80 (based on the batteryinfo dump) on my Nexus One
> > > >> (QSD8250, Android Froyo):
> > > >
> > > > shucks.
> > > >
> > > > well I think for a pm_qos class that has boolean dynamic range we can
> > > > get away with not walking the list on every request update. we can use
> > > > a counter, and the list will be for mostly for stats.
> > > >
> > >
> > > Did you give any thought to my suggestion to only use one entry per
> > > unique value on the first level list and then use secondary lists of
> > > identical values. That way if you only have two constraints values the
> > > list you have to walk when updating a request will never have more
> > > than two entries regardless of how many total request you have.
> > >
> > > A request update then becomes something like this:
> > > if on primary list {
> > > unlink from primary list
> > > if secondary list is not empty
> > > get next secondary entry and add in same spot on primary list
> > > }
> > > unlink from secondary list
> > > find new spot on primary list
> > > if already there
> > > add to secondary list
> > > else
> > > add to primary list
> >
> > This is just reinventing hash bucketed lists. To get the benefits, all
> > we do is implement an N state constraint as backed by an N bucketed hash
> > list, which the kernel already has all the internal mechanics for.
> >
> > James
> >
>
> http://www.itl.nist.gov/div897/sqg/dads/HTML/priorityque.html
>
> So no reinvention. Just using a common scheme.
By reinvention I meant open coding a common pattern for which the kernel
already has an API. (Whether we go with hash buckets or plists).
James
On Thu, 03 Jun 2010 10:29:52 -0500
James Bottomley <[email protected]> wrote:
> > So no reinvention. Just using a common scheme.
>
> By reinvention I meant open coding a common pattern for which the kernel
> already has an API. (Whether we go with hash buckets or plists).
>
> James
>
Ah, plists.h! Thanks for the pointer.
On Thursday 03 June 2010, mark gross wrote:
> On Thu, Jun 03, 2010 at 12:03:49AM +0200, Rafael J. Wysocki wrote:
> > On Wednesday 02 June 2010, mark gross wrote:
> > > On Tue, Jun 01, 2010 at 08:50:02PM -0700, Arve Hj?nnev?g wrote:
> > > > On Tue, Jun 1, 2010 at 7:05 AM, mark gross <[email protected]> wrote:
> > > > > On Tue, Jun 01, 2010 at 09:07:37AM +0200, Florian Mickler wrote:
> > > > ...
> > > > >> +static void update_target_val(int pm_qos_class, s32 val)
> > > > >> +{
> > > > >> + s32 extreme_value;
> > > > >> + s32 new_value;
> > > > >> + extreme_value = atomic_read(&pm_qos_array[pm_qos_class]->target_value);
> > > > >> + new_value = pm_qos_array[pm_qos_class]->comparitor(val,extreme_value);
> > > > >> + if (extreme_value != new_value)
> > > > >> + atomic_set(&pm_qos_array[pm_qos_class]->target_value,new_value);
> > > > >> +}
> > > > >> +
> > > > >
> > > > > Only works 1/2 the time, but I like the idea!
> > > > > It fails to get the righ answer when constraints are reduced. But, this
> > > > > idea is a good improvement i'll roll into the next pm_qos update!
> > > > >
> > > >
> > > > I think it would be a better idea to track your constraints with a
> > > > sorted data structure. That way you can to better than O(n) for both
> > > > directions. If you have a lot of constraints with the same value, it
> > > > may even be worthwhile to have a two stage structure where for
> > > > instance you use a rbtree for the unique values and list for identical
> > > > constraints.
> > >
> > > I don't agree, we went through this tree vrs list discussion a few times
> > > before in other areas of the kernel. Wherever the list tended to be
> > > short, a simple list wins. However; we can try it, after we have some
> > > metrics and stress test cases identified we can measure its effectivenes
> > > against.
> >
> > How many different values are there to handle?
> >
>
> for the current pm_qos users its tiny. I've never heard of more than a
> few < 10. However; for the new "interactive" class to provide suspend
> blocker functionality, I expect the number to be up to 20.
>
> but realistically I bet we never get more than 10ish.
>
> One constraint constraint request per module from isr to user mode.
> Once in user mode there would be only a few (assuming Android user
> space) I think just from the power HAL, input HAL, and the RIL.
>
> Still a pretty small number I don't think we need to worry about scaling
> as much as we need to worry about performance.
In that case sorting the structure is rather not going to improve things, but
it might be worth using a hashtable or something similar.
Rafael
On Thursday 03 June 2010, James Bottomley wrote:
> On Thu, 2010-06-03 at 00:10 -0700, Arve Hjønnevåg wrote:
> > On Wed, Jun 2, 2010 at 10:40 PM, mark gross <[email protected]> wrote:
> > > On Wed, Jun 02, 2010 at 09:54:15PM -0700, Brian Swetland wrote:
> > >> On Wed, Jun 2, 2010 at 8:18 PM, mark gross <[email protected]> wrote:
> > >> > On Wed, Jun 02, 2010 at 02:58:30PM -0700, Arve Hjønnevåg wrote:
> > >> >>
> > >> >> The list is not short. You have all the inactive and active
> > >> >> constraints on the same list. If you change it to a two level list
> > >> >> though, the list of unique values (which is the list you have to walk)
> > >> >> may be short enough for a tree to be overkill.
> > >> >
> > >> > what have you seen in practice from the wake-lock stats?
> > >> >
> > >> > I'm having a hard time seeing where you could get more than just a
> > >> > handfull. However; one could go to a dual list (like the scheduler) and
> > >> > move inactive nodes from an active to inactive list, or we could simply
> > >> > remove them from the list uppon inactivity. which would would well
> > >> > after I change the api to have the client allocate the memory for the
> > >> > nodes... BUT, if your moving things in and out of a list a lot, I'm not
> > >> > sure the break even point where changing the structure helps.
> > >> >
> > >> > We'll need to try it.
> > >> >
> > >> > I think we will almost never see more than 10 list elements.
> > >> >
> > >> > --mgross
> > >> >
> > >> >
> > >>
> > >> I see about 80 (based on the batteryinfo dump) on my Nexus One
> > >> (QSD8250, Android Froyo):
> > >
> > > shucks.
> > >
> > > well I think for a pm_qos class that has boolean dynamic range we can
> > > get away with not walking the list on every request update. we can use
> > > a counter, and the list will be for mostly for stats.
> > >
> >
> > Did you give any thought to my suggestion to only use one entry per
> > unique value on the first level list and then use secondary lists of
> > identical values. That way if you only have two constraints values the
> > list you have to walk when updating a request will never have more
> > than two entries regardless of how many total request you have.
> >
> > A request update then becomes something like this:
> > if on primary list {
> > unlink from primary list
> > if secondary list is not empty
> > get next secondary entry and add in same spot on primary list
> > }
> > unlink from secondary list
> > find new spot on primary list
> > if already there
> > add to secondary list
> > else
> > add to primary list
>
> This is just reinventing hash bucketed lists. To get the benefits, all
> we do is implement an N state constraint as backed by an N bucketed hash
> list, which the kernel already has all the internal mechanics for.
Agreed.
Rafael
On Thu, Jun 3, 2010 at 2:05 PM, Rafael J. Wysocki <[email protected]> wrote:
> On Thursday 03 June 2010, James Bottomley wrote:
>> On Thu, 2010-06-03 at 00:10 -0700, Arve Hj?nnev?g wrote:
>> > On Wed, Jun 2, 2010 at 10:40 PM, mark gross <[email protected]> wrote:
>> > > On Wed, Jun 02, 2010 at 09:54:15PM -0700, Brian Swetland wrote:
>> > >> On Wed, Jun 2, 2010 at 8:18 PM, mark gross <[email protected]> wrote:
>> > >> > On Wed, Jun 02, 2010 at 02:58:30PM -0700, Arve Hj?nnev?g wrote:
>> > >> >>
>> > >> >> The list is not short. You have all the inactive and active
>> > >> >> constraints on the same list. If you change it to a two level list
>> > >> >> though, the list of unique values (which is the list you have to walk)
>> > >> >> may be short enough for a tree to be overkill.
>> > >> >
>> > >> > what have you seen in practice from the wake-lock stats?
>> > >> >
>> > >> > I'm having a hard time seeing where you could get more than just a
>> > >> > handfull. ?However; one could go to a dual list (like the scheduler) and
>> > >> > move inactive nodes from an active to inactive list, or we could simply
>> > >> > remove them from the list uppon inactivity. ?which would would well
>> > >> > after I change the api to have the client allocate the memory for the
>> > >> > nodes... ?BUT, if your moving things in and out of a list a lot, I'm not
>> > >> > sure the break even point where changing the structure helps.
>> > >> >
>> > >> > We'll need to try it.
>> > >> >
>> > >> > I think we will almost never see more than 10 list elements.
>> > >> >
>> > >> > --mgross
>> > >> >
>> > >> >
>> > >>
>> > >> I see about 80 (based on the batteryinfo dump) on my Nexus One
>> > >> (QSD8250, Android Froyo):
>> > >
>> > > shucks.
>> > >
>> > > well I think for a pm_qos class that has boolean dynamic range we can
>> > > get away with not walking the list on every request update. ?we can use
>> > > a counter, and the list will be for mostly for stats.
>> > >
>> >
>> > Did you give any thought to my suggestion to only use one entry per
>> > unique value on the first level list and then use secondary lists of
>> > identical values. That way if you only have two constraints values the
>> > list you have to walk when updating a request will never have more
>> > than two entries regardless of how many total request you have.
>> >
>> > A request update then becomes something like this:
>> > ? if on primary list {
>> > ? ? unlink from primary list
>> > ? ? if secondary list is not empty
>> > ? ? ? get next secondary entry and add in same spot on primary list
>> > ? }
>> > ? unlink from secondary list
>> > ? find new spot on primary list
>> > ? if already there
>> > ? ? add to secondary list
>> > ? else
>> > ? ? add to primary list
>>
>> This is just reinventing hash bucketed lists. ?To get the benefits, all
>> we do is implement an N state constraint as backed by an N bucketed hash
>> list, which the kernel already has all the internal mechanics for.
>
> Agreed.
>
No, a hash is used for quick lookup of a specific value, not to find
an extreme value. It is however extremely similar to plists. The only
difference is that plists link all the secondary lists together. If we
want to have constraints that autoexpire, then keeping the secondary
lists separate allows the same optimization as I did for
wakelock/suspend_blocker timeouts where no timer is active if an
(equal or stricter) non-expiring constraint is active.
--
Arve Hj?nnev?g
On Thu, 3 Jun 2010 21:07:07 -0700
Arve Hj?nnev?g <[email protected]> wrote:
> On Thu, Jun 3, 2010 at 2:05 PM, Rafael J. Wysocki <[email protected]> wrote:
> > On Thursday 03 June 2010, James Bottomley wrote:
> >> On Thu, 2010-06-03 at 00:10 -0700, Arve Hj?nnev?g wrote:
> >> > A request update then becomes something like this:
> >> > ? if on primary list {
> >> > ? ? unlink from primary list
> >> > ? ? if secondary list is not empty
> >> > ? ? ? get next secondary entry and add in same spot on primary list
> >> > ? }
> >> > ? unlink from secondary list
> >> > ? find new spot on primary list
> >> > ? if already there
> >> > ? ? add to secondary list
> >> > ? else
> >> > ? ? add to primary list
> >>
> >> This is just reinventing hash bucketed lists. ?To get the benefits, all
> >> we do is implement an N state constraint as backed by an N bucketed hash
> >> list, which the kernel already has all the internal mechanics for.
> >
> > Agreed.
> >
>
> No, a hash is used for quick lookup of a specific value, not to find
> an extreme value. It is however extremely similar to plists. The only
> difference is that plists link all the secondary lists together. If we
> want to have constraints that autoexpire, then keeping the secondary
> lists separate allows the same optimization as I did for
> wakelock/suspend_blocker timeouts where no timer is active if an
> (equal or stricter) non-expiring constraint is active.
Can you give an example for the optimization or elaborate about the
negative effect of linking the secondary lists together? I don't
understand right now.
Would be hlist from list.h better? (I think that is what James is
referring to?) That is a (single-linked-)list of double-linked-lists.
Cheers,
Flo
On Thu, 2010-06-03 at 21:07 -0700, Arve Hjønnevåg wrote:
> On Thu, Jun 3, 2010 at 2:05 PM, Rafael J. Wysocki <[email protected]> wrote:
> > On Thursday 03 June 2010, James Bottomley wrote:
> >> On Thu, 2010-06-03 at 00:10 -0700, Arve Hjønnevåg wrote:
> >> > On Wed, Jun 2, 2010 at 10:40 PM, mark gross <[email protected]> wrote:
> >> > > On Wed, Jun 02, 2010 at 09:54:15PM -0700, Brian Swetland wrote:
> >> > >> On Wed, Jun 2, 2010 at 8:18 PM, mark gross <[email protected]> wrote:
> >> > >> > On Wed, Jun 02, 2010 at 02:58:30PM -0700, Arve Hjønnevåg wrote:
> >> > >> >>
> >> > >> >> The list is not short. You have all the inactive and active
> >> > >> >> constraints on the same list. If you change it to a two level list
> >> > >> >> though, the list of unique values (which is the list you have to walk)
> >> > >> >> may be short enough for a tree to be overkill.
> >> > >> >
> >> > >> > what have you seen in practice from the wake-lock stats?
> >> > >> >
> >> > >> > I'm having a hard time seeing where you could get more than just a
> >> > >> > handfull. However; one could go to a dual list (like the scheduler) and
> >> > >> > move inactive nodes from an active to inactive list, or we could simply
> >> > >> > remove them from the list uppon inactivity. which would would well
> >> > >> > after I change the api to have the client allocate the memory for the
> >> > >> > nodes... BUT, if your moving things in and out of a list a lot, I'm not
> >> > >> > sure the break even point where changing the structure helps.
> >> > >> >
> >> > >> > We'll need to try it.
> >> > >> >
> >> > >> > I think we will almost never see more than 10 list elements.
> >> > >> >
> >> > >> > --mgross
> >> > >> >
> >> > >> >
> >> > >>
> >> > >> I see about 80 (based on the batteryinfo dump) on my Nexus One
> >> > >> (QSD8250, Android Froyo):
> >> > >
> >> > > shucks.
> >> > >
> >> > > well I think for a pm_qos class that has boolean dynamic range we can
> >> > > get away with not walking the list on every request update. we can use
> >> > > a counter, and the list will be for mostly for stats.
> >> > >
> >> >
> >> > Did you give any thought to my suggestion to only use one entry per
> >> > unique value on the first level list and then use secondary lists of
> >> > identical values. That way if you only have two constraints values the
> >> > list you have to walk when updating a request will never have more
> >> > than two entries regardless of how many total request you have.
> >> >
> >> > A request update then becomes something like this:
> >> > if on primary list {
> >> > unlink from primary list
> >> > if secondary list is not empty
> >> > get next secondary entry and add in same spot on primary list
> >> > }
> >> > unlink from secondary list
> >> > find new spot on primary list
> >> > if already there
> >> > add to secondary list
> >> > else
> >> > add to primary list
> >>
> >> This is just reinventing hash bucketed lists. To get the benefits, all
> >> we do is implement an N state constraint as backed by an N bucketed hash
> >> list, which the kernel already has all the internal mechanics for.
> >
> > Agreed.
> >
>
> No, a hash is used for quick lookup of a specific value, not to find
> an extreme value.
If you only have N possible values an N bucket hash list is rather
efficient (provided N is small). But I would agree that knowing what N
is represents an API change, and since plists can do this without
changing the API, they're better.
> It is however extremely similar to plists. The only
> difference is that plists link all the secondary lists together.
Right, so they would solve the *current* problem exactly.
> If we
> want to have constraints that autoexpire, then keeping the secondary
> lists separate allows the same optimization as I did for
> wakelock/suspend_blocker timeouts where no timer is active if an
> (equal or stricter) non-expiring constraint is active.
But this is a future discussion and not part of the patch. The way open
source works is that we sort out the best implementation for the current
conditions. If the implementation has to change because of future
stuff, then we change it when the future stuff comes along. Changing
implementations is easy (they don't have any externally visible impact).
Changing the in-kernel API is slightly harder, but easily doable. It's
only changing the user visible ABI that we worry about and try not to
do.
James
On Thu, Jun 03, 2010 at 04:30:49PM +0200, Florian Mickler wrote:
> On Thu, 3 Jun 2010 06:24:49 -0700
> mark gross <[email protected]> wrote:
>
> > On Thu, Jun 03, 2010 at 12:10:03AM -0700, Arve Hj?nnev?g wrote:
>
> > ok I'm not getting it.
> > is this a fancy com-sci algorithm I should know about?
> >
> > --mgross
>
> I think you are at an advantage if you have studied fancy com-sci for
> this? Here is an example:
>
> say you have 5 constraints:
> qos1 with a value of 10
> qos2 with 5
> qos3 with 10
> qos4 with 11
>
> Now, you hash that list by the qos-values:
>
> 11 ---- 10 ----- 5
> | | |
> qos4 qos3 qos2
> |
> qos1
>
>
> To compute the maximum you just walk the "----" list.
>
> To reduce qos4 from 11 to 5 you remove it from its "|" list and
> prepend it to the corresponding "|" list. (4 Pointer adjustments +
> searching the "-----" list for the right place to insert.
>
> result:
>
> 10 ---- 5
> | |
> qos3 qos4
> | |
> qos1 qos2
>
> Cheers,
Oh! ok, thats easy!
Thanks!!!
--mgross
On Fri, Jun 04, 2010 at 09:23:10AM -0500, James Bottomley wrote:
> On Thu, 2010-06-03 at 21:07 -0700, Arve Hj?nnev?g wrote:
> > On Thu, Jun 3, 2010 at 2:05 PM, Rafael J. Wysocki <[email protected]> wrote:
> > > On Thursday 03 June 2010, James Bottomley wrote:
> > >> On Thu, 2010-06-03 at 00:10 -0700, Arve Hj?nnev?g wrote:
> > >> > On Wed, Jun 2, 2010 at 10:40 PM, mark gross <[email protected]> wrote:
> > >> > > On Wed, Jun 02, 2010 at 09:54:15PM -0700, Brian Swetland wrote:
> > >> > >> On Wed, Jun 2, 2010 at 8:18 PM, mark gross <[email protected]> wrote:
> > >> > >> > On Wed, Jun 02, 2010 at 02:58:30PM -0700, Arve Hj?nnev?g wrote:
> > >> > >> >>
> > >> > >> >> The list is not short. You have all the inactive and active
> > >> > >> >> constraints on the same list. If you change it to a two level list
> > >> > >> >> though, the list of unique values (which is the list you have to walk)
> > >> > >> >> may be short enough for a tree to be overkill.
> > >> > >> >
> > >> > >> > what have you seen in practice from the wake-lock stats?
> > >> > >> >
> > >> > >> > I'm having a hard time seeing where you could get more than just a
> > >> > >> > handfull. However; one could go to a dual list (like the scheduler) and
> > >> > >> > move inactive nodes from an active to inactive list, or we could simply
> > >> > >> > remove them from the list uppon inactivity. which would would well
> > >> > >> > after I change the api to have the client allocate the memory for the
> > >> > >> > nodes... BUT, if your moving things in and out of a list a lot, I'm not
> > >> > >> > sure the break even point where changing the structure helps.
> > >> > >> >
> > >> > >> > We'll need to try it.
> > >> > >> >
> > >> > >> > I think we will almost never see more than 10 list elements.
> > >> > >> >
> > >> > >> > --mgross
> > >> > >> >
> > >> > >> >
> > >> > >>
> > >> > >> I see about 80 (based on the batteryinfo dump) on my Nexus One
> > >> > >> (QSD8250, Android Froyo):
> > >> > >
> > >> > > shucks.
> > >> > >
> > >> > > well I think for a pm_qos class that has boolean dynamic range we can
> > >> > > get away with not walking the list on every request update. we can use
> > >> > > a counter, and the list will be for mostly for stats.
> > >> > >
> > >> >
> > >> > Did you give any thought to my suggestion to only use one entry per
> > >> > unique value on the first level list and then use secondary lists of
> > >> > identical values. That way if you only have two constraints values the
> > >> > list you have to walk when updating a request will never have more
> > >> > than two entries regardless of how many total request you have.
> > >> >
> > >> > A request update then becomes something like this:
> > >> > if on primary list {
> > >> > unlink from primary list
> > >> > if secondary list is not empty
> > >> > get next secondary entry and add in same spot on primary list
> > >> > }
> > >> > unlink from secondary list
> > >> > find new spot on primary list
> > >> > if already there
> > >> > add to secondary list
> > >> > else
> > >> > add to primary list
> > >>
> > >> This is just reinventing hash bucketed lists. To get the benefits, all
> > >> we do is implement an N state constraint as backed by an N bucketed hash
> > >> list, which the kernel already has all the internal mechanics for.
> > >
> > > Agreed.
> > >
> >
> > No, a hash is used for quick lookup of a specific value, not to find
> > an extreme value.
>
> If you only have N possible values an N bucket hash list is rather
> efficient (provided N is small). But I would agree that knowing what N
> is represents an API change, and since plists can do this without
> changing the API, they're better.
>
> > It is however extremely similar to plists. The only
> > difference is that plists link all the secondary lists together.
>
> Right, so they would solve the *current* problem exactly.
>
> > If we
> > want to have constraints that autoexpire, then keeping the secondary
> > lists separate allows the same optimization as I did for
> > wakelock/suspend_blocker timeouts where no timer is active if an
> > (equal or stricter) non-expiring constraint is active.
>
> But this is a future discussion and not part of the patch. The way open
> source works is that we sort out the best implementation for the current
> conditions. If the implementation has to change because of future
> stuff, then we change it when the future stuff comes along. Changing
> implementations is easy (they don't have any externally visible impact).
> Changing the in-kernel API is slightly harder, but easily doable. It's
> only changing the user visible ABI that we worry about and try not to
> do.
>
True.
The following is what I think I'll work on this weekend. (hopefully
have some sort of patch that at least compiles...)
Changes to pm_qos to enable "wakelock" or "suspend blocker" support:
Requirements:
1) atomic context support.
2) make updating request fast enough for hot path users.
3) Add a request class for "interactive_suspend", this particular
request has a dynamic range of 1 (its 0 or 1). If zero then ok to auto
suspend, if 1 then only user driven suspend. Whenever the aggregate
request changes value the registered notifiers are called.
Implementation:
* change api to have caller allocated the qos request structures. (solve
the kalloc issue)
* add plist use for constraint classes with hash-able dynamic ranges
* consider auto hashing / plist-ing everything. (most users of pm_qos
don't do any fancy stuff and tend to request the only 2 different
values, ever) but for now only request with dynamic range of 0,1 will
get the fancy lists.
I think the rest are implementation details.
--mgross
On Saturday 05 June 2010, mark gross wrote:
> On Fri, Jun 04, 2010 at 09:23:10AM -0500, James Bottomley wrote:
> > On Thu, 2010-06-03 at 21:07 -0700, Arve Hj?nnev?g wrote:
> > > On Thu, Jun 3, 2010 at 2:05 PM, Rafael J. Wysocki <[email protected]> wrote:
> > > > On Thursday 03 June 2010, James Bottomley wrote:
> > > >> On Thu, 2010-06-03 at 00:10 -0700, Arve Hj?nnev?g wrote:
> > > >> > On Wed, Jun 2, 2010 at 10:40 PM, mark gross <[email protected]> wrote:
> > > >> > > On Wed, Jun 02, 2010 at 09:54:15PM -0700, Brian Swetland wrote:
> > > >> > >> On Wed, Jun 2, 2010 at 8:18 PM, mark gross <[email protected]> wrote:
> > > >> > >> > On Wed, Jun 02, 2010 at 02:58:30PM -0700, Arve Hj?nnev?g wrote:
> > > >> > >> >>
> > > >> > >> >> The list is not short. You have all the inactive and active
> > > >> > >> >> constraints on the same list. If you change it to a two level list
> > > >> > >> >> though, the list of unique values (which is the list you have to walk)
> > > >> > >> >> may be short enough for a tree to be overkill.
> > > >> > >> >
> > > >> > >> > what have you seen in practice from the wake-lock stats?
> > > >> > >> >
> > > >> > >> > I'm having a hard time seeing where you could get more than just a
> > > >> > >> > handfull. However; one could go to a dual list (like the scheduler) and
> > > >> > >> > move inactive nodes from an active to inactive list, or we could simply
> > > >> > >> > remove them from the list uppon inactivity. which would would well
> > > >> > >> > after I change the api to have the client allocate the memory for the
> > > >> > >> > nodes... BUT, if your moving things in and out of a list a lot, I'm not
> > > >> > >> > sure the break even point where changing the structure helps.
> > > >> > >> >
> > > >> > >> > We'll need to try it.
> > > >> > >> >
> > > >> > >> > I think we will almost never see more than 10 list elements.
> > > >> > >> >
> > > >> > >> > --mgross
> > > >> > >> >
> > > >> > >> >
> > > >> > >>
> > > >> > >> I see about 80 (based on the batteryinfo dump) on my Nexus One
> > > >> > >> (QSD8250, Android Froyo):
> > > >> > >
> > > >> > > shucks.
> > > >> > >
> > > >> > > well I think for a pm_qos class that has boolean dynamic range we can
> > > >> > > get away with not walking the list on every request update. we can use
> > > >> > > a counter, and the list will be for mostly for stats.
> > > >> > >
> > > >> >
> > > >> > Did you give any thought to my suggestion to only use one entry per
> > > >> > unique value on the first level list and then use secondary lists of
> > > >> > identical values. That way if you only have two constraints values the
> > > >> > list you have to walk when updating a request will never have more
> > > >> > than two entries regardless of how many total request you have.
> > > >> >
> > > >> > A request update then becomes something like this:
> > > >> > if on primary list {
> > > >> > unlink from primary list
> > > >> > if secondary list is not empty
> > > >> > get next secondary entry and add in same spot on primary list
> > > >> > }
> > > >> > unlink from secondary list
> > > >> > find new spot on primary list
> > > >> > if already there
> > > >> > add to secondary list
> > > >> > else
> > > >> > add to primary list
> > > >>
> > > >> This is just reinventing hash bucketed lists. To get the benefits, all
> > > >> we do is implement an N state constraint as backed by an N bucketed hash
> > > >> list, which the kernel already has all the internal mechanics for.
> > > >
> > > > Agreed.
> > > >
> > >
> > > No, a hash is used for quick lookup of a specific value, not to find
> > > an extreme value.
> >
> > If you only have N possible values an N bucket hash list is rather
> > efficient (provided N is small). But I would agree that knowing what N
> > is represents an API change, and since plists can do this without
> > changing the API, they're better.
> >
> > > It is however extremely similar to plists. The only
> > > difference is that plists link all the secondary lists together.
> >
> > Right, so they would solve the *current* problem exactly.
> >
> > > If we
> > > want to have constraints that autoexpire, then keeping the secondary
> > > lists separate allows the same optimization as I did for
> > > wakelock/suspend_blocker timeouts where no timer is active if an
> > > (equal or stricter) non-expiring constraint is active.
> >
> > But this is a future discussion and not part of the patch. The way open
> > source works is that we sort out the best implementation for the current
> > conditions. If the implementation has to change because of future
> > stuff, then we change it when the future stuff comes along. Changing
> > implementations is easy (they don't have any externally visible impact).
> > Changing the in-kernel API is slightly harder, but easily doable. It's
> > only changing the user visible ABI that we worry about and try not to
> > do.
> >
>
> True.
>
> The following is what I think I'll work on this weekend. (hopefully
> have some sort of patch that at least compiles...)
>
>
> Changes to pm_qos to enable "wakelock" or "suspend blocker" support:
>
> Requirements:
> 1) atomic context support.
> 2) make updating request fast enough for hot path users.
> 3) Add a request class for "interactive_suspend", this particular
> request has a dynamic range of 1 (its 0 or 1). If zero then ok to auto
> suspend, if 1 then only user driven suspend. Whenever the aggregate
> request changes value the registered notifiers are called.
>
>
> Implementation:
> * change api to have caller allocated the qos request structures. (solve
> the kalloc issue)
> * add plist use for constraint classes with hash-able dynamic ranges
Please have a look at the patch James posted earlier today on linux-pm,
you were CCed.
Rafael
On Sat, Jun 05, 2010 at 09:07:32PM +0200, Rafael J. Wysocki wrote:
> On Saturday 05 June 2010, mark gross wrote:
> > On Fri, Jun 04, 2010 at 09:23:10AM -0500, James Bottomley wrote:
> > > On Thu, 2010-06-03 at 21:07 -0700, Arve Hj?nnev?g wrote:
> > > > On Thu, Jun 3, 2010 at 2:05 PM, Rafael J. Wysocki <[email protected]> wrote:
> > > > > On Thursday 03 June 2010, James Bottomley wrote:
> > > > >> On Thu, 2010-06-03 at 00:10 -0700, Arve Hj?nnev?g wrote:
> > > > >> > On Wed, Jun 2, 2010 at 10:40 PM, mark gross <[email protected]> wrote:
> > > > >> > > On Wed, Jun 02, 2010 at 09:54:15PM -0700, Brian Swetland wrote:
> > > > >> > >> On Wed, Jun 2, 2010 at 8:18 PM, mark gross <[email protected]> wrote:
> > > > >> > >> > On Wed, Jun 02, 2010 at 02:58:30PM -0700, Arve Hj?nnev?g wrote:
> > > > >> > >> >>
> > > > >> > >> >> The list is not short. You have all the inactive and active
> > > > >> > >> >> constraints on the same list. If you change it to a two level list
> > > > >> > >> >> though, the list of unique values (which is the list you have to walk)
> > > > >> > >> >> may be short enough for a tree to be overkill.
> > > > >> > >> >
> > > > >> > >> > what have you seen in practice from the wake-lock stats?
> > > > >> > >> >
> > > > >> > >> > I'm having a hard time seeing where you could get more than just a
> > > > >> > >> > handfull. However; one could go to a dual list (like the scheduler) and
> > > > >> > >> > move inactive nodes from an active to inactive list, or we could simply
> > > > >> > >> > remove them from the list uppon inactivity. which would would well
> > > > >> > >> > after I change the api to have the client allocate the memory for the
> > > > >> > >> > nodes... BUT, if your moving things in and out of a list a lot, I'm not
> > > > >> > >> > sure the break even point where changing the structure helps.
> > > > >> > >> >
> > > > >> > >> > We'll need to try it.
> > > > >> > >> >
> > > > >> > >> > I think we will almost never see more than 10 list elements.
> > > > >> > >> >
> > > > >> > >> > --mgross
> > > > >> > >> >
> > > > >> > >> >
> > > > >> > >>
> > > > >> > >> I see about 80 (based on the batteryinfo dump) on my Nexus One
> > > > >> > >> (QSD8250, Android Froyo):
> > > > >> > >
> > > > >> > > shucks.
> > > > >> > >
> > > > >> > > well I think for a pm_qos class that has boolean dynamic range we can
> > > > >> > > get away with not walking the list on every request update. we can use
> > > > >> > > a counter, and the list will be for mostly for stats.
> > > > >> > >
> > > > >> >
> > > > >> > Did you give any thought to my suggestion to only use one entry per
> > > > >> > unique value on the first level list and then use secondary lists of
> > > > >> > identical values. That way if you only have two constraints values the
> > > > >> > list you have to walk when updating a request will never have more
> > > > >> > than two entries regardless of how many total request you have.
> > > > >> >
> > > > >> > A request update then becomes something like this:
> > > > >> > if on primary list {
> > > > >> > unlink from primary list
> > > > >> > if secondary list is not empty
> > > > >> > get next secondary entry and add in same spot on primary list
> > > > >> > }
> > > > >> > unlink from secondary list
> > > > >> > find new spot on primary list
> > > > >> > if already there
> > > > >> > add to secondary list
> > > > >> > else
> > > > >> > add to primary list
> > > > >>
> > > > >> This is just reinventing hash bucketed lists. To get the benefits, all
> > > > >> we do is implement an N state constraint as backed by an N bucketed hash
> > > > >> list, which the kernel already has all the internal mechanics for.
> > > > >
> > > > > Agreed.
> > > > >
> > > >
> > > > No, a hash is used for quick lookup of a specific value, not to find
> > > > an extreme value.
> > >
> > > If you only have N possible values an N bucket hash list is rather
> > > efficient (provided N is small). But I would agree that knowing what N
> > > is represents an API change, and since plists can do this without
> > > changing the API, they're better.
> > >
> > > > It is however extremely similar to plists. The only
> > > > difference is that plists link all the secondary lists together.
> > >
> > > Right, so they would solve the *current* problem exactly.
> > >
> > > > If we
> > > > want to have constraints that autoexpire, then keeping the secondary
> > > > lists separate allows the same optimization as I did for
> > > > wakelock/suspend_blocker timeouts where no timer is active if an
> > > > (equal or stricter) non-expiring constraint is active.
> > >
> > > But this is a future discussion and not part of the patch. The way open
> > > source works is that we sort out the best implementation for the current
> > > conditions. If the implementation has to change because of future
> > > stuff, then we change it when the future stuff comes along. Changing
> > > implementations is easy (they don't have any externally visible impact).
> > > Changing the in-kernel API is slightly harder, but easily doable. It's
> > > only changing the user visible ABI that we worry about and try not to
> > > do.
> > >
> >
> > True.
> >
> > The following is what I think I'll work on this weekend. (hopefully
> > have some sort of patch that at least compiles...)
> >
> >
> > Changes to pm_qos to enable "wakelock" or "suspend blocker" support:
> >
> > Requirements:
> > 1) atomic context support.
> > 2) make updating request fast enough for hot path users.
> > 3) Add a request class for "interactive_suspend", this particular
> > request has a dynamic range of 1 (its 0 or 1). If zero then ok to auto
> > suspend, if 1 then only user driven suspend. Whenever the aggregate
> > request changes value the registered notifiers are called.
> >
> >
> > Implementation:
> > * change api to have caller allocated the qos request structures. (solve
> > the kalloc issue)
> > * add plist use for constraint classes with hash-able dynamic ranges
>
> Please have a look at the patch James posted earlier today on linux-pm,
> you were CCed.
>
I like James' post. I'm sorry I missed it before I sent this note, but
I'm really glad he's posted it. Now I can do some testing.
--mgross