Skip to contentSkip to conversation

Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

DISCUSSION Mathieu Desnoyers 3 participants 16 messages Oct 18, 2014 – Oct 24, 2014 14 messages not in the archive

lore
Share & tools
lore
#1 lore raw
In reply to a message not in the archive

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

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#3 lore raw
In reply to a message not in the archive

Hey,

That's pretty cool! Do you have any thoughts on the LifoSem implementation in folly? What are the differences in design decisions between your workqueue and lifosem?

One other folly abstraction you might want to look at is MPMCQueue -- this is our fifo workqueue that we combine with lifosem: https://github.com/facebook/folly/blob/master/folly/MPMCQueue.h.

One thing I'd point out about lifo waiting that really applies to rcu is the ability to quiesce threads. When we use futexes to implement data structures like LifoSem, we use an abstraction called MemoryIdler (https://github.com/facebook/folly/blob/master/folly/detail/MemoryIdler.h). When MemoryIdler calls futex() it passes a maximum timeout of 5 seconds. If it takes > 5 seconds to wake up the thread, MemoryIdler releases some of the local resources of that thread. For example, it calls madvise() to release unused portions of the thread's stack and tells jemalloc to free unused per-thread caches. Because we use lifo waiting, the oldest waiting threads tend to sleep for a long time.

For RCU, I'm guessing that because you require thread registration parts of the library iterate through all active threads. An abstraction like MemoryIdler could allow threads that sleep for a long time to unregister themselves reducing the cost of iteration.

One question I've been asking myself: is there an API the kernel could be providing us to do a better job here? One of the things that annoys me about LifoSem is that we don't need exactly LIFO behavior. All we're trying to do is avoid having threads go to sleep if they could spin a bit and acquire new work. We also want inactive threads to sleep for a long time. But among threads that have been running recently, I wish we could give the kernel more freedom in choosing. For example if the most recently run thread in the LIFO stack ran on CPU 12 but a task is currently running on CPU 12, it'd be great if the kernel could choose a different thread -- one that had recently run on a CPU where it can be immediately scheduled.

Something to think about here: most applications I've seen don't really stress the performance of this queue. The bulk of the performance win we've gotten from LifoSem has been in the application itself -- LIFO wait queues increase application performance through better cache usage. I believe this is where we'd get further wins -- eg, if the kernel could do a better job of selecting which thread to use.

-b
________________________________________
From: Mathieu Desnoyers [[email protected]]
Sent: Saturday, October 18, 2014 2:13 PM
To: Ben Maurer; lttng-dev
Cc: Yannick Brosseau; Paul E. McKenney; Lai Jiangshan; Stephen Hemminger
Subject: Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

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:
https://urldefense.proofpoint.com/v1/url?u=http://git.lttng.org/?p%3Duserspace-rcu.git%3Ba%3Dcommit%3Bh%3D2c6a5414ed2ab44be24211d15a5d9f1f40dbfc74&k=ZVNjlDMF0FElm4dQtryO4A%3D%3D%0A&r=ykFqYBj5kD4j7jlBP4F60A%3D%3D%0A&m=Lj6FdYEksb4oceU%2BtcZSfPjzIApytWcuNFbjvS2oDHc%3D%0A&s=f6323913816c4c2fae2116d0db4689082678cb921efaa7962e3bdede01907454

Note that this is work in progress, compile-tested only. I also need to write extensive tests.

Feedback is welcome,

Thanks!

Mathieu

#4 lore raw
In reply to a message not in the archive

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

Quoted 36 lines · Mathieu Desnoyers

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

#6 lore raw
In reply to a message not in the archive

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

Quoted 58 lines

From: "Lai Jiangshan" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: "Ben Maurer" <[email protected]>, "lttng-dev" <[email protected]>, "Yannick Brosseau" <[email protected]>, "Paul E. McKenney" <[email protected]>, "Stephen Hemminger" <[email protected]>
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

Quoted 36 lines · Mathieu Desnoyers

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

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#29 lore raw
In reply to a message not in the archive

----- Original Message -----

Quoted 7 lines

From: "Ben Maurer" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>, "lttng-dev" <[email protected]>
Cc: "Yannick Brosseau" <[email protected]>, "Paul E. McKenney" <[email protected]>, "Lai Jiangshan" <[email protected]>, "Stephen Hemminger" <[email protected]>
Sent: Sunday, October 19, 2014 3:15:28 PM
Subject: RE: Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

Quoted 5 lines

Hey,

That's pretty cool! Do you have any thoughts on the LifoSem implementation in folly? What are the differences in design decisions between your workqueue and lifosem?

Hi Ben,

I have to admit that I did not have time to look at thoroughly as I would have liked at the Folly implementation. So I'll focus on the design guidelines I'm aiming at for my workqueue implementation, and we'll be able to find out the comparison with folly from there. (more below)

Quoted 16 lines

One other folly abstraction you might want to look at is MPMCQueue -- this is our fifo workqueue that we combine with lifosem:
https://github.com/facebook/folly/blob/master/folly/MPMCQueue.h.

One thing I'd point out about lifo waiting that really applies to rcu is the ability to quiesce threads. When we use futexes to implement data structures like LifoSem, we use an abstraction called MemoryIdler
(https://github.com/facebook/folly/blob/master/folly/detail/MemoryIdler.h).
When MemoryIdler calls futex() it passes a maximum timeout of 5 seconds. If it takes > 5 seconds to wake up the thread, MemoryIdler releases some of the local resources of that thread. For example, it calls madvise() to release unused portions of the thread's stack and tells jemalloc to free unused per-thread caches. Because we use lifo waiting, the oldest waiting threads tend to sleep for a long time.

Quoted 4 lines

For RCU, I'm guessing that because you require thread registration parts of the library iterate through all active threads. An abstraction like MemoryIdler could allow threads that sleep for a long time to unregister themselves reducing the cost of iteration.

Yes, this could indeed speed up iteration a bit.

Quoted 12 lines

One question I've been asking myself: is there an API the kernel could be providing us to do a better job here? One of the things that annoys me about LifoSem is that we don't need exactly LIFO behavior. All we're trying to do is avoid having threads go to sleep if they could spin a bit and acquire new work. We also want inactive threads to sleep for a long time. But among threads that have been running recently, I wish we could give the kernel more freedom in choosing. For example if the most recently run thread in the LIFO stack ran on CPU 12 but a task is currently running on CPU 12, it'd be great if the kernel could choose a different thread -- one that had recently run on a CPU where it can be immediately scheduled.

Quoted 6 lines

Something to think about here: most applications I've seen don't really stress the performance of this queue. The bulk of the performance win we've gotten from LifoSem has been in the application itself -- LIFO wait queues increase application performance through better cache usage. I believe this is where we'd get further wins -- eg, if the kernel could do a better job of selecting which thread to use.

Ah-Ah! Well this is exactly one of the thing I'm trying to achieve with my workqueue/waitqueue implementation: provide exact LIFO ordering of wakeups. All done in user-space. I achieve this by having one futex int32_t per worker, and by pushing the worker structures into a stack (lfstack). Therefore, the LIFO ordering of wait (stack push) and wakeup (stack pop) is all done in userspace. Also, the waiters are responsible for busy-waiting for a while before calling futex wait, which achieve adaptative busy-wait/blocking similarly to pthread mutexes.

I try to bias speed and low latency guarantees in favor of the dispatcher (equivalent of your "network" thread). All the dispatcher has to do is to enqueue work into the workqueue (xchg + store), and then wakeup one worker thread (waitqueue stack pop (cmpxchg), check if worker is running, if not, futex wake).

Worker threads grab the entire content of the workqueue when they are looking for work to do. It minimizes the amount of cacheline bouncing that would be otherwise caused by picking work items one by one. We can do this efficiently thanks to wfcqueue splicing operation, which allow moving the entire content of a queue without locking and without touching the internal nodes of the queue.

In order to make sure we don't end up in situations where a thread would grab a lot of work, and delay its execution while other threads are waiting, I added a work-stealing scheme between neighboring threads. When a thread is busy processing a work item, it awakens one of its siblings, and the sibling is going to try to steal the entire work batch owned by the busy thread. It should allow work batches to trickle nicely amongst workers. Worker threads always do this when they wake up:
try to pick up work from the system workqueue, if no work is available, then they try to steal work from a neighbor.

Another goal I have in this design is that if the system is in a state where all workers are always busy, no calls to sys_futex() are required. All the synchronization is done in user-space.

Comments, thoughts ?

Thanks,

Mathieu

Quoted 45 lines

-b
________________________________________
From: Mathieu Desnoyers [[email protected]]
Sent: Saturday, October 18, 2014 2:13 PM
To: Ben Maurer; lttng-dev
Cc: Yannick Brosseau; Paul E. McKenney; Lai Jiangshan; Stephen Hemminger
Subject: Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

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:
https://urldefense.proofpoint.com/v1/url?u=http://git.lttng.org/?p%3Duserspace-rcu.git%3Ba%3Dcommit%3Bh%3D2c6a5414ed2ab44be24211d15a5d9f1f40dbfc74&k=ZVNjlDMF0FElm4dQtryO4A%3D%3D%0A&r=ykFqYBj5kD4j7jlBP4F60A%3D%3D%0A&m=Lj6FdYEksb4oceU%2BtcZSfPjzIApytWcuNFbjvS2oDHc%3D%0A&s=f6323913816c4c2fae2116d0db4689082678cb921efaa7962e3bdede01907454

Note that this is work in progress, compile-tested only. I also need to write extensive tests.

Feedback is welcome,

Thanks!

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#8 lore raw
In reply to a message not in the archive

Hi, Mathieu

In the code, how this problem be solved?
"All the tasks may continue stealing works without any progress."

Why ___urcu_steal_work() needs cds_wfcq_dequeue_lock()?

It is not a good idea for a worker to call synchronize_rcu() (in urcu_accept_work()). A new work may be coming soon.

thanks,
Lai

Quoted 77 lines · Mathieu Desnoyers

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

Quoted 58 lines

From: "Lai Jiangshan" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: "Ben Maurer" <[email protected]>, "lttng-dev" <[email protected]>, "Yannick Brosseau" <[email protected]>, "Paul E. McKenney" <[email protected]>, "Stephen Hemminger" <[email protected]>
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

Quoted 36 lines · Mathieu Desnoyers

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

#10 lore raw
In reply to a message not in the archive

Hi Mathieu:

what happen when the wait_node is still queued when urcu_worker_unregister() is called?

Quoted 11 lines · Lai Jiangshan

Content preview: Hi, Mathieu In the code, how this problem be solved? "All
the tasks may continue stealing works without any progress." Why ___urcu_steal_work()

    needs cds_wfcq_dequeue_lock()? [...] 

Content analysis details: (1.3 points, 5.0 required)

pts rule name description
---- ---------------------- --------------------------------------------------
1.3 RDNS_NONE Delivered to internal network by a host with no rDNS
X-Poly-FromMTA: (services.dorsal.polymtl.ca [132.207.72.61]) at Thu, 23 Oct 2014 04:24:22 +0000

Quoted 4 lines

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()?

Quoted 2 lines

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.

Quoted 3 lines

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().

Thanks,
Lai

Quoted 90 lines

thanks,
Lai

Quoted 11 lines · Mathieu Desnoyers

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

Quoted 66 lines

Please let me know if you notice anything else,

Thanks!

Mathieu

----- Original Message -----

Quoted 58 lines

From: "Lai Jiangshan" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: "Ben Maurer" <[email protected]>, "lttng-dev" <[email protected]>, "Yannick Brosseau" <[email protected]>, "Paul E. McKenney" <[email protected]>, "Stephen Hemminger" <[email protected]>
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

Quoted 36 lines · Mathieu Desnoyers

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
[email protected]
http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
.

#11 lore raw
In reply to a message not in the archive

----- Original Message -----

Quoted 8 lines

From: "Lai Jiangshan" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: "Ben Maurer" <[email protected]>, "lttng-dev" <[email protected]>, "Yannick Brosseau" <[email protected]>, "Paul E. McKenney" <[email protected]>, "Stephen Hemminger" <[email protected]>
Sent: Thursday, October 23, 2014 12:26:58 AM
Subject: Re: Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

Hi, Mathieu

Hi Lai,

Quoted 3 lines

In the code, how this problem be solved?
"All the tasks may continue stealing works without any progress."

Good point. It is not. I see two possible solutions for this:

1) We break the circular chain of siblings at the list head. It has the downside that work could accumulate at the first worker of the list, or
2) Whenever we grab work (either from the global queue or from a sibling), we could dequeue one element and keep it to ourself, out of reach of siblings. This would ensure progress, since worker stealing work would always keep one work element to itself, which would therefore ensure progress.

I personally prefer (2), since it has fewer downsides.

Quoted 2 lines

Why ___urcu_steal_work() needs cds_wfcq_dequeue_lock()?

This lock is to protect operations on the sibling workqueue. Here are the various actors touching it:

- The worker attempting to steal from the sibling (with splice-from),
- The sibling itself, in urcu_dequeue_work(), with a dequeue operation,

Looking at the wfcq synchronization table:

* Synchronization table:
*
* External synchronization techniques described in the API below is
* required between pairs marked with "X". No external synchronization
* required between pairs marked with "-".
*
* Legend:
* [1] cds_wfcq_enqueue
* [2] __cds_wfcq_splice (destination queue)
* [3] __cds_wfcq_dequeue
* [4] __cds_wfcq_splice (source queue)
* [5] __cds_wfcq_first
* [6] __cds_wfcq_next
*
* [1] [2] [3] [4] [5] [6]

 * [1]  -   -   -   -   -   -
 * [2]  -   -   -   -   -   -
 * [3]  -   -   X   X   X   X
 * [4]  -   -   X   -   X   X
 * [5]  -   -   X   X   -   -
 * [6]  -   -   X   X   -   -

We need a mutex between splice-from and dequeue since they are executed by different threads. I can replace this with a call to cds_wfcq_splice_blocking() instead, which takes the lock internally. That would be neater.

Quoted 4 lines

It is not a good idea for a worker to call synchronize_rcu() (in urcu_accept_work()).
A new work may be coming soon.

The reason why the worker calls synchronize_rcu() there is to protect the waitqueue lfstack "pop" operation from ABA. It matches the RCU read-side critical sections encompassing urcu_dequeue_wake_single().

Another way to achieve this would be to grab a mutex across calls to urcu_dequeue_wake_single(), but unfortunately this call needs to be done by the dispatcher thread, and I'm trying to keep a low-latency bias in favor of the dispatcher here. In this case, it is done at the expense of overhead in the worker when the worker is about to busy-wait and eventually block, so I thought the tradeoff was not so bad.

Thoughts ?

Thanks for the feedback!

Mathieu

Quoted 4 lines

thanks,
Lai

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#13 lore raw
In reply to a message not in the archive

----- Original Message -----

Quoted 11 lines

From: "Lai Jiangshan" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: "Paul E. McKenney" <[email protected]>, "lttng-dev" <[email protected]>, "Ben Maurer" <[email protected]>, "Yannick Brosseau" <[email protected]>
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.

Quoted 2 lines · Lai Jiangshan

[...]

Quoted 7 lines
Quoted 5 lines

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.

Quoted 6 lines
Quoted 3 lines

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,

Quoted 16 lines
Quoted 5 lines

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;
		}
	}
}
Quoted 5 lines

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

Quoted 99 lines

Thanks,
Lai

Quoted 93 lines

thanks,
Lai

Quoted 11 lines · Mathieu Desnoyers

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

Quoted 69 lines

Please let me know if you notice anything else,

Thanks!

Mathieu

----- Original Message -----

Quoted 61 lines

From: "Lai Jiangshan" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: "Ben Maurer" <[email protected]>, "lttng-dev" <[email protected]>, "Yannick Brosseau" <[email protected]>, "Paul E. McKenney" <[email protected]>, "Stephen Hemminger" <[email protected]>
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

Quoted 36 lines · Mathieu Desnoyers

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
[email protected]
http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
.

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#15 lore raw
In reply to a message not in the archive

----- Original Message -----

Quoted 75 lines

From: "Mathieu Desnoyers" <[email protected]>
To: "Lai Jiangshan" <[email protected]>
Cc: "lttng-dev" <[email protected]>, "Paul E. McKenney" <[email protected]>, "Ben Maurer" <[email protected]>, "Yannick Brosseau" <[email protected]>
Sent: Thursday, October 23, 2014 9:30:12 AM
Subject: Re: [lttng-dev] Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

----- Original Message -----

Quoted 9 lines

From: "Lai Jiangshan" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: "Paul E. McKenney" <[email protected]>, "lttng-dev" <[email protected]>, "Ben Maurer"
<[email protected]>, "Yannick Brosseau" <[email protected]>
Sent: Thursday, October 23, 2014 5:28:24 AM
Subject: Re: [lttng-dev] Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

Quoted 5 lines

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.

Quoted 2 lines · Lai Jiangshan

[...]

Quoted 8 lines
Quoted 5 lines

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.

Quoted 6 lines
Quoted 3 lines

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,

Quoted 19 lines
Quoted 5 lines

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().

Quoted 7 lines
Quoted 2 lines

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.

All the above comments should be taken care of by this string of commits:

commit a649215929e3af5a0dd26d9fc5bb9ed49e677773

Author: Mathieu Desnoyers <[email protected]>
Date:   Thu Oct 23 12:19:31 2014 -0400

workqueue: keep one work item from stealing co-workers

Takes care of lack of progress issue that could theoretically occur due to a steady work-stealing circular loop amongst co-workers. Keeping a work item hidden from co-workers ensures forward progress.

commit 6e17009c7e4276b3a90aada07e7c9835e9a788be

Author: Mathieu Desnoyers <[email protected]>
Date:   Thu Oct 23 11:27:58 2014 -0400

workqueue: ensure worker is removed from waitqueue upon unregister

commit 1b0a9891cd2f9100dc87745d77a4d0069a21adb7

Author: Mathieu Desnoyers <[email protected]>
Date:   Thu Oct 23 11:13:24 2014 -0400

workqueue: implement shutdown

commit 0695bd205e8aa88b3b032f483b7dc98c16450784

Author: Mathieu Desnoyers <[email protected]>
Date:   Thu Oct 23 09:01:29 2014 -0400

workqueue: use cds_wfcq_splice_blocking() rather than explicit locks

cds_wfcq_splice_blocking() internally takes the locks.

Please let me know if I missed anything,

Thanks!

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#17 lore raw
In reply to a message not in the archive

The next thing I'm wondering now: should we include an optional bound to the global workqueue size in the API ?

I've just had cases here where I stress test the queue with very frequent dispatch, and it can fill up memory relatively quickly if the workers have a large amount of work to do per work-item.

I think the usual way to do this would be to make the behavior nonblocking when the queue is full, so the dispatcher can take action and move the work away to another machine, or report congestion.

Thoughts ?

Thanks,

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#19 lore raw
In reply to a message not in the archive

Bounds are pretty critical :-), often during operational incidents we will get large buildups in our queues and these cause problems.

For us, one of the most critical things isn't the memory usage but the delay caused to the client. For example, if a server has a queue that incoming requests are put into if that queue grows large clients experience large delays. Since most calls to the server have a short timeout (seconds), we'd rather prevent items from entering the queue so that we fail fast.

Some of our applications switch to LIFO processing of work items when the queue is large. What this does is to focus the processing effort on recent requests -- ones which will hopefully get back to the user in time for them to see a response.

Long story short: when a queue is overloaded, we'd rather drop some requests quickly and serve the other requests with minimal queuing delay. Think of queues as bufferbloat applied to work items. In fact, we have experimented with some of the bufferbloat techniques on our work queues (specifically, CoDEL)

-b
________________________________________
From: Mathieu Desnoyers [[email protected]]
Sent: Thursday, October 23, 2014 2:57 PM
To: Lai Jiangshan
Cc: lttng-dev; Paul E. McKenney; Ben Maurer; Yannick Brosseau
Subject: Re: [lttng-dev] Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

The next thing I'm wondering now: should we include an optional bound to the global workqueue size in the API ?

I've just had cases here where I stress test the queue with very frequent dispatch, and it can fill up memory relatively quickly if the workers have a large amount of work to do per work-item.

I think the usual way to do this would be to make the behavior nonblocking when the queue is full, so the dispatcher can take action and move the work away to another machine, or report congestion.

Thoughts ?

Thanks,

Mathieu

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

#21 lore raw
In reply to a message not in the archive

Interesting point about bufferbloat!

I've just pushed the "approximate queue upper bound" feature in the last commit.

Going further, when the queue is full, there are indeed a few options:

1) sleep for a few ms and retry enqueue,
2) grab the entire content of the global workqueue, and discard its work elements one by one,
3) in addition to (2), also steal work from all worker threads, and discard their work elements.

Making the dispatcher act as a dummy "worker thread" would allow it to easily accomplish (2). We'd need some tweaks to "steal all worker's work elements" (3) (new API). This could be presented as a "urcu_queue_steal_all" or something like that, and then the dispatcher could iterate on the work items and either discard them, or perform the appropriate socket action.

Thoughts ?

Thanks,

Mathieu

----- Original Message -----

Quoted 60 lines

From: "Ben Maurer" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>, "Lai Jiangshan" <[email protected]>
Cc: "lttng-dev" <[email protected]>, "Paul E. McKenney" <[email protected]>, "Yannick Brosseau" <[email protected]>
Sent: Thursday, October 23, 2014 6:09:11 PM
Subject: RE: [lttng-dev] Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

Bounds are pretty critical :-), often during operational incidents we will get large buildups in our queues and these cause problems.

For us, one of the most critical things isn't the memory usage but the delay caused to the client. For example, if a server has a queue that incoming requests are put into if that queue grows large clients experience large delays. Since most calls to the server have a short timeout (seconds), we'd rather prevent items from entering the queue so that we fail fast.

Some of our applications switch to LIFO processing of work items when the queue is large. What this does is to focus the processing effort on recent requests -- ones which will hopefully get back to the user in time for them to see a response.

Long story short: when a queue is overloaded, we'd rather drop some requests quickly and serve the other requests with minimal queuing delay. Think of queues as bufferbloat applied to work items. In fact, we have experimented with some of the bufferbloat techniques on our work queues (specifically, CoDEL)

-b
________________________________________
From: Mathieu Desnoyers [[email protected]]
Sent: Thursday, October 23, 2014 2:57 PM
To: Lai Jiangshan
Cc: lttng-dev; Paul E. McKenney; Ben Maurer; Yannick Brosseau
Subject: Re: [lttng-dev] Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

The next thing I'm wondering now: should we include an optional bound to the global workqueue size in the API ?

I've just had cases here where I stress test the queue with very frequent dispatch, and it can fill up memory relatively quickly if the workers have a large amount of work to do per work-item.

I think the usual way to do this would be to make the behavior nonblocking when the queue is full, so the dispatcher can take action and move the work away to another machine, or report congestion.

Thoughts ?

Thanks,

Mathieu

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

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#23 lore raw
In reply to a message not in the archive

I just implemented a urcu_workqueue_steal_all(), and the benchmark test program now uses this when there is congestion in the queue.

Thanks,

Mathieu

----- Original Message -----

Quoted 113 lines

From: "Mathieu Desnoyers" <[email protected]>
To: "Ben Maurer" <[email protected]>
Cc: "Yannick Brosseau" <[email protected]>, "lttng-dev" <[email protected]>, "Paul E. McKenney" <[email protected]>
Sent: Thursday, October 23, 2014 6:48:52 PM
Subject: Re: [lttng-dev] Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

Interesting point about bufferbloat!

I've just pushed the "approximate queue upper bound" feature in the last commit.

Going further, when the queue is full, there are indeed a few options:

1) sleep for a few ms and retry enqueue,
2) grab the entire content of the global workqueue, and discard its work elements one by one,
3) in addition to (2), also steal work from all worker threads, and discard their work elements.

Making the dispatcher act as a dummy "worker thread" would allow it to easily accomplish (2). We'd need some tweaks to "steal all worker's work elements" (3) (new API). This could be presented as a "urcu_queue_steal_all" or something like that, and then the dispatcher could iterate on the work items and either discard them, or perform the appropriate socket action.

Thoughts ?

Thanks,

Mathieu

----- Original Message -----

Quoted 56 lines

From: "Ben Maurer" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>, "Lai Jiangshan" <[email protected]>
Cc: "lttng-dev" <[email protected]>, "Paul E. McKenney" <[email protected]>, "Yannick Brosseau" <[email protected]>
Sent: Thursday, October 23, 2014 6:09:11 PM
Subject: RE: [lttng-dev] Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

Bounds are pretty critical :-), often during operational incidents we will get large buildups in our queues and these cause problems.

For us, one of the most critical things isn't the memory usage but the delay
caused to the client. For example, if a server has a queue that incoming requests are put into if that queue grows large clients experience large delays. Since most calls to the server have a short timeout (seconds), we'd rather prevent items from entering the queue so that we fail fast.

Some of our applications switch to LIFO processing of work items when the queue is large. What this does is to focus the processing effort on recent requests -- ones which will hopefully get back to the user in time for them to see a response.

Long story short: when a queue is overloaded, we'd rather drop some requests
quickly and serve the other requests with minimal queuing delay. Think of queues as bufferbloat applied to work items. In fact, we have experimented with some of the bufferbloat techniques on our work queues (specifically, CoDEL)

-b
________________________________________
From: Mathieu Desnoyers [[email protected]]
Sent: Thursday, October 23, 2014 2:57 PM
To: Lai Jiangshan
Cc: lttng-dev; Paul E. McKenney; Ben Maurer; Yannick Brosseau
Subject: Re: [lttng-dev] Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

The next thing I'm wondering now: should we include an optional bound to the global workqueue size in the API ?

I've just had cases here where I stress test the queue with very frequent dispatch, and it can fill up memory relatively quickly if the workers have a large amount of work to do per work-item.

I think the usual way to do this would be to make the behavior nonblocking when the queue is full, so the dispatcher can take action and move the work away to another machine, or report congestion.

Thoughts ?

Quoted 9 lines

Thanks,

Mathieu

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

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

_______________________________________________
lttng-dev mailing list
[email protected]
http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#25 lore raw
In reply to a message not in the archive
Quoted 77 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 8 lines

From: "Lai Jiangshan" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: "Ben Maurer" <[email protected]>, "lttng-dev" <[email protected]>, "Yannick Brosseau" <[email protected]>, "Paul E. McKenney" <[email protected]>, "Stephen Hemminger" <[email protected]>
Sent: Thursday, October 23, 2014 12:26:58 AM
Subject: Re: Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

Hi, Mathieu

Hi Lai,

Quoted 3 lines

In the code, how this problem be solved?
"All the tasks may continue stealing works without any progress."

Good point. It is not. I see two possible solutions for this:

1) We break the circular chain of siblings at the list head. It has the downside that work could accumulate at the first worker of the list, or
2) Whenever we grab work (either from the global queue or from a sibling), we could dequeue one element and keep it to ourself, out of reach of siblings. This would ensure progress, since worker stealing work would always keep one work element to itself, which would therefore ensure progress.

I personally prefer (2), since it has fewer downsides.

Quoted 2 lines

Why ___urcu_steal_work() needs cds_wfcq_dequeue_lock()?

This lock is to protect operations on the sibling workqueue. Here are the various actors touching it:

- The worker attempting to steal from the sibling (with splice-from),
- The sibling itself, in urcu_dequeue_work(), with a dequeue operation,

Looking at the wfcq synchronization table:

* Synchronization table:
*
* External synchronization techniques described in the API below is
* required between pairs marked with "X". No external synchronization
* required between pairs marked with "-".
*
* Legend:
* [1] cds_wfcq_enqueue
* [2] __cds_wfcq_splice (destination queue)
* [3] __cds_wfcq_dequeue
* [4] __cds_wfcq_splice (source queue)
* [5] __cds_wfcq_first
* [6] __cds_wfcq_next
*
* [1] [2] [3] [4] [5] [6]

 * [1]  -   -   -   -   -   -
 * [2]  -   -   -   -   -   -
 * [3]  -   -   X   X   X   X
 * [4]  -   -   X   -   X   X
 * [5]  -   -   X   X   -   -
 * [6]  -   -   X   X   -   -

We need a mutex between splice-from and dequeue since they are executed by different threads. I can replace this with a call to cds_wfcq_splice_blocking() instead, which takes the lock internally. That would be neater.

Quoted 4 lines

It is not a good idea for a worker to call synchronize_rcu() (in urcu_accept_work()).
A new work may be coming soon.

The reason why the worker calls synchronize_rcu() there is to protect the waitqueue lfstack "pop" operation from ABA. It matches the RCU read-side critical sections encompassing urcu_dequeue_wake_single().

Quoted 6 lines

Another way to achieve this would be to grab a mutex across calls to urcu_dequeue_wake_single(), but unfortunately this call needs to be done by the dispatcher thread, and I'm trying to keep a low-latency bias in favor of the dispatcher here. In this case, it is done at the expense of overhead in the worker when the worker is about to busy-wait and eventually block, so I thought the tradeoff was not so bad.

"single worker pattern" does be a frequent use-case. you can image the lag and jitter in this case.

How about a mutex&rcu protected idle-workers?

idle-worker is wokenup via rcu-protected scheme.
and dequeued&requeued (in urcu_accept_work() or urcu_worker_unregister()) via mutex-protected scheme.

Quoted 12 lines

Thoughts ?

Thanks for the feedback!

Mathieu

Quoted 4 lines

thanks,
Lai

#27 lore raw
In reply to a message not in the archive

----- Original Message -----

Quoted 19 lines

From: "Lai Jiangshan" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: "Ben Maurer" <[email protected]>, "lttng-dev" <[email protected]>, "Yannick Brosseau" <[email protected]>, "Paul E. McKenney" <[email protected]>, "Stephen Hemminger" <[email protected]>
Sent: Thursday, October 23, 2014 9:45:59 PM
Subject: Re: Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

Quoted 11 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 9 lines

From: "Lai Jiangshan" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: "Ben Maurer" <[email protected]>, "lttng-dev" <[email protected]>, "Yannick Brosseau" <[email protected]>, "Paul E. McKenney" <[email protected]>, "Stephen Hemminger" <[email protected]>
Sent: Thursday, October 23, 2014 12:26:58 AM
Subject: Re: Userspace RCU: workqueue with batching, cheap wakeup, and work stealing

[...]

Quoted 16 lines
Quoted 9 lines
Quoted 4 lines

It is not a good idea for a worker to call synchronize_rcu() (in urcu_accept_work()).
A new work may be coming soon.

The reason why the worker calls synchronize_rcu() there is to protect the waitqueue lfstack "pop" operation from ABA. It matches the RCU read-side critical sections encompassing urcu_dequeue_wake_single().

Quoted 6 lines

Another way to achieve this would be to grab a mutex across calls to urcu_dequeue_wake_single(), but unfortunately this call needs to be done by the dispatcher thread, and I'm trying to keep a low-latency bias in favor of the dispatcher here. In this case, it is done at the expense of overhead in the worker when the worker is about to busy-wait and eventually block, so I thought the tradeoff was not so bad.

Quoted 2 lines

"single worker pattern" does be a frequent use-case. you can image the lag and jitter in this case.

I'd be happy to find a way to reduce unnecessary jitter, indeed. However, we need to keep in mind that this is issued only when the worker thread has no more work to do. And if there are few registered RCU threads, synchronize_rcu() should be pretty quick, especially now that multiple grace periods can run concurrently.

Quoted 7 lines

How about a mutex&rcu protected idle-workers?

idle-worker is wokenup via rcu-protected scheme.
and dequeued&requeued (in urcu_accept_work() or urcu_worker_unregister()) via mutex-protected scheme.

I'm not sure I understand your proposal. Can you give more detail about the RCU protected scheme you refer to here, along with how it is intended to interact with mutex ?

Note that if we use RCU read-side around lfstack pop, it needs to be matched by a grace period between all other "pop"/"pop all" and re-push to deal with ABA.

Thanks,

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com