[lttng-dev] Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

[Mathieu Desnoyers]

----- Original Message -----
> From: "Lai Jiangshan" <laijs at cn.fujitsu.com>
> To: "Mathieu Desnoyers" <mathieu.desnoyers at efficios.com>
> Cc: "Paul E. McKenney" <paulmck at linux.vnet.ibm.com>, "lttng-dev" <lttng-dev at lists.lttng.org>, "Ben Maurer"
> <bmaurer at fb.com>, "Yannick Brosseau" <scientist at fb.com>
> Sent: Thursday, October 23, 2014 5:28:24 AM
> Subject: Re: [lttng-dev] Userspace RCU: workqueue with batching, cheap wakeup, and work stealing
> 
> Hi Mathieu:
> 
> what happen when the wait_node is still queued when urcu_worker_unregister()
> is called?

Hrm, I think this could indeed be an issue. I'm thinking to add a "shutdown"
mode to the workqueue (similarly to folly lifosem). Perhaps this could help
us handling this situation.

> 
> On 10/23/2014 12:26 PM, Lai Jiangshan wrote:
[...]
> > 
> > Hi, Mathieu
> > 
> > In the code, how this problem be solved?
> > "All the tasks may continue stealing works without any progress."
> 
> Can __urcu_wakeup_siblings() be moved to the end of the urcu_dequeue_work()?

It might help, but I don't think it would solve the theoretical
lack-of-progress issue. If we are in a state where all workers threads
are running, none need to be awakened to steal work, and they could fall
into an endless cycle of work-stealing followed by facing an empty work
queue due to another concurrent stealing. I think getting threads to keep
one work item for themselves when they grab work from the global queue
or steal work offers better forward progress guarantees in this case.

> 
> > 
> > Why ___urcu_steal_work() needs cds_wfcq_dequeue_lock()?
> Sorry, it does need, it locks the source queue...
> but we have cds_wfcq_splice_blocking() which wrap the locking and the
> splicing.

Yes,

> 
> > 
> > It is not a good idea for a worker to call synchronize_rcu() (in
> > urcu_accept_work()).
> > A new work may be coming soon.
> 
> 
> I suggest to add a new API:
> __cds_lfs_pop_if(stack, expect) {
> 	atomic {
> 		if the top == expect {
> 			pop it;
> 		}
> 	}
> }
> 
> Then all the worker can only be woken up by urcu_adaptative_wake_up(),
> rather than urcu_dequeue_wake_single().
> 
> workers dequeues itself when successfully urcu_accept_work() by using
> __cds_lfs_pop_if().

There is something I don't like about this approach: what if, for some
reason, a worker being awakened takes a lot of time to start running.
It would therefore stall the entire waitqueue until it can be executed
and pop itself from the waitqueue.

Thoughts ?

Thanks!

Mathieu

> 
> Thanks,
> Lai
> 
> > 
> > thanks,
> > Lai
> > 
> > On 10/22/2014 07:20 PM, Mathieu Desnoyers wrote:
> >> Hi Lai,
> >>
> >> I pushed a few updates within the past days, including one
> >> fixing this issue. The updated branch is available at:
> >>
> >> git://git.urcu.so/urcu.git
> >> branch: urcu/workqueue-wakeup
> >>
> >> gitweb:
> >> http://git.lttng.org/?p=userspace-rcu.git;a=shortlog;h=refs/heads/urcu/workqueue-wakeup
> >>
> >> Please let me know if you notice anything else,
> >>
> >> Thanks!
> >>
> >> Mathieu
> >>
> >> ----- Original Message -----
> >>> From: "Lai Jiangshan" <laijs at cn.fujitsu.com>
> >>> To: "Mathieu Desnoyers" <mathieu.desnoyers at efficios.com>
> >>> Cc: "Ben Maurer" <bmaurer at fb.com>, "lttng-dev"
> >>> <lttng-dev at lists.lttng.org>, "Yannick Brosseau" <scientist at fb.com>,
> >>> "Paul E. McKenney" <paulmck at linux.vnet.ibm.com>, "Stephen Hemminger"
> >>> <stephen at networkplumber.org>
> >>> Sent: Wednesday, October 22, 2014 6:57:18 AM
> >>> Subject: Re: Userspace RCU: workqueue with batching, cheap wakeup, and
> >>> work stealing
> >>>
> >>> Hi
> >>>
> >>> I just glance the code quickly...
> >>>
> >>> __urcu_steal_work() and __urcu_wakeup_siblings don't test
> >>> if they visit the queue->sibling_head.
> >>>
> >>> All the tasks may continue stealing works without any progress.
> >>>
> >>> Thanks,
> >>> Lai
> >>>
> >>> On 10/19/2014 05:13 AM, Mathieu Desnoyers wrote:
> >>>> Hi,
> >>>>
> >>>> I have written an implementation of a workqueue based
> >>>> on wfcqueue (fifo workqueue), wfstack (lifo wait queue)
> >>>> including a work-stealing scheme. I think this could
> >>>> scale very naturally to large workloads, and it skips
> >>>> the overhead of sys_futex when wakees are already running.
> >>>> Since the wakeup scheme is very lightweight when work
> >>>> is ongoing, we use it extensively.
> >>>>
> >>>> It also makes extensive use of wfcqueue "splice" operation
> >>>> to move work batch in bulk amongst queue and worker
> >>>> threads. It is a O(1) operation which does not need to
> >>>> touch the content of the queue.
> >>>>
> >>>> RCU is used to lookup the sibling worker threads for
> >>>> work stealing and to wake the siblings of a thread
> >>>> busy handling work.
> >>>>
> >>>> It's at:
> >>>>
> >>>> git://git.urcu.so/urcu.git
> >>>> branch: urcu/workqueue-wakeup
> >>>>
> >>>> or gitweb of the top commit:
> >>>> http://git.lttng.org/?p=userspace-rcu.git;a=commit;h=2c6a5414ed2ab44be24211d15a5d9f1f40dbfc74
> >>>>
> >>>> Note that this is work in progress, compile-tested only.
> >>>> I also need to write extensive tests.
> >>>>
> >>>> Feedback is welcome,
> >>>>
> >>>> Thanks!
> >>>>
> >>>> Mathieu
> >>>>
> >>>
> >>>
> >>
> > 
> > 
> > _______________________________________________
> > lttng-dev mailing list
> > lttng-dev at lists.lttng.org
> > http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> > .
> > 
> 
> 

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com