linux-kernel - Re: [PATCH v2] epoll: Support for disabling items, and a self-test app.

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: <CCA6A06A.10264%pholland@adobe.com>
Date:	Fri, 19 Oct 2012 06:29:08 -0700
From:	Paul Holland <pholland@...be.com>
To:	Paolo Bonzini <pbonzini@...hat.com>,
	Andy Lutomirski <luto@...capital.net>
CC:	Andrew Morton <akpm@...ux-foundation.org>,
	"mtk.manpages@...il.com" <mtk.manpages@...il.com>,
	Paton Lewis <palewis@...be.com>,
	Alexander Viro <viro@...iv.linux.org.uk>,
	Jason Baron <jbaron@...hat.com>,
	"linux-fsdevel@...r.kernel.org" <linux-fsdevel@...r.kernel.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	Davide Libenzi <davidel@...ilserver.org>,
	"libc-alpha@...rceware.org" <libc-alpha@...rceware.org>,
	Linux API <linux-api@...r.kernel.org>,
	"paulmck@...ux.vnet.ibm.com" <paulmck@...ux.vnet.ibm.com>
Subject: Re: [PATCH v2] epoll: Support for disabling items, and a self-test
 app.

On 10/19/12 6:03 AM, "Paolo Bonzini" <pbonzini@...hat.com> wrote:

>Il 18/10/2012 20:05, Andy Lutomirski ha scritto:
>> 
>> Unless something is rather buggy in kernel land (and I don't think it
>> is), once EPOLL_CTL_DEL has returned, no call to epoll_wait that starts
>> *after* EPOLL_CTL_DEL finishes will return that object.  This suggests
>> an RCU-like approach: once EPOLL_CTL_DEL has returned and every thread
>> has returned from an epoll_wait call that started after the
>> EPOLL_CTL_DEL returns, then the data structure can be safely freed.
>> 
>> In pseudocode:
>> 
>> delete(fd, pdata) {
>>   pdata->dead = true;
>>   EPOLL_CTL_DEL(fd);
>>   rcu_call(delete pdata);
>> }
>> 
>> wait() {
>>   epoll_wait;
>>   for each event pdata {
>>     if (pdata->gone) continue;
>>     process the event;
>>   }
>> 
>>   rcu_this_is_a_grace_period();
>> }
>> 
>> Of course, these are not normal grace periods and would need to be
>> tracked separately.  (The optimal data structure to do this without
>> killing scalability is not obvious.  urcu presumably implements such a
>> thing.)
>> 
>> Am I right?
>
>Equip each thread with a) an id or something else that lets each thread
>refer to "the next" thread; b) a lists of "items waiting to be deleted".
> Then the deleting thread adds the item being deleted to the first
>thread's list.  Before executing epoll_wait, thread K empties its list
>and passes the buck, appending the old contents of its list to that of
>thread K+1.  This is an O(1) operation no matter how many items are
>being deleted; only Thread N, being the last thread, actually has to go
>through the list and delete the items.
>
>The lists need to be protected by a mutex, but contention should really
>be rare since there are just two writers.  Note that each thread only
>needs to hold one mutex at a time, and the deletion loop does not need
>to happen with the mutex held at all, so there's no worries of
>"cascading" waits on the mutexes.
>
>Compared to http://thread.gmane.org/gmane.linux.kernel/1311457, you get
>rid of the per-item mutex and the operations that have to be done with
>the (now per-thread) mutex held remain pretty trivial.
>
>Paolo

A disadvantage of solutions in this direction, which was not preset in
Paton's patch, is that all calls to epoll_wait would need to specify some
timeout value (!= -1) to guarantee that they each come out of epoll_wait
and execute the "pass the buck" or "grace_period" logic.  So you would
then have contention between designs that want highly responsive "delete"
operations (those would require very short timeout values to epoll_wait)
and those that want low execution overhead (those would want larger
timeout values).


>

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