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]

Date:	Tue, 27 Feb 2007 08:01:05 -0800 (PST)
From:	Davide Libenzi <davidel@...ilserver.org>
To:	Evgeniy Polyakov <johnpol@....mipt.ru>
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 Tue, 27 Feb 2007, Evgeniy Polyakov wrote:

> 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:

In all the books where I studied, the algorithms below would be classified 
as O(num_ready) ones:

[sys_kevent_wait]
+	for (i=0; i<num; ++i) {
+		k = kevent_dequeue_ready_ring(u);
+		if (!k)
+			break;
+		kevent_complete_ready(k);
+
+		if (k->event.ret_flags & KEVENT_RET_COPY_FAILED)
+			break;
+		kevent_stat_ring(u);
+		copied++;
+	}

[kevent_user_wait]
+	while (num < max_nr && ((k = kevent_dequeue_ready(u)) != NULL)) {
+		if (copy_to_user(buf + num*sizeof(struct ukevent),
+					&k->event, sizeof(struct ukevent))) {
+			if (num == 0)
+				num = -EFAULT;
+			break;
+		}
+		kevent_complete_ready(k);
+		++num;
+		kevent_stat_wait(u);
+	}

It does not matter if inside the loop you invert a 20Kx20K matrix or you 
copy a byte, they both are O(num_ready).



- Davide


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