Skip to contentSkip to conversation

Query regarding srcu_funnel_exp_start()

DISCUSSION Neeraj Upadhyay 2 participants 6 messages Oct 27, 2017 – Oct 29, 2017

lore
Share & tools
lore
#0 lore raw

Hi,

One query regarding srcu_funnel_exp_start() function in kernel/rcu/srcutree.c.

static void srcu_funnel_exp_start(struct srcu_struct *sp, struct srcu_node *snp,
unsigned long s)

{
	<snip>
	if (!ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, s))
		sp->srcu_gp_seq_needed_exp = s;
	<snip>
}

Why is sp->srcu_gp_seq_needed_exp set to 's' if srcu_gp_seq_needed_exp is >= 's'. Shouldn't srcu_gp_seq_needed_exp be equal to the greater of both?

Thanks
Neeraj

Signature · 2 lines
QUALCOMM INDIA, on behalf of Qualcomm Innovation Center, Inc. is a
member of the Code Aurora Forum, hosted by The Linux Foundation
#1 lore raw
Quoted 15 lines · Neeraj Upadhyay

Hi,

One query regarding srcu_funnel_exp_start() function in kernel/rcu/srcutree.c.

static void srcu_funnel_exp_start(struct srcu_struct *sp, struct srcu_node *snp,
unsigned long s)

{
	<snip>
	if (!ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, s))
		sp->srcu_gp_seq_needed_exp = s;
	<snip>
}
Quoted 2 lines

Why is sp->srcu_gp_seq_needed_exp set to 's' if srcu_gp_seq_needed_exp is >= 's'. Shouldn't srcu_gp_seq_needed_exp be equal to the greater of both?

Let's suppose that it is incorrect as currently written. Can you construct a test case demonstrating a failure of some sort, then provide a fix?

To start with, if it is currently incorrect, what would be the nature of the failure?

Thanx, Paul

#2 lore raw
Quoted 16 lines · Paul E. McKenney
Quoted 15 lines · Neeraj Upadhyay

Hi,

One query regarding srcu_funnel_exp_start() function in kernel/rcu/srcutree.c.

static void srcu_funnel_exp_start(struct srcu_struct *sp, struct srcu_node *snp,
unsigned long s)

{
	<snip>
	if (!ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, s))
		sp->srcu_gp_seq_needed_exp = s;
	<snip>
}
Quoted 6 lines
Quoted 2 lines

Why is sp->srcu_gp_seq_needed_exp set to 's' if srcu_gp_seq_needed_exp is >= 's'. Shouldn't srcu_gp_seq_needed_exp be equal to the greater of both?

Let's suppose that it is incorrect as currently written. Can you construct a test case demonstrating a failure of some sort, then provide a fix?

Will check this. Might take some time to build a test case.

Quoted 6 lines

To start with, if it is currently incorrect, what would be the nature of the failure?

Thanx, Paul

Hi Paul,

I see below scenario, where new gp won't be expedited. Please correct me if I am missing something here.

1. CPU0 calls synchronize_srcu_expedited()

synchronize_srcu_expedited()
__synchronize_srcu()

    __call_srcu()
            s = rcu_seq_snap(&sp->srcu_gp_seq); // lets say srcu_gp_seq 
 = 0;
                                                // s = 0x100
            sdp->srcu_gp_seq_needed = s // 0x100
            needgp = true
            sdp->srcu_gp_seq_needed_exp = s // 0x100
        srcu_funnel_gp_start()
                sp->srcu_gp_seq_needed_exp = s;
            srcu_gp_start(sp);
                rcu_seq_start(&sp->srcu_gp_seq);

2. CPU1 calls normal synchronize_srcu()

synchronize_srcu()

    __synchronize_srcu(sp, true)
        __call_srcu()
                s = rcu_seq_snap(&sp->srcu_gp_seq); // srcu_gp_seq = 1
                                                    // s= 0x200
                sdp->srcu_gp_seq_needed = s; // 0x200
            srcu_funnel_gp_start()
                smp_store_release(&sp->srcu_gp_seq_needed, s); // 0x200

3. CPU3 calls synchronize_srcu_expedited()

synchronize_srcu_expedited()
__synchronize_srcu()

    __call_srcu()
            s = rcu_seq_snap(&sp->srcu_gp_seq); // srcu_gp_seq = 1
                                                // s = 0x200
            sdp->srcu_gp_seq_needed_exp = s // 0x200
        srcu_funnel_exp_start(sp, sdp->mynode, s);
            // sp->srcu_gp_seq_needed_exp = 0x100
            // s = 0x200 ; sp->srcu_gp_seq_needed_exp is not updated
            if (!ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, s))
                sp->srcu_gp_seq_needed_exp = s;

Thanks
Neeraj

Signature · 2 lines
QUALCOMM INDIA, on behalf of Qualcomm Innovation Center, Inc. is a
member of the Code Aurora Forum, hosted by The Linux Foundation
#3 lore raw
Quoted 17 lines · Neeraj Upadhyay
Quoted 16 lines · Paul E. McKenney
Quoted 15 lines · Neeraj Upadhyay

Hi,

One query regarding srcu_funnel_exp_start() function in kernel/rcu/srcutree.c.

static void srcu_funnel_exp_start(struct srcu_struct *sp, struct srcu_node *snp,
unsigned long s)

{
	<snip>
	if (!ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, s))
		sp->srcu_gp_seq_needed_exp = s;
	<snip>
}
Quoted 8 lines
Quoted 6 lines
Quoted 2 lines

Why is sp->srcu_gp_seq_needed_exp set to 's' if srcu_gp_seq_needed_exp is >= 's'. Shouldn't srcu_gp_seq_needed_exp be equal to the greater of both?

Let's suppose that it is incorrect as currently written. Can you construct a test case demonstrating a failure of some sort, then provide a fix?

Will check this. Might take some time to build a test case.

Fair enough!

I suggest checking to see if kernel/rcu/rcuperf.c can do what you need for this test. (Might not with a single test, but perhaps a before-and-after comparison. Or maybe you really do need to add some test code somewhere.)

Quoted 11 lines
Quoted 5 lines

To start with, if it is currently incorrect, what would be the nature of the failure?

Thanx, Paul

Hi Paul,

I see below scenario, where new gp won't be expedited. Please correct me if I am missing something here.

Quoted 8 lines

1. CPU0 calls synchronize_srcu_expedited()

synchronize_srcu_expedited()
__synchronize_srcu()

    __call_srcu()
            s = rcu_seq_snap(&sp->srcu_gp_seq); // lets say
srcu_gp_seq  = 0;
                                                // s = 0x100

Looks like you have one hex digit and then two binary digits, but why not? (RCU_SEQ_STATE_MASK is 3 rather than 0xff.)

Quoted 23 lines
            sdp->srcu_gp_seq_needed = s // 0x100
            needgp = true
            sdp->srcu_gp_seq_needed_exp = s // 0x100
        srcu_funnel_gp_start()
                sp->srcu_gp_seq_needed_exp = s;
            srcu_gp_start(sp);
                rcu_seq_start(&sp->srcu_gp_seq);

2. CPU1 calls normal synchronize_srcu()

synchronize_srcu()

    __synchronize_srcu(sp, true)
        __call_srcu()
                s = rcu_seq_snap(&sp->srcu_gp_seq); // srcu_gp_seq = 1
                                                    // s= 0x200
                sdp->srcu_gp_seq_needed = s; // 0x200
            srcu_funnel_gp_start()
                smp_store_release(&sp->srcu_gp_seq_needed, s); // 0x200

3. CPU3 calls synchronize_srcu_expedited()

synchronize_srcu_expedited()
__synchronize_srcu()

Quoted 9 lines
    __call_srcu()
            s = rcu_seq_snap(&sp->srcu_gp_seq); // srcu_gp_seq = 1
                                                // s = 0x200
            sdp->srcu_gp_seq_needed_exp = s // 0x200
        srcu_funnel_exp_start(sp, sdp->mynode, s);
            // sp->srcu_gp_seq_needed_exp = 0x100
            // s = 0x200 ; sp->srcu_gp_seq_needed_exp is not updated
            if (!ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, s))
                sp->srcu_gp_seq_needed_exp = s;

Seems plausible, but you should be able to show the difference in grace-period duration with a test.

While you are in srcu_funnel_exp_start(), should it be rechecking rcu_seq_done(&sp->srcu_gp_seq, s) as well as the current ULONG_CMP_GE(snp->srcu_gp_seq_needed_exp, s) under the lock? Why or why not?

Thanx, Paul

#4 lore raw
Quoted 25 lines · Paul E. McKenney
Quoted 24 lines · Neeraj Upadhyay
Quoted 22 lines · Paul E. McKenney
Quoted 15 lines · Neeraj Upadhyay

Hi,

One query regarding srcu_funnel_exp_start() function in kernel/rcu/srcutree.c.

static void srcu_funnel_exp_start(struct srcu_struct *sp, struct srcu_node *snp,
unsigned long s)

{
	<snip>
	if (!ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, s))
		sp->srcu_gp_seq_needed_exp = s;
	<snip>
}
Quoted 2 lines

Why is sp->srcu_gp_seq_needed_exp set to 's' if srcu_gp_seq_needed_exp is >= 's'. Shouldn't srcu_gp_seq_needed_exp be equal to the greater of both?

Let's suppose that it is incorrect as currently written. Can you construct a test case demonstrating a failure of some sort, then provide a fix?

Quoted 8 lines
Quoted 1 line

Will check this. Might take some time to build a test case.

Fair enough!

I suggest checking to see if kernel/rcu/rcuperf.c can do what you need for this test. (Might not with a single test, but perhaps a before-and-after comparison. Or maybe you really do need to add some test code somewhere.)

Thanks for the suggestion, will try that out.

Quoted 20 lines
Quoted 11 lines
Quoted 5 lines

To start with, if it is currently incorrect, what would be the nature of the failure?

Thanx, Paul

Hi Paul,

I see below scenario, where new gp won't be expedited. Please correct me if I am missing something here.

Quoted 8 lines

1. CPU0 calls synchronize_srcu_expedited()

synchronize_srcu_expedited()
__synchronize_srcu()

     __call_srcu()
             s = rcu_seq_snap(&sp->srcu_gp_seq); // lets say
srcu_gp_seq  = 0;
                                                 // s = 0x100
Quoted 2 lines

Looks like you have one hex digit and then two binary digits, but why not? (RCU_SEQ_STATE_MASK is 3 rather than 0xff >

Yeah, sorry I confused myself while representing the values. 0x100 need to be replaced with b'100' and 0x200 with b'1000'.

Quoted 33 lines
Quoted 23 lines
             sdp->srcu_gp_seq_needed = s // 0x100
             needgp = true
             sdp->srcu_gp_seq_needed_exp = s // 0x100
         srcu_funnel_gp_start()
                 sp->srcu_gp_seq_needed_exp = s;
             srcu_gp_start(sp);
                 rcu_seq_start(&sp->srcu_gp_seq);

2. CPU1 calls normal synchronize_srcu()

synchronize_srcu()

     __synchronize_srcu(sp, true)
         __call_srcu()
                 s = rcu_seq_snap(&sp->srcu_gp_seq); // srcu_gp_seq = 1
                                                     // s= 0x200
                 sdp->srcu_gp_seq_needed = s; // 0x200
             srcu_funnel_gp_start()
                 smp_store_release(&sp->srcu_gp_seq_needed, s); // 0x200

3. CPU3 calls synchronize_srcu_expedited()

synchronize_srcu_expedited()
__synchronize_srcu()

Quoted 9 lines
     __call_srcu()
             s = rcu_seq_snap(&sp->srcu_gp_seq); // srcu_gp_seq = 1
                                                 // s = 0x200
             sdp->srcu_gp_seq_needed_exp = s // 0x200
         srcu_funnel_exp_start(sp, sdp->mynode, s);
             // sp->srcu_gp_seq_needed_exp = 0x100
             // s = 0x200 ; sp->srcu_gp_seq_needed_exp is not updated
             if (!ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, s))
                 sp->srcu_gp_seq_needed_exp = s;
Quoted 3 lines

Seems plausible, but you should be able to show the difference in grace-period duration with a test.

Ok sure, will attempt that.

Quoted 7 lines

While you are in srcu_funnel_exp_start(), should it be rechecking rcu_seq_done(&sp->srcu_gp_seq, s) as well as the current ULONG_CMP_GE(snp->srcu_gp_seq_needed_exp, s) under the lock? Why or why not?

Thanx, Paul

Hi Paul,

I don't see how it will impact. I have put markers in code snippet below to explain my points. My understanding is

* rcu_seq_done check @a is a fastpath return, and avoid contention for snp lock, if the gp has already elapsed.

* Checking it @b, inside srcu_node lock might not make any difference, as sp->srcu_gp_seq counter portion is updated under srcu_struct lock. Also, we cannot lock srcu_struct at this point, as it will cause lock contention among multiple CPUs.

* Checking rcu_seq_done @c also does not impact, as we have already done all the work of traversing the entire parent chain and if rcu_seq_done() is true srcu_gp_seq_needed_exp will be greater than or equal to 's'.

  srcu_gp_end()
    raw_spin_lock_irq_rcu_node(sp);
    rcu_seq_end(&sp->srcu_gp_seq);
    gpseq = rcu_seq_current(&sp->srcu_gp_seq);
    if (ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, gpseq))
        sp->srcu_gp_seq_needed_exp = gpseq;
    raw_spin_unlock_irq_rcu_node(sp);

static void srcu_funnel_exp_start(...)

{
    <snip>

    for (; snp != NULL; snp = snp->srcu_parent) {
        if (rcu_seq_done(&sp->srcu_gp_seq, s) ||  /* a */
            ULONG_CMP_GE(READ_ONCE(snp->srcu_gp_seq_needed_exp), s))
            return;
        raw_spin_lock_irqsave_rcu_node(snp, flags);
        /* b */
        if (ULONG_CMP_GE(snp->srcu_gp_seq_needed_exp, s)) {
            raw_spin_unlock_irqrestore_rcu_node(snp, flags);
            return;
        }
        <snip>
        raw_spin_unlock_irqrestore_rcu_node(snp, flags);
    }
    raw_spin_lock_irqsave_rcu_node(sp, flags);
    /* c */
    if (!ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, s))
        sp->srcu_gp_seq_needed_exp = s;
    raw_spin_unlock_irqrestore_rcu_node(sp, flags);
}

Thanks
Neeraj

Signature · 2 lines
QUALCOMM INDIA, on behalf of Qualcomm Innovation Center, Inc. is a
member of the Code Aurora Forum, hosted by The Linux Foundation
#5 lore raw
Quoted 56 lines · Neeraj Upadhyay
Quoted 25 lines · Paul E. McKenney
Quoted 24 lines · Neeraj Upadhyay
Quoted 22 lines · Paul E. McKenney
Quoted 15 lines · Neeraj Upadhyay

Hi,

One query regarding srcu_funnel_exp_start() function in kernel/rcu/srcutree.c.

static void srcu_funnel_exp_start(struct srcu_struct *sp, struct srcu_node *snp,
unsigned long s)

{
	<snip>
	if (!ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, s))
		sp->srcu_gp_seq_needed_exp = s;
	<snip>
}
Quoted 2 lines

Why is sp->srcu_gp_seq_needed_exp set to 's' if srcu_gp_seq_needed_exp is >= 's'. Shouldn't srcu_gp_seq_needed_exp be equal to the greater of both?

Let's suppose that it is incorrect as currently written. Can you construct a test case demonstrating a failure of some sort, then provide a fix?

Quoted 7 lines
Quoted 1 line

Will check this. Might take some time to build a test case.

Fair enough!

I suggest checking to see if kernel/rcu/rcuperf.c can do what you need for this test. (Might not with a single test, but perhaps a before-and-after comparison. Or maybe you really do need to add some test code somewhere.)

Thanks for the suggestion, will try that out.

Quoted 20 lines
Quoted 19 lines
Quoted 5 lines

To start with, if it is currently incorrect, what would be the nature of the failure?

Thanx, Paul

Hi Paul,

I see below scenario, where new gp won't be expedited. Please correct me if I am missing something here.

1. CPU0 calls synchronize_srcu_expedited()

synchronize_srcu_expedited()
__synchronize_srcu()

    __call_srcu()
            s = rcu_seq_snap(&sp->srcu_gp_seq); // lets say
srcu_gp_seq  = 0;
                                                // s = 0x100
Quoted 5 lines
Quoted 2 lines

Looks like you have one hex digit and then two binary digits, but why not? (RCU_SEQ_STATE_MASK is 3 rather than 0xff >

Yeah, sorry I confused myself while representing the values. 0x100 need to be replaced with b'100' and 0x200 with b'1000'.

Sounds like something I would do! ;-)

Quoted 87 lines
Quoted 33 lines
Quoted 23 lines
            sdp->srcu_gp_seq_needed = s // 0x100
            needgp = true
            sdp->srcu_gp_seq_needed_exp = s // 0x100
        srcu_funnel_gp_start()
                sp->srcu_gp_seq_needed_exp = s;
            srcu_gp_start(sp);
                rcu_seq_start(&sp->srcu_gp_seq);

2. CPU1 calls normal synchronize_srcu()

synchronize_srcu()

    __synchronize_srcu(sp, true)
        __call_srcu()
                s = rcu_seq_snap(&sp->srcu_gp_seq); // srcu_gp_seq = 1
                                                    // s= 0x200
                sdp->srcu_gp_seq_needed = s; // 0x200
            srcu_funnel_gp_start()
                smp_store_release(&sp->srcu_gp_seq_needed, s); // 0x200

3. CPU3 calls synchronize_srcu_expedited()

synchronize_srcu_expedited()
__synchronize_srcu()

Quoted 9 lines
    __call_srcu()
            s = rcu_seq_snap(&sp->srcu_gp_seq); // srcu_gp_seq = 1
                                                // s = 0x200
            sdp->srcu_gp_seq_needed_exp = s // 0x200
        srcu_funnel_exp_start(sp, sdp->mynode, s);
            // sp->srcu_gp_seq_needed_exp = 0x100
            // s = 0x200 ; sp->srcu_gp_seq_needed_exp is not updated
            if (!ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, s))
                sp->srcu_gp_seq_needed_exp = s;
Quoted 3 lines

Seems plausible, but you should be able to show the difference in grace-period duration with a test.

Ok sure, will attempt that.

Quoted 6 lines

While you are in srcu_funnel_exp_start(), should it be rechecking rcu_seq_done(&sp->srcu_gp_seq, s) as well as the current ULONG_CMP_GE(snp->srcu_gp_seq_needed_exp, s) under the lock? Why or why not?

Thanx, Paul

Hi Paul,

I don't see how it will impact. I have put markers in code snippet below to explain my points. My understanding is

* rcu_seq_done check @a is a fastpath return, and avoid contention for snp lock, if the gp has already elapsed.

* Checking it @b, inside srcu_node lock might not make any difference, as sp->srcu_gp_seq counter portion is updated under srcu_struct lock. Also, we cannot lock srcu_struct at this point, as it will cause lock contention among multiple CPUs.

* Checking rcu_seq_done @c also does not impact, as we have already done all the work of traversing the entire parent chain and if rcu_seq_done() is true srcu_gp_seq_needed_exp will be greater than or equal to 's'.

  srcu_gp_end()
    raw_spin_lock_irq_rcu_node(sp);
    rcu_seq_end(&sp->srcu_gp_seq);
    gpseq = rcu_seq_current(&sp->srcu_gp_seq);
    if (ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, gpseq))
        sp->srcu_gp_seq_needed_exp = gpseq;
    raw_spin_unlock_irq_rcu_node(sp);

static void srcu_funnel_exp_start(...)

{
    <snip>

    for (; snp != NULL; snp = snp->srcu_parent) {
        if (rcu_seq_done(&sp->srcu_gp_seq, s) ||  /* a */
            ULONG_CMP_GE(READ_ONCE(snp->srcu_gp_seq_needed_exp), s))
            return;
        raw_spin_lock_irqsave_rcu_node(snp, flags);
        /* b */
        if (ULONG_CMP_GE(snp->srcu_gp_seq_needed_exp, s)) {
            raw_spin_unlock_irqrestore_rcu_node(snp, flags);
            return;
        }
        <snip>
Quoted 8 lines
        raw_spin_unlock_irqrestore_rcu_node(snp, flags);
    }
    raw_spin_lock_irqsave_rcu_node(sp, flags);
    /* c */
    if (!ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, s))
        sp->srcu_gp_seq_needed_exp = s;
    raw_spin_unlock_irqrestore_rcu_node(sp, flags);
}

That does match my understanding, thank you for taking the time to go through it! Especially given that my understanding has proven to be wrong from time to time. ;-)

Thanx, Paul