linux-kernel - Re: [patch 00/13] Syslets, "Threadlets", generic AIO support, v3

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 for Android: free password hash cracker in your pocket

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

Message-ID: <20070227101332.GB23170@2ka.mipt.ru>
Date:	Tue, 27 Feb 2007 13:13:32 +0300
From:	Evgeniy Polyakov <johnpol@....mipt.ru>
To:	Davide Libenzi <davidel@...ilserver.org>
Cc:	Ingo Molnar <mingo@...e.hu>, Ulrich Drepper <drepper@...hat.com>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Arjan van de Ven <arjan@...radead.org>,
	Christoph Hellwig <hch@...radead.org>,
	Andrew Morton <akpm@....com.au>,
	Alan Cox <alan@...rguk.ukuu.org.uk>,
	Zach Brown <zach.brown@...cle.com>,
	"David S. Miller" <davem@...emloft.net>,
	Suparna Bhattacharya <suparna@...ibm.com>,
	Jens Axboe <jens.axboe@...cle.com>,
	Thomas Gleixner <tglx@...utronix.de>
Subject: Re: [patch 00/13] Syslets, "Threadlets", generic AIO support, v3

On Mon, Feb 26, 2007 at 06:18:51PM -0800, Davide Libenzi (davidel@...ilserver.org) wrote:
> On Mon, 26 Feb 2007, Evgeniy Polyakov wrote:
> 
> > 2. its notifications do not go through the second loop, i.e. it is O(1),
> > not O(ready_num), and notifications happens directly from internals of
> > the appropriate subsystem, which does not require special wakeup
> > (although it can be done too).
> 
> Sorry if I do not read kevent code correctly, but in kevent_user_wait() 
> there is a:
> 
>     while (num < max_nr && ((k = kevent_dequeue_ready(u)) != NULL)) {
>         ...
>     }
> 
> loop, that make it O(ready_num). From a mathematical standpoint, they're 
> both O(ready_num), but epoll is doing three passes over the ready set.
> I always though that if the number of ready events is so big that the more 
> passes over the ready set becomes relevant, probably the "work" done by 
> userspace for each fetched event would make the extra cost irrelevant.
> But that can be fixed by a patch that will follow on lkml ...
 
No, kevent_dequeue_ready() copies data to userspace, that is it.
So it looks roughly following:

storage is ready: -> kevent_requee() - ends up in ading event to the end
of the queue (list add under spinlock)

kevent_wait() -> copy first, second, ...

Kevent poll (as long as epoll) model requires _additional_ check in 
userspace context before it is copied, so we endup with checking the 
full ready queue again - that what I pointed as O(ready_num), O() implies 
price for copying to userspace, list_add and so on.
 
> - Davide
> 

-- 
	Evgeniy Polyakov
-
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/