linux-kernel - Re: [linux-pm] [PATCH 0/8] Suspend block api (version 8)

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Thu, 3 Jun 2010 21:07:07 -0700
From:	Arve Hjønnevåg <arve@...roid.com>
To:	"Rafael J. Wysocki" <rjw@...k.pl>
Cc:	James Bottomley <James.Bottomley@...e.de>, markgross@...gnar.org,
	640e9920@...il.com, Peter Zijlstra <peterz@...radead.org>,
	Brian Swetland <swetland@...gle.com>,
	Ingo Molnar <mingo@...e.hu>,
	LKML <linux-kernel@...r.kernel.org>,
	Florian Mickler <florian@...kler.org>,
	Linux PM <linux-pm@...ts.linux-foundation.org>,
	Thomas Gleixner <tglx@...utronix.de>,
	Alan Cox <alan@...rguk.ukuu.org.uk>
Subject: Re: [linux-pm] [PATCH 0/8] Suspend block api (version 8)

On Thu, Jun 3, 2010 at 2:05 PM, Rafael J. Wysocki <rjw@...k.pl> 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 <640e9920@...il.com> 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 <640e9920@...il.com> 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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/