real time Userspace RCU

real time Userspace RCU

[Yuxin Ren]

Hi,

 Is there any work or research about Userspace RCU on real time or
embedded systems?
Any information is welcome.

Thanks a lot!
Yuxin
_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: real time Userspace RCU

[Michel Dagenais]

Real-time and embedded systems is an important current focus for the LTTng toolchain research. Do you have specific needs for userspace RCU?

----- Mail original -----
> Hi,
> 
>  Is there any work or research about Userspace RCU on real time or
> embedded systems?
> Any information is welcome.
> 
> Thanks a lot!
> Yuxin
> _______________________________________________
> lttng-dev mailing list
> lttng-dev@lists.lttng.org
> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> 
_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: real time Userspace RCU

[Yuxin Ren]

Thank you for your reply.

I want to generally understand how to apply urcu to real time systems.
I know real time system focus on predictability on both timing and
memory consumption.
So how does real time urcu support predictability?
Could you provide me some papers, documents or any materials about any
aspect of real time urcu?

Thanks again!

On Thu, Mar 10, 2016 at 1:52 PM, Michel Dagenais
<michel.dagenais@polymtl.ca> wrote:
> Real-time and embedded systems is an important current focus for the LTTng toolchain research. Do you have specific needs for userspace RCU?
>
> ----- Mail original -----
>> Hi,
>>
>>  Is there any work or research about Userspace RCU on real time or
>> embedded systems?
>> Any information is welcome.
>>
>> Thanks a lot!
>> Yuxin
>> _______________________________________________
>> lttng-dev mailing list
>> lttng-dev@lists.lttng.org
>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
>>
_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: real time Userspace RCU

[Mathieu Desnoyers]

----- On Mar 10, 2016, at 3:33 PM, Yuxin Ren ryx@gwmail.gwu.edu wrote:

> Thank you for your reply.
> 
> I want to generally understand how to apply urcu to real time systems.
> I know real time system focus on predictability on both timing and
> memory consumption.
> So how does real time urcu support predictability?
> Could you provide me some papers, documents or any materials about any
> aspect of real time urcu?

Adding Paul E. McKenney in CC, who may have some thoughts on this
topic.

Thanks,

Mathieu

> 
> Thanks again!
> 
> On Thu, Mar 10, 2016 at 1:52 PM, Michel Dagenais
> <michel.dagenais@polymtl.ca> wrote:
>> Real-time and embedded systems is an important current focus for the LTTng
>> toolchain research. Do you have specific needs for userspace RCU?
>>
>> ----- Mail original -----
>>> Hi,
>>>
>>>  Is there any work or research about Userspace RCU on real time or
>>> embedded systems?
>>> Any information is welcome.
>>>
>>> Thanks a lot!
>>> Yuxin
>>> _______________________________________________
>>> lttng-dev mailing list
>>> lttng-dev@lists.lttng.org
>>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
>>>
> _______________________________________________
> lttng-dev mailing list
> lttng-dev@lists.lttng.org
> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: real time Userspace RCU

[Paul E. McKenney]

On Thu, Mar 10, 2016 at 08:53:05PM +0000, Mathieu Desnoyers wrote:
> ----- On Mar 10, 2016, at 3:33 PM, Yuxin Ren ryx@gwmail.gwu.edu wrote:
> 
> > Thank you for your reply.
> > 
> > I want to generally understand how to apply urcu to real time systems.
> > I know real time system focus on predictability on both timing and
> > memory consumption.
> > So how does real time urcu support predictability?
> > Could you provide me some papers, documents or any materials about any
> > aspect of real time urcu?
> 
> Adding Paul E. McKenney in CC, who may have some thoughts on this
> topic.

URCU does timing quite well, given that the read-side primitives each
execute a fixed sequence of instructions.  Updates using call_rcu()
can be used to minimize update-side latency, but if you need to bound
memory overhead, the best way to do that is to make sure that updates
are not on the critical path, and then use synchronize_rcu() instead
of call_rcu().  In that case, the total amount of memory waiting for
reclamation is bounded by the maximum size of an RCU-protected memory
block times the number of threads.

So can you design your application so that updates are off the critical
path?  If so, you can get both bounded read-side accesses and bounded
memory footprint.

This of course assumes that your data structures are simple enough
that readers don't need to use retry techniques.

The following info might be helpful:

http://www2.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf
http://www2.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.09.29a.pdf

http://www2.rdrop.com/users/paulmck/realtime/paper/RTLWS2012occcRT.2012.10.19e.pdf

It also depends on your timeframe.  Microseconds?  Life is hard.
Milliseconds?  Care is required, but you have a fair amount of freedom.
Seconds?  Life is not so hard.  Unless you need to do two seconds of
computation in one second or some such.  ;-)

							Thanx, Paul

> Thanks,
> 
> Mathieu
> 
> > 
> > Thanks again!
> > 
> > On Thu, Mar 10, 2016 at 1:52 PM, Michel Dagenais
> > <michel.dagenais@polymtl.ca> wrote:
> >> Real-time and embedded systems is an important current focus for the LTTng
> >> toolchain research. Do you have specific needs for userspace RCU?
> >>
> >> ----- Mail original -----
> >>> Hi,
> >>>
> >>>  Is there any work or research about Userspace RCU on real time or
> >>> embedded systems?
> >>> Any information is welcome.
> >>>
> >>> Thanks a lot!
> >>> Yuxin
> >>> _______________________________________________
> >>> lttng-dev mailing list
> >>> lttng-dev@lists.lttng.org
> >>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> >>>
> > _______________________________________________
> > lttng-dev mailing list
> > lttng-dev@lists.lttng.org
> > https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> 
> -- 
> Mathieu Desnoyers
> EfficiOS Inc.
> http://www.efficios.com
> 

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: real time Userspace RCU

[Michel Dagenais]

Indeed, all the relevant articles that I know on that topic were written by Paul. If your real-time tasks are on the read side of RCU, they should not block because of that. However, reclaiming the memory and the associated machinery that sometimes involves inter-processor interrupts may cause problems if you have "deep sub-milisecond" deadlines.

----- Mail original -----
> ----- On Mar 10, 2016, at 3:33 PM, Yuxin Ren ryx@gwmail.gwu.edu wrote:
> 
> > Thank you for your reply.
> > 
> > I want to generally understand how to apply urcu to real time systems.
> > I know real time system focus on predictability on both timing and
> > memory consumption.
> > So how does real time urcu support predictability?
> > Could you provide me some papers, documents or any materials about any
> > aspect of real time urcu?
> 
> Adding Paul E. McKenney in CC, who may have some thoughts on this
> topic.
> 
> Thanks,
> 
> Mathieu
> 
> > 
> > Thanks again!
> > 
> > On Thu, Mar 10, 2016 at 1:52 PM, Michel Dagenais
> > <michel.dagenais@polymtl.ca> wrote:
> >> Real-time and embedded systems is an important current focus for the LTTng
> >> toolchain research. Do you have specific needs for userspace RCU?
> >>
> >> ----- Mail original -----
> >>> Hi,
> >>>
> >>>  Is there any work or research about Userspace RCU on real time or
> >>> embedded systems?
> >>> Any information is welcome.
> >>>
> >>> Thanks a lot!
> >>> Yuxin
> >>> _______________________________________________
> >>> lttng-dev mailing list
> >>> lttng-dev@lists.lttng.org
> >>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> >>>
> > _______________________________________________
> > lttng-dev mailing list
> > lttng-dev@lists.lttng.org
> > https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> 
> --
> Mathieu Desnoyers
> EfficiOS Inc.
> http://www.efficios.com
> 
_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: real time Userspace RCU

[Mathieu Desnoyers]

----- On Mar 11, 2016, at 6:45 AM, Paul E. McKenney paulmck@linux.vnet.ibm.com wrote:

> On Thu, Mar 10, 2016 at 08:53:05PM +0000, Mathieu Desnoyers wrote:
>> ----- On Mar 10, 2016, at 3:33 PM, Yuxin Ren ryx@gwmail.gwu.edu wrote:
>> 
>> > Thank you for your reply.
>> > 
>> > I want to generally understand how to apply urcu to real time systems.
>> > I know real time system focus on predictability on both timing and
>> > memory consumption.
>> > So how does real time urcu support predictability?
>> > Could you provide me some papers, documents or any materials about any
>> > aspect of real time urcu?
>> 
>> Adding Paul E. McKenney in CC, who may have some thoughts on this
>> topic.
> 
> URCU does timing quite well, given that the read-side primitives each
> execute a fixed sequence of instructions.  Updates using call_rcu()
> can be used to minimize update-side latency, but if you need to bound
> memory overhead, the best way to do that is to make sure that updates
> are not on the critical path, and then use synchronize_rcu() instead
> of call_rcu().  In that case, the total amount of memory waiting for
> reclamation is bounded by the maximum size of an RCU-protected memory
> block times the number of threads.

An intermediate solution if both update throughput and bounded-memory
are required (but the application would not have real-time constraints
on updates) would be to use the defer_rcu() API in liburcu. It amortizes
the cost of synchronize_rcu() over many defer_rcu() calls with a worker
thread, but only up to an upper bound. When the upper bound is reached,
the defer queue call empties the defer queue itself.

Thanks,

Mathieu

> 
> So can you design your application so that updates are off the critical
> path?  If so, you can get both bounded read-side accesses and bounded
> memory footprint.
> 
> This of course assumes that your data structures are simple enough
> that readers don't need to use retry techniques.
> 
> The following info might be helpful:
> 
> http://www2.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf
> http://www2.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.09.29a.pdf
> 
> http://www2.rdrop.com/users/paulmck/realtime/paper/RTLWS2012occcRT.2012.10.19e.pdf
> 
> It also depends on your timeframe.  Microseconds?  Life is hard.
> Milliseconds?  Care is required, but you have a fair amount of freedom.
> Seconds?  Life is not so hard.  Unless you need to do two seconds of
> computation in one second or some such.  ;-)
> 
>							Thanx, Paul
> 
>> Thanks,
>> 
>> Mathieu
>> 
>> > 
>> > Thanks again!
>> > 
>> > On Thu, Mar 10, 2016 at 1:52 PM, Michel Dagenais
>> > <michel.dagenais@polymtl.ca> wrote:
>> >> Real-time and embedded systems is an important current focus for the LTTng
>> >> toolchain research. Do you have specific needs for userspace RCU?
>> >>
>> >> ----- Mail original -----
>> >>> Hi,
>> >>>
>> >>>  Is there any work or research about Userspace RCU on real time or
>> >>> embedded systems?
>> >>> Any information is welcome.
>> >>>
>> >>> Thanks a lot!
>> >>> Yuxin
>> >>> _______________________________________________
>> >>> lttng-dev mailing list
>> >>> lttng-dev@lists.lttng.org
>> >>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
>> >>>
>> > _______________________________________________
>> > lttng-dev mailing list
>> > lttng-dev@lists.lttng.org
>> > https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
>> 
>> --
>> Mathieu Desnoyers
>> EfficiOS Inc.
>> http://www.efficios.com

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: real time Userspace RCU

[Yuxin Ren]

Thank you all!!

I agree URCU does timing quite well.
But are there any formal response time analysis for URCU/RCU (both
read  and update path)?
Or could anyone guide me how to do RTA for URCU/RCU?

Thanks again.

On Fri, Mar 11, 2016 at 10:00 PM, Mathieu Desnoyers
<mathieu.desnoyers@efficios.com> wrote:
> ----- On Mar 11, 2016, at 6:45 AM, Paul E. McKenney paulmck@linux.vnet.ibm.com wrote:
>
>> On Thu, Mar 10, 2016 at 08:53:05PM +0000, Mathieu Desnoyers wrote:
>>> ----- On Mar 10, 2016, at 3:33 PM, Yuxin Ren ryx@gwmail.gwu.edu wrote:
>>>
>>> > Thank you for your reply.
>>> >
>>> > I want to generally understand how to apply urcu to real time systems.
>>> > I know real time system focus on predictability on both timing and
>>> > memory consumption.
>>> > So how does real time urcu support predictability?
>>> > Could you provide me some papers, documents or any materials about any
>>> > aspect of real time urcu?
>>>
>>> Adding Paul E. McKenney in CC, who may have some thoughts on this
>>> topic.
>>
>> URCU does timing quite well, given that the read-side primitives each
>> execute a fixed sequence of instructions.  Updates using call_rcu()
>> can be used to minimize update-side latency, but if you need to bound
>> memory overhead, the best way to do that is to make sure that updates
>> are not on the critical path, and then use synchronize_rcu() instead
>> of call_rcu().  In that case, the total amount of memory waiting for
>> reclamation is bounded by the maximum size of an RCU-protected memory
>> block times the number of threads.
>
> An intermediate solution if both update throughput and bounded-memory
> are required (but the application would not have real-time constraints
> on updates) would be to use the defer_rcu() API in liburcu. It amortizes
> the cost of synchronize_rcu() over many defer_rcu() calls with a worker
> thread, but only up to an upper bound. When the upper bound is reached,
> the defer queue call empties the defer queue itself.
>
> Thanks,
>
> Mathieu
>
>>
>> So can you design your application so that updates are off the critical
>> path?  If so, you can get both bounded read-side accesses and bounded
>> memory footprint.
>>
>> This of course assumes that your data structures are simple enough
>> that readers don't need to use retry techniques.
>>
>> The following info might be helpful:
>>
>> http://www2.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf
>> http://www2.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.09.29a.pdf
>>
>> http://www2.rdrop.com/users/paulmck/realtime/paper/RTLWS2012occcRT.2012.10.19e.pdf
>>
>> It also depends on your timeframe.  Microseconds?  Life is hard.
>> Milliseconds?  Care is required, but you have a fair amount of freedom.
>> Seconds?  Life is not so hard.  Unless you need to do two seconds of
>> computation in one second or some such.  ;-)
>>
>>                                                       Thanx, Paul
>>
>>> Thanks,
>>>
>>> Mathieu
>>>
>>> >
>>> > Thanks again!
>>> >
>>> > On Thu, Mar 10, 2016 at 1:52 PM, Michel Dagenais
>>> > <michel.dagenais@polymtl.ca> wrote:
>>> >> Real-time and embedded systems is an important current focus for the LTTng
>>> >> toolchain research. Do you have specific needs for userspace RCU?
>>> >>
>>> >> ----- Mail original -----
>>> >>> Hi,
>>> >>>
>>> >>>  Is there any work or research about Userspace RCU on real time or
>>> >>> embedded systems?
>>> >>> Any information is welcome.
>>> >>>
>>> >>> Thanks a lot!
>>> >>> Yuxin
>>> >>> _______________________________________________
>>> >>> lttng-dev mailing list
>>> >>> lttng-dev@lists.lttng.org
>>> >>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
>>> >>>
>>> > _______________________________________________
>>> > lttng-dev mailing list
>>> > lttng-dev@lists.lttng.org
>>> > https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
>>>
>>> --
>>> Mathieu Desnoyers
>>> EfficiOS Inc.
>>> http://www.efficios.com
>
> --
> Mathieu Desnoyers
> EfficiOS Inc.
> http://www.efficios.com
_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: real time Userspace RCU

[Paul E. McKenney]

On Thu, Mar 31, 2016 at 09:20:07AM +0800, Yuxin Ren wrote:
> Thank you all!!
> 
> I agree URCU does timing quite well.
> But are there any formal response time analysis for URCU/RCU (both
> read  and update path)?

Not that I know of.  You could be the first!

> Or could anyone guide me how to do RTA for URCU/RCU?

Compile something with a simple RCU read-side critical section, and then
count the instructions.  QSBR will of course work best, but MB will also
have good bounds.  Signal-based will be a bit more complicated.

Much depends on what type of RTA you want to do.  Brandenburg's
dissertation has quite a bit of info and many citations:

	http://www.cs.unc.edu/~bbb/diss/

You can also take an experimental approach, though a great many
runs are required.  OSADL (https://www.osadl.org/) does quite a
bit of this work on -rt Linux.

							Thanx, Paul

> Thanks again.
> 
> On Fri, Mar 11, 2016 at 10:00 PM, Mathieu Desnoyers
> <mathieu.desnoyers@efficios.com> wrote:
> > ----- On Mar 11, 2016, at 6:45 AM, Paul E. McKenney paulmck@linux.vnet.ibm.com wrote:
> >
> >> On Thu, Mar 10, 2016 at 08:53:05PM +0000, Mathieu Desnoyers wrote:
> >>> ----- On Mar 10, 2016, at 3:33 PM, Yuxin Ren ryx@gwmail.gwu.edu wrote:
> >>>
> >>> > Thank you for your reply.
> >>> >
> >>> > I want to generally understand how to apply urcu to real time systems.
> >>> > I know real time system focus on predictability on both timing and
> >>> > memory consumption.
> >>> > So how does real time urcu support predictability?
> >>> > Could you provide me some papers, documents or any materials about any
> >>> > aspect of real time urcu?
> >>>
> >>> Adding Paul E. McKenney in CC, who may have some thoughts on this
> >>> topic.
> >>
> >> URCU does timing quite well, given that the read-side primitives each
> >> execute a fixed sequence of instructions.  Updates using call_rcu()
> >> can be used to minimize update-side latency, but if you need to bound
> >> memory overhead, the best way to do that is to make sure that updates
> >> are not on the critical path, and then use synchronize_rcu() instead
> >> of call_rcu().  In that case, the total amount of memory waiting for
> >> reclamation is bounded by the maximum size of an RCU-protected memory
> >> block times the number of threads.
> >
> > An intermediate solution if both update throughput and bounded-memory
> > are required (but the application would not have real-time constraints
> > on updates) would be to use the defer_rcu() API in liburcu. It amortizes
> > the cost of synchronize_rcu() over many defer_rcu() calls with a worker
> > thread, but only up to an upper bound. When the upper bound is reached,
> > the defer queue call empties the defer queue itself.
> >
> > Thanks,
> >
> > Mathieu
> >
> >>
> >> So can you design your application so that updates are off the critical
> >> path?  If so, you can get both bounded read-side accesses and bounded
> >> memory footprint.
> >>
> >> This of course assumes that your data structures are simple enough
> >> that readers don't need to use retry techniques.
> >>
> >> The following info might be helpful:
> >>
> >> http://www2.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf
> >> http://www2.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.09.29a.pdf
> >>
> >> http://www2.rdrop.com/users/paulmck/realtime/paper/RTLWS2012occcRT.2012.10.19e.pdf
> >>
> >> It also depends on your timeframe.  Microseconds?  Life is hard.
> >> Milliseconds?  Care is required, but you have a fair amount of freedom.
> >> Seconds?  Life is not so hard.  Unless you need to do two seconds of
> >> computation in one second or some such.  ;-)
> >>
> >>                                                       Thanx, Paul
> >>
> >>> Thanks,
> >>>
> >>> Mathieu
> >>>
> >>> >
> >>> > Thanks again!
> >>> >
> >>> > On Thu, Mar 10, 2016 at 1:52 PM, Michel Dagenais
> >>> > <michel.dagenais@polymtl.ca> wrote:
> >>> >> Real-time and embedded systems is an important current focus for the LTTng
> >>> >> toolchain research. Do you have specific needs for userspace RCU?
> >>> >>
> >>> >> ----- Mail original -----
> >>> >>> Hi,
> >>> >>>
> >>> >>>  Is there any work or research about Userspace RCU on real time or
> >>> >>> embedded systems?
> >>> >>> Any information is welcome.
> >>> >>>
> >>> >>> Thanks a lot!
> >>> >>> Yuxin
> >>> >>> _______________________________________________
> >>> >>> lttng-dev mailing list
> >>> >>> lttng-dev@lists.lttng.org
> >>> >>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> >>> >>>
> >>> > _______________________________________________
> >>> > lttng-dev mailing list
> >>> > lttng-dev@lists.lttng.org
> >>> > https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> >>>
> >>> --
> >>> Mathieu Desnoyers
> >>> EfficiOS Inc.
> >>> http://www.efficios.com
> >
> > --
> > Mathieu Desnoyers
> > EfficiOS Inc.
> > http://www.efficios.com
> 

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: real time Userspace RCU

[Yuxin Ren]

I really appreciate your reply!!

I have one more question.
From real time aspect, preemption of URCU read-side critical sections
can cause priority-inversion issue.
Does current URCU implementation deal with this problem?
And if so, how does it solve this?

Thanks
Yuxin

On Thu, Mar 31, 2016 at 7:22 AM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
> On Thu, Mar 31, 2016 at 09:20:07AM +0800, Yuxin Ren wrote:
>> Thank you all!!
>>
>> I agree URCU does timing quite well.
>> But are there any formal response time analysis for URCU/RCU (both
>> read  and update path)?
>
> Not that I know of.  You could be the first!
>
>> Or could anyone guide me how to do RTA for URCU/RCU?
>
> Compile something with a simple RCU read-side critical section, and then
> count the instructions.  QSBR will of course work best, but MB will also
> have good bounds.  Signal-based will be a bit more complicated.
>
> Much depends on what type of RTA you want to do.  Brandenburg's
> dissertation has quite a bit of info and many citations:
>
>         http://www.cs.unc.edu/~bbb/diss/
>
> You can also take an experimental approach, though a great many
> runs are required.  OSADL (https://www.osadl.org/) does quite a
> bit of this work on -rt Linux.
>
>                                                         Thanx, Paul
>
>> Thanks again.
>>
>> On Fri, Mar 11, 2016 at 10:00 PM, Mathieu Desnoyers
>> <mathieu.desnoyers@efficios.com> wrote:
>> > ----- On Mar 11, 2016, at 6:45 AM, Paul E. McKenney paulmck@linux.vnet.ibm.com wrote:
>> >
>> >> On Thu, Mar 10, 2016 at 08:53:05PM +0000, Mathieu Desnoyers wrote:
>> >>> ----- On Mar 10, 2016, at 3:33 PM, Yuxin Ren ryx@gwmail.gwu.edu wrote:
>> >>>
>> >>> > Thank you for your reply.
>> >>> >
>> >>> > I want to generally understand how to apply urcu to real time systems.
>> >>> > I know real time system focus on predictability on both timing and
>> >>> > memory consumption.
>> >>> > So how does real time urcu support predictability?
>> >>> > Could you provide me some papers, documents or any materials about any
>> >>> > aspect of real time urcu?
>> >>>
>> >>> Adding Paul E. McKenney in CC, who may have some thoughts on this
>> >>> topic.
>> >>
>> >> URCU does timing quite well, given that the read-side primitives each
>> >> execute a fixed sequence of instructions.  Updates using call_rcu()
>> >> can be used to minimize update-side latency, but if you need to bound
>> >> memory overhead, the best way to do that is to make sure that updates
>> >> are not on the critical path, and then use synchronize_rcu() instead
>> >> of call_rcu().  In that case, the total amount of memory waiting for
>> >> reclamation is bounded by the maximum size of an RCU-protected memory
>> >> block times the number of threads.
>> >
>> > An intermediate solution if both update throughput and bounded-memory
>> > are required (but the application would not have real-time constraints
>> > on updates) would be to use the defer_rcu() API in liburcu. It amortizes
>> > the cost of synchronize_rcu() over many defer_rcu() calls with a worker
>> > thread, but only up to an upper bound. When the upper bound is reached,
>> > the defer queue call empties the defer queue itself.
>> >
>> > Thanks,
>> >
>> > Mathieu
>> >
>> >>
>> >> So can you design your application so that updates are off the critical
>> >> path?  If so, you can get both bounded read-side accesses and bounded
>> >> memory footprint.
>> >>
>> >> This of course assumes that your data structures are simple enough
>> >> that readers don't need to use retry techniques.
>> >>
>> >> The following info might be helpful:
>> >>
>> >> http://www2.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf
>> >> http://www2.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.09.29a.pdf
>> >>
>> >> http://www2.rdrop.com/users/paulmck/realtime/paper/RTLWS2012occcRT.2012.10.19e.pdf
>> >>
>> >> It also depends on your timeframe.  Microseconds?  Life is hard.
>> >> Milliseconds?  Care is required, but you have a fair amount of freedom.
>> >> Seconds?  Life is not so hard.  Unless you need to do two seconds of
>> >> computation in one second or some such.  ;-)
>> >>
>> >>                                                       Thanx, Paul
>> >>
>> >>> Thanks,
>> >>>
>> >>> Mathieu
>> >>>
>> >>> >
>> >>> > Thanks again!
>> >>> >
>> >>> > On Thu, Mar 10, 2016 at 1:52 PM, Michel Dagenais
>> >>> > <michel.dagenais@polymtl.ca> wrote:
>> >>> >> Real-time and embedded systems is an important current focus for the LTTng
>> >>> >> toolchain research. Do you have specific needs for userspace RCU?
>> >>> >>
>> >>> >> ----- Mail original -----
>> >>> >>> Hi,
>> >>> >>>
>> >>> >>>  Is there any work or research about Userspace RCU on real time or
>> >>> >>> embedded systems?
>> >>> >>> Any information is welcome.
>> >>> >>>
>> >>> >>> Thanks a lot!
>> >>> >>> Yuxin
>> >>> >>> _______________________________________________
>> >>> >>> lttng-dev mailing list
>> >>> >>> lttng-dev@lists.lttng.org
>> >>> >>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
>> >>> >>>
>> >>> > _______________________________________________
>> >>> > lttng-dev mailing list
>> >>> > lttng-dev@lists.lttng.org
>> >>> > https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
>> >>>
>> >>> --
>> >>> Mathieu Desnoyers
>> >>> EfficiOS Inc.
>> >>> http://www.efficios.com
>> >
>> > --
>> > Mathieu Desnoyers
>> > EfficiOS Inc.
>> > http://www.efficios.com
>>
>
_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: real time Userspace RCU

[Paul E. McKenney]

Hello, Yuxin,

Currently, userspace RCU does not prevent this sort of priority-inversion
issue.

We have not yet had complaints about it, but did you have any thoughts for
a good implementation tht would avoid this sort of priority inversion?

							Thanx, Paul

On Fri, Apr 15, 2016 at 11:46:48AM -0400, Yuxin Ren wrote:
> I really appreciate your reply!!
> 
> I have one more question.
> >From real time aspect, preemption of URCU read-side critical sections
> can cause priority-inversion issue.
> Does current URCU implementation deal with this problem?
> And if so, how does it solve this?
> 
> Thanks
> Yuxin
> 
> On Thu, Mar 31, 2016 at 7:22 AM, Paul E. McKenney
> <paulmck@linux.vnet.ibm.com> wrote:
> > On Thu, Mar 31, 2016 at 09:20:07AM +0800, Yuxin Ren wrote:
> >> Thank you all!!
> >>
> >> I agree URCU does timing quite well.
> >> But are there any formal response time analysis for URCU/RCU (both
> >> read  and update path)?
> >
> > Not that I know of.  You could be the first!
> >
> >> Or could anyone guide me how to do RTA for URCU/RCU?
> >
> > Compile something with a simple RCU read-side critical section, and then
> > count the instructions.  QSBR will of course work best, but MB will also
> > have good bounds.  Signal-based will be a bit more complicated.
> >
> > Much depends on what type of RTA you want to do.  Brandenburg's
> > dissertation has quite a bit of info and many citations:
> >
> >         http://www.cs.unc.edu/~bbb/diss/
> >
> > You can also take an experimental approach, though a great many
> > runs are required.  OSADL (https://www.osadl.org/) does quite a
> > bit of this work on -rt Linux.
> >
> >                                                         Thanx, Paul
> >
> >> Thanks again.
> >>
> >> On Fri, Mar 11, 2016 at 10:00 PM, Mathieu Desnoyers
> >> <mathieu.desnoyers@efficios.com> wrote:
> >> > ----- On Mar 11, 2016, at 6:45 AM, Paul E. McKenney paulmck@linux.vnet.ibm.com wrote:
> >> >
> >> >> On Thu, Mar 10, 2016 at 08:53:05PM +0000, Mathieu Desnoyers wrote:
> >> >>> ----- On Mar 10, 2016, at 3:33 PM, Yuxin Ren ryx@gwmail.gwu.edu wrote:
> >> >>>
> >> >>> > Thank you for your reply.
> >> >>> >
> >> >>> > I want to generally understand how to apply urcu to real time systems.
> >> >>> > I know real time system focus on predictability on both timing and
> >> >>> > memory consumption.
> >> >>> > So how does real time urcu support predictability?
> >> >>> > Could you provide me some papers, documents or any materials about any
> >> >>> > aspect of real time urcu?
> >> >>>
> >> >>> Adding Paul E. McKenney in CC, who may have some thoughts on this
> >> >>> topic.
> >> >>
> >> >> URCU does timing quite well, given that the read-side primitives each
> >> >> execute a fixed sequence of instructions.  Updates using call_rcu()
> >> >> can be used to minimize update-side latency, but if you need to bound
> >> >> memory overhead, the best way to do that is to make sure that updates
> >> >> are not on the critical path, and then use synchronize_rcu() instead
> >> >> of call_rcu().  In that case, the total amount of memory waiting for
> >> >> reclamation is bounded by the maximum size of an RCU-protected memory
> >> >> block times the number of threads.
> >> >
> >> > An intermediate solution if both update throughput and bounded-memory
> >> > are required (but the application would not have real-time constraints
> >> > on updates) would be to use the defer_rcu() API in liburcu. It amortizes
> >> > the cost of synchronize_rcu() over many defer_rcu() calls with a worker
> >> > thread, but only up to an upper bound. When the upper bound is reached,
> >> > the defer queue call empties the defer queue itself.
> >> >
> >> > Thanks,
> >> >
> >> > Mathieu
> >> >
> >> >>
> >> >> So can you design your application so that updates are off the critical
> >> >> path?  If so, you can get both bounded read-side accesses and bounded
> >> >> memory footprint.
> >> >>
> >> >> This of course assumes that your data structures are simple enough
> >> >> that readers don't need to use retry techniques.
> >> >>
> >> >> The following info might be helpful:
> >> >>
> >> >> http://www2.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf
> >> >> http://www2.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.09.29a.pdf
> >> >>
> >> >> http://www2.rdrop.com/users/paulmck/realtime/paper/RTLWS2012occcRT.2012.10.19e.pdf
> >> >>
> >> >> It also depends on your timeframe.  Microseconds?  Life is hard.
> >> >> Milliseconds?  Care is required, but you have a fair amount of freedom.
> >> >> Seconds?  Life is not so hard.  Unless you need to do two seconds of
> >> >> computation in one second or some such.  ;-)
> >> >>
> >> >>                                                       Thanx, Paul
> >> >>
> >> >>> Thanks,
> >> >>>
> >> >>> Mathieu
> >> >>>
> >> >>> >
> >> >>> > Thanks again!
> >> >>> >
> >> >>> > On Thu, Mar 10, 2016 at 1:52 PM, Michel Dagenais
> >> >>> > <michel.dagenais@polymtl.ca> wrote:
> >> >>> >> Real-time and embedded systems is an important current focus for the LTTng
> >> >>> >> toolchain research. Do you have specific needs for userspace RCU?
> >> >>> >>
> >> >>> >> ----- Mail original -----
> >> >>> >>> Hi,
> >> >>> >>>
> >> >>> >>>  Is there any work or research about Userspace RCU on real time or
> >> >>> >>> embedded systems?
> >> >>> >>> Any information is welcome.
> >> >>> >>>
> >> >>> >>> Thanks a lot!
> >> >>> >>> Yuxin
> >> >>> >>> _______________________________________________
> >> >>> >>> lttng-dev mailing list
> >> >>> >>> lttng-dev@lists.lttng.org
> >> >>> >>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> >> >>> >>>
> >> >>> > _______________________________________________
> >> >>> > lttng-dev mailing list
> >> >>> > lttng-dev@lists.lttng.org
> >> >>> > https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> >> >>>
> >> >>> --
> >> >>> Mathieu Desnoyers
> >> >>> EfficiOS Inc.
> >> >>> http://www.efficios.com
> >> >
> >> > --
> >> > Mathieu Desnoyers
> >> > EfficiOS Inc.
> >> > http://www.efficios.com
> >>
> >
> 

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev