Messages in this thread | | | Date | Sat, 26 Sep 2009 03:05:22 -0400 | From | Mathieu Desnoyers <> | Subject | Re: [RFC] Userspace RCU: (ab)using futexes to save cpu cycles and energy |
| |
* Mathieu Desnoyers (mathieu.desnoyers@polymtl.ca) wrote: > * Chris Friesen (cfriesen@nortel.com) wrote: > > On 09/23/2009 04:32 PM, Mathieu Desnoyers wrote: > > > > > > > /* > > > * Defer thread waiting. Single thread. > > > */ > > > static void wait_defer(void) > > > { > > > atomic_dec(&defer_thread_futex); > > > smp_mb(); /* Write futex before read queue */ > > > if (rcu_defer_num_callbacks()) { > > > smp_mb(); /* Read queue before write futex */ > > > /* Callbacks are queued, don't wait. */ > > > atomic_set(&defer_thread_futex, 0); > > > } else { > > > smp_rmb(); /* Read queue before read futex */ > > > if (atomic_read(&defer_thread_futex) == -1) > > > futex(&defer_thread_futex, FUTEX_WAIT, -1, > > > NULL, NULL, 0); > > > } > > > } > > > > > The goal here is that if call_rcu() enqueues a callback (even if it > > > races with defer thread going to sleep), there should not be a > > > potentially infinite delay before it gets executed. > > > > It doesn't seem like the test for the number of callbacks should be > > necessary. I don't see anything like that in the glibc code, nor do I > > remember anything like that in the futex sample code. > > > > The mutex code (and usual futex users) use futex to implement mutual > exclusion. My goal is to send a wakeup signal to a thread waiting for > work to perform when adding such work. But without any mutual exclusion. > > So it is understandable that glibc code or futex sample code does not > cover that, given this use is, well, creative. ;) > > > I'm still not totally convinced that you can avoid race conditions > > without using atomic test-and-set or compare-and-exchange. I haven't > > sat down and worked it out completely though. > > > > Yes.. this is heavily dependent on the states and values which can be > reached. I should probably take time to create a promela model and run > that though the spin model checker to be sure. >
Just created a Promela model for this. It assumes sequential memory ordering (so it's a fairly simplified model). Given I added memory barriers between each operation, it should well represent reality though.
My algorithm seems to behave as expected: when a callback is added to the queue, it's not possible to have the waiter thread blocked until the end of days.
Available at: http://www.lttng.org/cgi-bin/gitweb.cgi?p=userspace-rcu.git;a=blob;f=formal-model/futex-wakeup/futex.spin
Thanks,
Mathieu
> Thanks for the comments, > > Mathieu > > > Chris > > -- > Mathieu Desnoyers > OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
-- Mathieu Desnoyers OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
| |