* SRCU: Question on srcu_advance_state
@ 2020-11-20 8:30 Zhang,Qiang
2020-11-21 1:11 ` Paul E. McKenney
0 siblings, 1 reply; 6+ messages in thread
From: Zhang,Qiang @ 2020-11-20 8:30 UTC (permalink / raw)
To: paulmck; +Cc: rcu, Joel Fernandes
Hello Pual
sorry to disturb you, I also have some quesetion for you:
in srcu_advance_state function, when seq state == SRCU_STATE_SCAN1, we
will check, if the previous readers critical region exits, will be
returned directly.
I'd like to know under what scenario this will happen?
Thanks
Qiang
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: SRCU: Question on srcu_advance_state
2020-11-20 8:30 SRCU: Question on srcu_advance_state Zhang,Qiang
@ 2020-11-21 1:11 ` Paul E. McKenney
2020-11-23 1:59 ` 回复: " Zhang, Qiang
0 siblings, 1 reply; 6+ messages in thread
From: Paul E. McKenney @ 2020-11-21 1:11 UTC (permalink / raw)
To: Zhang,Qiang; +Cc: rcu, Joel Fernandes
On Fri, Nov 20, 2020 at 04:30:15PM +0800, Zhang,Qiang wrote:
> Hello Pual
>
> sorry to disturb you, I also have some quesetion for you:
>
> in srcu_advance_state function, when seq state == SRCU_STATE_SCAN1, we will
> check, if the previous readers critical region exits, will be returned
> directly.
>
> I'd like to know under what scenario this will happen?
Suppose that a reader gets preempted for a very long time in the
middle of __srcu_read_lock():
int __srcu_read_lock(struct srcu_struct *ssp)
{
int idx;
idx = READ_ONCE(ssp->srcu_idx) & 0x1;
// PREEMPTED RIGHT HERE
this_cpu_inc(ssp->sda->srcu_lock_count[idx]);
smp_mb(); /* B */ /* Avoid leaking the critical section. */
return idx;
}
Suppose that several SRCU grace periods elapse during that preemption.
Do you see how that can lead to your SRCU_STATE_SCAN1 early exit?
Thanx, Paul
PS: The paper below outlines a similar situation in userspace RCU,
so feel free to use this paper as a hint. The paper is in two
pieces, with the first piece in the first URL and the second in
either of the last two URLs.
@article{MathieuDesnoyers2012URCU,
Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole",
Title="User-Level Implementations of Read-Copy Update",
journal="IEEE Transactions on Parallel and Distributed Systems",
volume={23},
year="2012",
issn="1045-9219",
pages="375-382",
doi="10.1109/TPDS.2011.159",
publisher="IEEE Computer Society",
address="Los Alamitos, CA, USA",
annotation={
RCU overview, desiderata, semi-formal semantics, user-level RCU
usage scenarios, three classes of RCU implementation, wait-free
RCU updates, RCU grace-period batching, update overhead,
http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
http://www.computer.org/cms/Computer.org/dl/trans/td/2012/02/extras/ttd2012020375s.pdf
},
}
^ permalink raw reply [flat|nested] 6+ messages in thread
* 回复: SRCU: Question on srcu_advance_state
2020-11-21 1:11 ` Paul E. McKenney
@ 2020-11-23 1:59 ` Zhang, Qiang
2020-11-25 3:03 ` Paul E. McKenney
0 siblings, 1 reply; 6+ messages in thread
From: Zhang, Qiang @ 2020-11-23 1:59 UTC (permalink / raw)
To: paulmck; +Cc: rcu, Joel Fernandes
________________________________________
发件人: Paul E. McKenney <paulmck@kernel.org>
发送时间: 2020年11月21日 9:11
收件人: Zhang, Qiang
抄送: rcu@vger.kernel.org; Joel Fernandes
主题: Re: SRCU: Question on srcu_advance_state
[Please note this e-mail is from an EXTERNAL e-mail address]
On Fri, Nov 20, 2020 at 04:30:15PM +0800, Zhang,Qiang wrote:
> Hello Pual
>
> sorry to disturb you, I also have some quesetion for you:
>
> in srcu_advance_state function, when seq state == SRCU_STATE_SCAN1, we will
> check, if the previous readers critical region exits, will be returned
> directly.
>
> I'd like to know under what scenario this will happen?
>Suppose that a reader gets preempted for a very long time in the
>middle of __srcu_read_lock():
>
> int __srcu_read_lock(struct srcu_struct *ssp)
> {
> int idx;
>
> idx = READ_ONCE(ssp->srcu_idx) & 0x1;
> // PREEMPTED RIGHT HERE
> this_cpu_inc(ssp->sda->srcu_lock_count[idx]);
> smp_mb(); /* B */ /* Avoid leaking the critical section. */
> return idx;
> }
>Suppose that several SRCU grace periods elapse during that preemption.
>
>Do you see how that can lead to your SRCU_STATE_SCAN1 early exit?
I see, thank you for your explanation.
Thanks
Qiang
>
> Thanx, Paul
>
>
>PS: The paper below outlines a similar situation in userspace RCU,
> so feel free to use this paper as a hint. The paper is in two
> pieces, with the first piece in the first URL and the second in
> either of the last two URLs.
>
>@article{MathieuDesnoyers2012URCU,
> Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel >R. Dagenais and Jonathan Walpole",
> Title="User-Level Implementations of Read-Copy Update",
>journal="IEEE Transactions on Parallel and Distributed Systems",
>volume={23},
> year="2012",
>issn="1045-9219",
> pages="375-382",
> doi="10.1109/TPDS.2011.159",
>publisher="IEEE Computer Society",
> address="Los Alamitos, CA, USA",
> annotation={
> RCU overview, desiderata, semi-formal semantics, user-level RCU
> usage scenarios, three classes of RCU implementation, wait-free
> RCU updates, RCU grace-period batching, update overhead,
> http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
> http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
> http://www.computer.org/cms/Computer.org/dl/trans/td/2012/02/extras/ttd2012020375s.pdf
>},
>}
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: 回复: SRCU: Question on srcu_advance_state
2020-11-23 1:59 ` 回复: " Zhang, Qiang
@ 2020-11-25 3:03 ` Paul E. McKenney
2020-11-27 8:19 ` 回复: " Zhang, Qiang
0 siblings, 1 reply; 6+ messages in thread
From: Paul E. McKenney @ 2020-11-25 3:03 UTC (permalink / raw)
To: Zhang, Qiang; +Cc: rcu, Joel Fernandes
On Mon, Nov 23, 2020 at 01:59:37AM +0000, Zhang, Qiang wrote:
>
>
> ________________________________________
> 发件人: Paul E. McKenney <paulmck@kernel.org>
> 发送时间: 2020年11月21日 9:11
> 收件人: Zhang, Qiang
> 抄送: rcu@vger.kernel.org; Joel Fernandes
> 主题: Re: SRCU: Question on srcu_advance_state
>
> [Please note this e-mail is from an EXTERNAL e-mail address]
>
> On Fri, Nov 20, 2020 at 04:30:15PM +0800, Zhang,Qiang wrote:
> > Hello Pual
> >
> > sorry to disturb you, I also have some quesetion for you:
> >
> > in srcu_advance_state function, when seq state == SRCU_STATE_SCAN1, we will
> > check, if the previous readers critical region exits, will be returned
> > directly.
> >
> > I'd like to know under what scenario this will happen?
>
> >Suppose that a reader gets preempted for a very long time in the
> >middle of __srcu_read_lock():
> >
> > int __srcu_read_lock(struct srcu_struct *ssp)
> > {
> > int idx;
> >
> > idx = READ_ONCE(ssp->srcu_idx) & 0x1;
> > // PREEMPTED RIGHT HERE
> > this_cpu_inc(ssp->sda->srcu_lock_count[idx]);
> > smp_mb(); /* B */ /* Avoid leaking the critical section. */
> > return idx;
> > }
>
> >Suppose that several SRCU grace periods elapse during that preemption.
> >
> >Do you see how that can lead to your SRCU_STATE_SCAN1 early exit?
>
> I see, thank you for your explanation.
To cement your new knowledge, can you tell me in detail the sequence of
events, line by line in the code, that would lead to the SRCU_STATE_SCAN1
early exit?
Thanx, Paul
> Thanks
> Qiang
> >
> > Thanx, Paul
> >
> >
> >PS: The paper below outlines a similar situation in userspace RCU,
> > so feel free to use this paper as a hint. The paper is in two
> > pieces, with the first piece in the first URL and the second in
> > either of the last two URLs.
> >
> >@article{MathieuDesnoyers2012URCU,
> > Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel >R. Dagenais and Jonathan Walpole",
> > Title="User-Level Implementations of Read-Copy Update",
> >journal="IEEE Transactions on Parallel and Distributed Systems",
> >volume={23},
> > year="2012",
> >issn="1045-9219",
> > pages="375-382",
> > doi="10.1109/TPDS.2011.159",
> >publisher="IEEE Computer Society",
> > address="Los Alamitos, CA, USA",
> > annotation={
> > RCU overview, desiderata, semi-formal semantics, user-level RCU
> > usage scenarios, three classes of RCU implementation, wait-free
> > RCU updates, RCU grace-period batching, update overhead,
> > http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
> > http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
> > http://www.computer.org/cms/Computer.org/dl/trans/td/2012/02/extras/ttd2012020375s.pdf
> >},
> >}
^ permalink raw reply [flat|nested] 6+ messages in thread
* 回复: 回复: SRCU: Question on srcu_advance_state
2020-11-25 3:03 ` Paul E. McKenney
@ 2020-11-27 8:19 ` Zhang, Qiang
2020-12-02 18:10 ` Paul E. McKenney
0 siblings, 1 reply; 6+ messages in thread
From: Zhang, Qiang @ 2020-11-27 8:19 UTC (permalink / raw)
To: paulmck; +Cc: rcu, Joel Fernandes
On Mon, Nov 23, 2020 at 01:59:37AM +0000, Zhang, Qiang wrote:
>
>
> ________________________________________
> 发件人: Paul E. McKenney <paulmck@kernel.org>
> 发送时间: 2020年11月21日 9:11
> 收件人: Zhang, Qiang
> 抄送: rcu@vger.kernel.org; Joel Fernandes
> 主题: Re: SRCU: Question on srcu_advance_state
>
> [Please note this e-mail is from an EXTERNAL e-mail address]
>
> On Fri, Nov 20, 2020 at 04:30:15PM +0800, Zhang,Qiang wrote:
> > Hello Pual
> >
> > sorry to disturb you, I also have some quesetion for you:
> >
> > in srcu_advance_state function, when seq state == SRCU_STATE_SCAN1, we will
> > check, if the previous readers critical region exits, will be returned
> > directly.
> >
> > I'd like to know under what scenario this will happen?
>
> >Suppose that a reader gets preempted for a very long time in the
> >middle of __srcu_read_lock():
> >
> > int __srcu_read_lock(struct srcu_struct *ssp)
> > {
> > int idx;
> >
> > idx = READ_ONCE(ssp->srcu_idx) & 0x1;
> > // PREEMPTED RIGHT HERE
> > this_cpu_inc(ssp->sda->srcu_lock_count[idx]);
> > smp_mb(); /* B */ /* Avoid leaking the critical section. */
> > return idx;
> > }
>
> >Suppose that several SRCU grace periods elapse during that preemption.
> >
> >Do you see how that can lead to your SRCU_STATE_SCAN1 early exit?
>
> I see, thank you for your explanation.
>>>To cement your new knowledge, can you tell me in detail the sequence of
>>>events, line by line in the code, that would lead to the >>>SRCU_STATE_SCAN1
>>>early exit?
>>>
Suppose you have the following scenario :
ssp->srcu_idx = 0
cpu0 cpu1
__srcu_read_lock process_srcu
idx = READ_ONCE(ssp->srcu_idx) & 0x1; srcu_advance_state
/*idx == 0,*/ by preempt long time SRCU_STATE_SCAN1
idx = 1 ^ (ssp->srcu_idx & 1);
/*idx == 1*/
try_check_zero (idx)== true
other task run srcu_flip(ssp);
/* ssp->srcu_idx == 1*/
SRCU_STATE_SCAN2
idx = 1 ^ (ssp->srcu_idx & 1);
/*idx == 0*/
try_check_zero (idx)== true
srcu_gp_end
current task run
this_cpu_inc(ssp->sda->srcu_lock_count[idx]); process_srcu
srcu_advance_state
SRCU_STATE_SCAN1
/*ssp->srcu_idx ==1*/
idx = 1 ^ (ssp->srcu_idx & 1);
/*idx==0*/
try_check_zero == false
return
do something
__srcu_read_unlock
/*idx == 0*/
this_cpu_inc(ssp->sda->srcu_unlock_count[idx]);
Thanks
Qiang
> >
> > Thanx, Paul
> >
> >
> >PS: The paper below outlines a similar situation in userspace RCU,
> > so feel free to use this paper as a hint. The paper is in two
> > pieces, with the first piece in the first URL and the second in
> > either of the last two URLs.
> >
> >@article{MathieuDesnoyers2012URCU,
> > Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel >R. Dagenais and Jonathan Walpole",
> > Title="User-Level Implementations of Read-Copy Update",
> >journal="IEEE Transactions on Parallel and Distributed Systems",
> >volume={23},
> > year="2012",
> >issn="1045-9219",
> > pages="375-382",
> > doi="10.1109/TPDS.2011.159",
> >publisher="IEEE Computer Society",
> > address="Los Alamitos, CA, USA",
> > annotation={
> > RCU overview, desiderata, semi-formal semantics, user-level RCU
> > usage scenarios, three classes of RCU implementation, wait-free
> > RCU updates, RCU grace-period batching, update overhead,
> > http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
> > http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
> > http://www.computer.org/cms/Computer.org/dl/trans/td/2012/02/extras/ttd2012020375s.pdf
> >},
> >}
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: 回复: 回复: SRCU: Question on srcu_advance_state
2020-11-27 8:19 ` 回复: " Zhang, Qiang
@ 2020-12-02 18:10 ` Paul E. McKenney
0 siblings, 0 replies; 6+ messages in thread
From: Paul E. McKenney @ 2020-12-02 18:10 UTC (permalink / raw)
To: Zhang, Qiang; +Cc: rcu, Joel Fernandes
On Fri, Nov 27, 2020 at 08:19:32AM +0000, Zhang, Qiang wrote:
>
> On Mon, Nov 23, 2020 at 01:59:37AM +0000, Zhang, Qiang wrote:
> >
> >
> > ________________________________________
> > 发件人: Paul E. McKenney <paulmck@kernel.org>
> > 发送时间: 2020年11月21日 9:11
> > 收件人: Zhang, Qiang
> > 抄送: rcu@vger.kernel.org; Joel Fernandes
> > 主题: Re: SRCU: Question on srcu_advance_state
> >
> > [Please note this e-mail is from an EXTERNAL e-mail address]
> >
> > On Fri, Nov 20, 2020 at 04:30:15PM +0800, Zhang,Qiang wrote:
> > > Hello Pual
> > >
> > > sorry to disturb you, I also have some quesetion for you:
> > >
> > > in srcu_advance_state function, when seq state == SRCU_STATE_SCAN1, we will
> > > check, if the previous readers critical region exits, will be returned
> > > directly.
> > >
> > > I'd like to know under what scenario this will happen?
> >
> > >Suppose that a reader gets preempted for a very long time in the
> > >middle of __srcu_read_lock():
> > >
> > > int __srcu_read_lock(struct srcu_struct *ssp)
> > > {
> > > int idx;
> > >
> > > idx = READ_ONCE(ssp->srcu_idx) & 0x1;
> > > // PREEMPTED RIGHT HERE
> > > this_cpu_inc(ssp->sda->srcu_lock_count[idx]);
> > > smp_mb(); /* B */ /* Avoid leaking the critical section. */
> > > return idx;
> > > }
> >
> > >Suppose that several SRCU grace periods elapse during that preemption.
> > >
> > >Do you see how that can lead to your SRCU_STATE_SCAN1 early exit?
> >
> > I see, thank you for your explanation.
>
> >>>To cement your new knowledge, can you tell me in detail the sequence of
> >>>events, line by line in the code, that would lead to the >>>SRCU_STATE_SCAN1
> >>>early exit?
> >>>
>
> Suppose you have the following scenario :
> ssp->srcu_idx = 0
>
> cpu0 cpu1
>
> __srcu_read_lock process_srcu
> idx = READ_ONCE(ssp->srcu_idx) & 0x1; srcu_advance_state
> /*idx == 0,*/ by preempt long time SRCU_STATE_SCAN1
> idx = 1 ^ (ssp->srcu_idx & 1);
> /*idx == 1*/
> try_check_zero (idx)== true
> other task run srcu_flip(ssp);
> /* ssp->srcu_idx == 1*/
> SRCU_STATE_SCAN2
> idx = 1 ^ (ssp->srcu_idx & 1);
> /*idx == 0*/
> try_check_zero (idx)== true
> srcu_gp_end
> current task run
> this_cpu_inc(ssp->sda->srcu_lock_count[idx]); process_srcu
> srcu_advance_state
> SRCU_STATE_SCAN1
> /*ssp->srcu_idx ==1*/
> idx = 1 ^ (ssp->srcu_idx & 1);
> /*idx==0*/
> try_check_zero == false
> return
>
> do something
>
> __srcu_read_unlock
> /*idx == 0*/
> this_cpu_inc(ssp->sda->srcu_unlock_count[idx]);
Very good!
If you are interested, you might consider blogging this, whether in
English or your native language.
Thanx, Paul
> Thanks
> Qiang
>
> > >
> > > Thanx, Paul
> > >
> > >
> > >PS: The paper below outlines a similar situation in userspace RCU,
> > > so feel free to use this paper as a hint. The paper is in two
> > > pieces, with the first piece in the first URL and the second in
> > > either of the last two URLs.
> > >
> > >@article{MathieuDesnoyers2012URCU,
> > > Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel >R. Dagenais and Jonathan Walpole",
> > > Title="User-Level Implementations of Read-Copy Update",
> > >journal="IEEE Transactions on Parallel and Distributed Systems",
> > >volume={23},
> > > year="2012",
> > >issn="1045-9219",
> > > pages="375-382",
> > > doi="10.1109/TPDS.2011.159",
> > >publisher="IEEE Computer Society",
> > > address="Los Alamitos, CA, USA",
> > > annotation={
> > > RCU overview, desiderata, semi-formal semantics, user-level RCU
> > > usage scenarios, three classes of RCU implementation, wait-free
> > > RCU updates, RCU grace-period batching, update overhead,
> > > http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
> > > http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
> > > http://www.computer.org/cms/Computer.org/dl/trans/td/2012/02/extras/ttd2012020375s.pdf
> > >},
> > >}
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2020-12-02 18:11 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-11-20 8:30 SRCU: Question on srcu_advance_state Zhang,Qiang
2020-11-21 1:11 ` Paul E. McKenney
2020-11-23 1:59 ` 回复: " Zhang, Qiang
2020-11-25 3:03 ` Paul E. McKenney
2020-11-27 8:19 ` 回复: " Zhang, Qiang
2020-12-02 18:10 ` Paul E. McKenney
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).