Skip to contentSkip to conversation

__rcu_process_callbacks() in Linux 2.6

DISCUSSION James Huang 2 participants 2 messages Nov 21, 2007

lore
Share & tools
lore
#0 lore raw

Paul,

I am not sure I understand your answer about using test_and_set_bit() in tasklet_schedule() as a
memory barrier in this case.

       Yes, tasklet_schedule() includes a test_and_set_bit(TASKLET_STATE_SCHED, &t->state) on a tasklet, but 

in this case the tasklet is a per CPU tasklet.

According to documentation/atomic_ops.txt, atomic op that returns a value has the semantics of
"explicit memory barriers performed before and after the operation".
If I understand it correctly, this means that, for exmaple,

           atomic_t aa = ATOMIC_INIT(0);
           int X = 1;
           int Y = 2;

CPU 0:

          update X=100;
          atomc_inc_return(&aa);
          update Y=200;

Then CPU 1 will always see X=100 before it sees the new value of aa (1), and CPU 1 wil always see the new value of aa (1) before it sees Y=200.

This ordering semantics does not apply to the scenario in our discussion.
For one thing, the rcu tasklet is a per CPU tasklet. So obviously no other CPU's will even read its t->state.

Am I still missing something?
By the way, which tasklet_schedule() are you referring to in your previous email? Is it the one called by CPU 0, CPU 1, or CPU 2?

Thanks,
James Huang

----- Original Message ----
From: Paul E. McKenney <[email protected]>
To: James Huang <[email protected]>
Cc: [email protected]; [email protected]; [email protected]
Sent: Wednesday, November 21, 2007 8:54:15 AM
Subject: Re: __rcu_process_callbacks() in Linux 2.6

Quoted 114 lines · James Huang

Please disregard the previous email.

In the latest Linux 2.6 RCU implementation, __rcu_process_callbacks() is coded as follows:

422 static void __rcu_process_callbacks(struct rcu_ctrlblk *rcp,
423 struct rcu_data *rdp)
424 {
425 if (rdp->curlist && !rcu_batch_before(rcp->completed, rdp->batch)) {

426                *rdp->donetail = rdp->curlist;
427                rdp->donetail = rdp->curtail;
428                rdp->curlist = NULL;
429                rdp->curtail = &rdp->curlist;
430        }
431 
432        if (rdp->nxtlist && !rdp->curlist) {
433                local_irq_disable();
434                rdp->curlist = rdp->nxtlist;
435                rdp->curtail = rdp->nxttail;
436                rdp->nxtlist = NULL;
437                rdp->nxttail = &rdp->nxtlist;
438                local_irq_enable();

439
440 /*
441 * start the next batch of callbacks
442 */
443

444                /* determine batch number */
445                rdp->batch = rcp->cur + 1;
446                /* see the comment and corresponding wmb() in

447 * the rcu_start_batch()
448 */
449 smp_rmb();
450
451 if (!rcp->next_pending) {

452                        /* and start it/schedule start if it's a new batch */
453                        spin_lock(&rcp->lock);
454                        rcp->next_pending = 1;
455                        rcu_start_batch(rcp);
456                        spin_unlock(&rcp->lock);

457 }
458 }
459
460 rcu_check_quiescent_state(rcp, rdp);
461 if (rdp->donelist)
462 rcu_do_batch(rdp);
463 }

The question is how does the update of rdp->batch at line 445 guarantee to observe the most updated value of rcp->cur?? The issue is that there is no memory barrier/locking before line 445.
So I think the following sequence of events in chronological order is possible:

Assume initially rcp->cur = 100, this current batch value is visible to every CPU, and batch 100 has completed
(i.e. rcp->completed = 100, rcp->next_pending = 0, rcp->cpumask = 0, and for each CPU, rdp->quiescbatch = 100, rdp->qs_pending = 0, rdp->passed_quiesc = 1)

CPU 0:
---------

             call_rcu(): a callback inserted into rdp->nxtlist;                    

             timer interrupt 
               call rcu_pending(), return true  ( ! rdp->curlist && rdp->nxtlist)
               call rcu_check_callbacks() 
                     schedule per CPU rcu_tasklet

               __rcu_process_callbacks()
                           move callbacks from nxtlist to curlist;
                           rdp->batch = 101
                           lock rcp->lock
                           rcp->next_pending = 1
                           call rcu_start_batch()
                                 find the current batch has completed and next batch pending;
                                 rcp->next_pending = 0
                                 update rcp->cur to 101 and initialize rcp->cpumask;                  <----- time t1
                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                           unlock rcp->lock

CPU 1:
---------

             timer interrupt 
                 call rcu_pending(), return true (asume observing rcp->cur = 101 != rdp->quiescbatch) 
                 
                 call rcu_check_callbacks() 
                       schedule per CPU rcu_tasklet

                 __rcu_process_callbacks()
                       call rcu_check_quisecent_state()
                             find rdp->quiescbatch != rcp->cur
                             set rdp->qs_pending = 1
                             set rdp->passed_quiesc = 0
                             set rdp->quiescbatch = 101 (rcp->cur)

             Another timer interrupt
                 call rcu_pending(), return true (rdp->qs_pending == 1)  
                 call rcu_check_callbacks() 
                       (assume in user mode)                        <-- time t2  pass quiescent state
                       ~~~~~~~~~~~~~~~~~~                            ~~~~~~~~~~~~~~~~~~~~~~
                       rdp->passed_quiesc = 1
                       schedule per CPU rcu_tasklet
           
                 __rcu_process_callbacks()
                       call rcu_check_quisecent_state()
                             find rdp->qs_pending == 1 && rdp-> passed_quiesc == 1
                             set rdp->qs_pending = 0
                             lock rcp->lock
                             call cpu_quite()
                                   clear bit in the rcp->cpumask set up by CPU 0 at time t1
                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                             unlock rcp->lock

CPU 2:
---------

Quoted 7 lines
             call_rcu(): a callback inserted into rdp->nxtlist;    <--- time t3
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             
             timer interrupt 
                 call rcu_pending(), return true ( ! rdp->curlist && rdp->nxtlist)
                 call rcu_check_callbacks() 
                     schedule per CPU rcu_tasklet

The tasklet_schedule() code calls test_and_set_bit(), which is an atomic operation that returns a value. It therefore implies a memory barrier, so that if the prior call_rcu() at time t3 "happens after" CPU 1's quiescent state at time t2 (which, due to locking, must follow the update to rcp->cur at time t1), then the access to rcp->cur at time t4 must see the new value of rcp->cur.

This is admittedly a bit subtle and perhaps a bit fragile. Manfred, Dipankar, would it be worth putting an explicit memory barrier somewhere in this sequence, or is there another memory barrier that I forgetting?

Thanx, Paul

Quoted 19 lines
                 calls __rcu_process_callbacks()
                     move callbacks from nxtlist to curlist; (including the callback inserted at time t3)
                     rdp->batch = rcp->cur + 1;                        <--- time t4
                     ~~~~~~~~~~~~~~~~~~~~

At time t4, CPU 2 might observe rcp->cpu as 100 and set rdp->batch to 101.
So CPU 2 essentially started its batch 101 (includes a callback inserted at time t3) after CPU 1 passed its quiescent state (at time t2) for batch 101.

Isn't this an issue??? Am I missing something?
Thanks for pointing me to the right direction.

-- James Huang
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

#1 lore raw
Quoted 7 lines · James Huang

Paul,

I am not sure I understand your answer about using test_and_set_bit() in tasklet_schedule() as a
memory barrier in this case.

       Yes, tasklet_schedule() includes a test_and_set_bit(TASKLET_STATE_SCHED, &t->state) on a tasklet, but 

in this case the tasklet is a per CPU tasklet.

Memory barriers are memory barriers, regardless of what type of data is being processed.

Quoted 2 lines

According to documentation/atomic_ops.txt, atomic op that returns a value has the semantics of
"explicit memory barriers performed before and after the operation".

And test_and_set_bit() does return a value, namely the value of the affected bit before the operation. Therefore, any correct implementation for a CONFIG_SMP build must include memory barriers before and after. Extracting the relevant passage from Documentation/atomic_ops.txt between the pair of dashed lines:

------------------------------------------------------------------------

	int test_and_set_bit(unsigned long nr, volatile unsigned long *addr);
	int test_and_clear_bit(unsigned long nr, volatile unsigned long *addr);
	int test_and_change_bit(unsigned long nr, volatile unsigned long *addr);

Like the above, except that these routines return a boolean which indicates whether the changed bit was set _BEFORE_ the atomic bit operation.

WARNING! It is incredibly important that the value be a boolean, ie. "0" or "1". Do not try to be fancy and save a few instructions by declaring the above to return "long" and just returning something like "old_val & mask" because that will not work.

For one thing, this return value gets truncated to int in many code paths using these interfaces, so on 64-bit if the bit is set in the upper 32-bits then testers will never see that.

One great example of where this problem crops up are the thread_info flag operations. Routines such as test_and_set_ti_thread_flag() chop the return value into an int. There are other places where things like this occur as well.

These routines, like the atomic_t counter operations returning values, require explicit memory barrier semantics around their execution. All memory operations before the atomic bit operation call must be made visible globally before the atomic bit operation is made visible. Likewise, the atomic bit operation must be visible globally before any subsequent memory operation is made visible. For example:

	obj->dead = 1;
	if (test_and_set_bit(0, &obj->flags))
		/* ... */;
	obj->killed = 1;

The implementation of test_and_set_bit() must guarantee that "obj->dead = 1;" is visible to cpus before the atomic memory operation done by test_and_set_bit() becomes visible. Likewise, the atomic memory operation done by test_and_set_bit() must become visible before "obj->killed = 1;" is visible.

------------------------------------------------------------------------

Quoted 9 lines

If I understand it correctly, this means that, for exmaple,

           atomic_t aa = ATOMIC_INIT(0);
           int X = 1;
           int Y = 2;
 CPU 0:
          update X=100;
          atomc_inc_return(&aa);
          update Y=200;

But, yes, atomic_inc_return() does indeed force ordering.

Quoted 2 lines

Then CPU 1 will always see X=100 before it sees the new value of aa (1), and CPU 1 wil always see the new value of aa (1) before it sees Y=200.

Yep. And CPU 1 will also see any preceding unrelated assignment prior to the new value of aa as well. And it is not just preceding stores. See the sentence from Documentation/atomic_ops.txt:

All memory operations before the atomic bit operation call must be made visible globally before the atomic bit operation is made visible.

Both stores -and- loads.

Quoted 4 lines

This ordering semantics does not apply to the scenario in our discussion.
For one thing, the rcu tasklet is a per CPU tasklet. So obviously no other CPU's will even read its t->state.

Am I still missing something?

Yep -- the test_and_set_bit() operation has no clue who else might or might not be reading t->state. Besides, tasklets need not be allocated on a per-CPU basis, and therefore tasklet_schedule() must be prepared to deal with other CPUs concurrently manipulating t->state, for example, via the tasklet_disable() interface.

Another thing that might help is to fill in the RCU read-side critical section that CPU 2 would have to execute (after all the stuff you currently have it executing), along with the RCU update that would need to precede CPU 2's call_rcu() call. I have done this in your example code below.

Note that in order for a failure to occur, CPU 1 must reach /* A */ before CPU 2 reaches /* B */.

One key point is that tasklet_schedule()'s memory ordering affects this preceding code for CPU 2. The second key point is that acquiring and releasing a lock acts as a barrier as well (though a limited one).

The result is that CPU 2 must see CPU 1's update to rcp->cur in the case that CPU 1 makes it to /* A */ before CPU 2 makes it to /* B */.

Quoted 2 lines

By the way, which tasklet_schedule() are you referring to in your previous email? Is it the one called by CPU 0, CPU 1, or CPU 2?

The one called by CPU 2 that appears immediately before my response below.

All that aside, unless Manfred, Dipankar, or whomever can point out some other ordering constraint that I have missed, this one is messy enough that an additional explicit memory barrier might be in order.

Manfred? Dipankar?

Quoted 5 lines

Thanks,
James Huang

Quoted 119 lines

----- Original Message ----
From: Paul E. McKenney <[email protected]>
To: James Huang <[email protected]>
Cc: [email protected]; [email protected]; [email protected]
Sent: Wednesday, November 21, 2007 8:54:15 AM
Subject: Re: __rcu_process_callbacks() in Linux 2.6

Quoted 111 lines · James Huang

Please disregard the previous email.

In the latest Linux 2.6 RCU implementation, __rcu_process_callbacks() is coded as follows:

422 static void __rcu_process_callbacks(struct rcu_ctrlblk *rcp,
423 struct rcu_data *rdp)
424 {
425 if (rdp->curlist && !rcu_batch_before(rcp->completed, rdp->batch)) {

426                *rdp->donetail = rdp->curlist;
427                rdp->donetail = rdp->curtail;
428                rdp->curlist = NULL;
429                rdp->curtail = &rdp->curlist;
430        }
431 
432        if (rdp->nxtlist && !rdp->curlist) {
433                local_irq_disable();
434                rdp->curlist = rdp->nxtlist;
435                rdp->curtail = rdp->nxttail;
436                rdp->nxtlist = NULL;
437                rdp->nxttail = &rdp->nxtlist;
438                local_irq_enable();

439
440 /*
441 * start the next batch of callbacks
442 */
443

444                /* determine batch number */
445                rdp->batch = rcp->cur + 1;
446                /* see the comment and corresponding wmb() in

447 * the rcu_start_batch()
448 */
449 smp_rmb();
450
451 if (!rcp->next_pending) {

452                        /* and start it/schedule start if it's a new batch */
453                        spin_lock(&rcp->lock);
454                        rcp->next_pending = 1;
455                        rcu_start_batch(rcp);
456                        spin_unlock(&rcp->lock);

457 }
458 }
459
460 rcu_check_quiescent_state(rcp, rdp);
461 if (rdp->donelist)
462 rcu_do_batch(rdp);
463 }

The question is how does the update of rdp->batch at line 445 guarantee to observe the most updated value of rcp->cur?? The issue is that there is no memory barrier/locking before line 445.
So I think the following sequence of events in chronological order is possible:

Assume initially rcp->cur = 100, this current batch value is visible to every CPU, and batch 100 has completed
(i.e. rcp->completed = 100, rcp->next_pending = 0, rcp->cpumask = 0, and for each CPU, rdp->quiescbatch = 100, rdp->qs_pending = 0, rdp->passed_quiesc = 1)

CPU 0:
---------

             call_rcu(): a callback inserted into rdp->nxtlist;                    

             timer interrupt 
               call rcu_pending(), return true  ( ! rdp->curlist && rdp->nxtlist)
               call rcu_check_callbacks() 
                     schedule per CPU rcu_tasklet

               __rcu_process_callbacks()
                           move callbacks from nxtlist to curlist;
                           rdp->batch = 101
                           lock rcp->lock
                           rcp->next_pending = 1
                           call rcu_start_batch()
                                 find the current batch has completed and next batch pending;
                                 rcp->next_pending = 0
                                 update rcp->cur to 101 and initialize rcp->cpumask;                  <----- time t1
                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                           unlock rcp->lock

CPU 1:
---------

             timer interrupt 
                 call rcu_pending(), return true (asume observing rcp->cur = 101 != rdp->quiescbatch) 
                 
                 call rcu_check_callbacks() 
                       schedule per CPU rcu_tasklet

                 __rcu_process_callbacks()
                       call rcu_check_quisecent_state()
                             find rdp->quiescbatch != rcp->cur
                             set rdp->qs_pending = 1
                             set rdp->passed_quiesc = 0
                             set rdp->quiescbatch = 101 (rcp->cur)

             Another timer interrupt
                 call rcu_pending(), return true (rdp->qs_pending == 1)  
                 call rcu_check_callbacks() 
                       (assume in user mode)                        <-- time t2  pass quiescent state
                       ~~~~~~~~~~~~~~~~~~                            ~~~~~~~~~~~~~~~~~~~~~~
                       rdp->passed_quiesc = 1
                       schedule per CPU rcu_tasklet
           
                 __rcu_process_callbacks()
                       call rcu_check_quisecent_state()
                             find rdp->qs_pending == 1 && rdp-> passed_quiesc == 1
                             set rdp->qs_pending = 0
                             lock rcp->lock
                             call cpu_quite()
                                   clear bit in the rcp->cpumask set up by CPU 0 at time t1
                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                             unlock rcp->lock
		rcu_read_lock();
		p = rcu_dereference(RCU_protected_pointer);
		/* A */
		/* do something time-consuming with p */
		rcu_read_unlock();
Quoted 3 lines
Quoted 3 lines

CPU 2:
---------

		q1 = kmalloc(...);
		initialize_it(q1);
		q = RCU_protected_pointer;
		/* B */
		rcu_assign_pointer(RCU_protected_pointer, q1);
Quoted 15 lines
Quoted 7 lines
             call_rcu(): a callback inserted into rdp->nxtlist;    <--- time t3
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             
             timer interrupt 
                 call rcu_pending(), return true ( ! rdp->curlist && rdp->nxtlist)
                 call rcu_check_callbacks() 
                     schedule per CPU rcu_tasklet

The tasklet_schedule() code calls test_and_set_bit(), which is an atomic operation that returns a value. It therefore implies a memory barrier, so that if the prior call_rcu() at time t3 "happens after" CPU 1's quiescent state at time t2 (which, due to locking, must follow the update to rcp->cur at time t1), then the access to rcp->cur at time t4 must see the new value of rcp->cur.

Quoted 16 lines

This is admittedly a bit subtle and perhaps a bit fragile. Manfred, Dipankar, would it be worth putting an explicit memory barrier somewhere in this sequence, or is there another memory barrier that I forgetting?

Thanx, Paul

Quoted 10 lines
                 calls __rcu_process_callbacks()
                     move callbacks from nxtlist to curlist; (including the callback inserted at time t3)
                     rdp->batch = rcp->cur + 1;                        <--- time t4
                     ~~~~~~~~~~~~~~~~~~~~

At time t4, CPU 2 might observe rcp->cpu as 100 and set rdp->batch to 101.
So CPU 2 essentially started its batch 101 (includes a callback inserted at time t3) after CPU 1 passed its quiescent state (at time t2) for batch 101.

Isn't this an issue??? Am I missing something?
Thanks for pointing me to the right direction.

Thanx, Paul