linux-kernel - Re: [RFC PATCH v3] drivercore: Add driver probe deferral mechanism

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]

Message-ID: <7790.1316800223@turing-police.cc.vt.edu>
Date:	Fri, 23 Sep 2011 13:50:23 -0400
From:	Valdis.Kletnieks@...edu
To:	Grant Likely <grant.likely@...retlab.ca>
Cc:	Alan Cox <alan@...rguk.ukuu.org.uk>, Arnd Bergmann <arnd@...db.de>,
	Greg Kroah-Hartman <greg@...ah.com>,
	Mark Brown <broonie@...nsource.wolfsonmicro.com>,
	Manjunath GKondaiah <manjunath.gkondaiah@...aro.org>,
	linux-kernel@...r.kernel.org, Dilan Lee <dilee@...dia.com>,
	linux-arm-kernel@...ts.infradead.org
Subject: Re: [RFC PATCH v3] drivercore: Add driver probe deferral mechanism

On Thu, 22 Sep 2011 15:19:01 MDT, Grant Likely said:
> On Thu, Sep 22, 2011 at 2:29 PM, Alan Cox <alan@...rguk.ukuu.org.uk> wrote:
> > Definitely what is needed for some of the x86 SoC stuff and would let us
> > rip out some of the special case magic for the SCU discovery.
> >
> > First thing that strikes me is driver_bound kicks the processing queue
> > again. That seems odd - surely this isn't needed because any driver that
> > does initialise this time and may allow something else to get going will
> > queue the kick itself. Thus this seems to just add overhead.
> >
> > It all looks a bit O(N²) if we don't expect the drivers that might
> > trigger something else binding to just say 'hey I'm one of the
> > troublemakers'
> 
> The way I read it, absolute worst case is when every device but one
> depends on another device.  In that case I believe it will be
> O(Nlog(N)).  (Every device gets probed on the first pass, but only the
> last one gets probed.  Then it goes through N-1 devices to the result
> of only 1 more device getting probed, then N-2, etc.). 

That is indeed O(N**2) not Nlog(N).  The total number of probes is (N+1)(N)/2
To get it to O(Nlog(N)), you'd have to probe N devices the first pass, N/2 devices
on the second pass, N/4 on the third, and so on.


Content of type "application/pgp-signature" skipped