Skip to contentSkip to conversation

__rcu_process_callbacks() in Linux 2.6

DISCUSSION James Huang 2 participants 5 messages Nov 26, 2007 – Nov 28, 2007 1 message not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw
Quoted 18 lines

-----Original Message-----
From: James Huang [mailto:[email protected]]
Sent: Monday, November 26, 2007 2:21 PM
To: James Huang
Subject: Fw: __rcu_process_callbacks() in Linux 2.6

----- Forwarded Message ----
From: Manfred Spraul <[email protected]>
To: James Huang <[email protected]>
Cc: Paul E. McKenney <[email protected]>; linux- [email protected]
Sent: Monday, November 26, 2007 10:28:37 AM
Subject: __rcu_process_callbacks() in Linux 2.6

Hi James,

Quoted 8 lines

If I understand the issue correctly, then the race is:

step 1: cpu 1: starts a new rcu batch (i.e. rcp->cur++, smb_mb)

step 2: cpu 2: completes the quiet state
step 3: cpu 2: reads pointer 0x123 (ptr to a rcu protected struct)

step 4: cpu 3: call_rcu(0x123): rcu protected struct added to

rdp->nxtlist

Quoted 8 lines

step 5: cpu 3: moves a new batch into rdp->curlist, rdp->batch = rcp-

Quoted 1 line

cur+1.

xxxxxxxxxxxxxxx Problem: where is the smp_rmb() that guarantees that xxxxxxxxxxxxxxx update to rcp->cur from step 1 is seen by cpu 3? step 6: cpu 3: completes quiet state
step 7: cpu 3: struct 0x123 destroyed

step 8: cpu 2: accesses pointer 0x123, but the struct is already

destroyed

Quoted 2 lines

James: Is that the race?

[James Huang]

Yes, this is the race condition that I am concerned about.

Quoted 2 lines

I agree with Paul, there are smb_rmb's on cpu 3 between Step 1 and

Step 5:

Quoted 8 lines

Either the test_and_set_bit in tasklet_action for rcu_process_callback if step 4 happens before the tasklet or somewhere in the irq handler path if step 4 happens in an irq handler that interrupted rcu_process_callback.

Thus theoretically no additional smb_rmb() should be necessary. What is missing is proper documentation.

[James Huang]

Is it true that a smb_rmb() before a read operation (say from variable
X) will guarantee that the read will always retrieve the most "current"
value of X? I can not find such a guarantee in atomic_ops.txt or
memory-barriers.txt under Linux's documentation directory. What is described in both documents is relative ordering, e.g.

            CPU1                       CPU2
           ------                     ------
          write X = x1
          smp_wmb()  
          write Y = y1 

                                      read Y
                                      smp_rmb()
                                      read X

Then CPU2 will read X with a value of x1 if it reads Y with a value of y1.

Please point me to the right section in the document if smp_rmb() does provide such a guarantee.

Thanks,
-- James Huang

Quoted 2 lines

I'm analyzing the code right now:
Is it really true that typically a cpu only completes data in every

other

Quoted 2 lines

rcu
cycle? I.e. that most structures are stored in the rcu callback list

until

Quoted 17 lines

two
quiet states happened?

I've tried to track the values of rcp->cur and rdp->batch. If next_pending is set, then cpu_quiet() immetiately starts the next rcu cycle and a cpu cannot both complete the currently pending rcu callbacks and add new callbacks to the next cycle, thus a cpu only takes part in every other rcu cycle.

The oocalc file is at
http://www.colorfullife.com/~manfred/rcu.ods
http://www.colorfullife.com/~manfred/rcu.pdf

Is that analysis correct? Perhaps the whole code should be rewritten?

--
Manfred

#2 lore raw
Quoted 75 lines · James Huang
Quoted 17 lines

-----Original Message-----
From: James Huang [mailto:[email protected]]
Sent: Monday, November 26, 2007 2:21 PM
To: James Huang
Subject: Fw: __rcu_process_callbacks() in Linux 2.6

----- Forwarded Message ----
From: Manfred Spraul <[email protected]>
To: James Huang <[email protected]>
Cc: Paul E. McKenney <[email protected]>; linux- [email protected]
Sent: Monday, November 26, 2007 10:28:37 AM
Subject: __rcu_process_callbacks() in Linux 2.6

Hi James,

Quoted 8 lines

If I understand the issue correctly, then the race is:

step 1: cpu 1: starts a new rcu batch (i.e. rcp->cur++, smb_mb)

step 2: cpu 2: completes the quiet state
step 3: cpu 2: reads pointer 0x123 (ptr to a rcu protected struct)

step 4: cpu 3: call_rcu(0x123): rcu protected struct added to

rdp->nxtlist

Quoted 8 lines

step 5: cpu 3: moves a new batch into rdp->curlist, rdp->batch = rcp-

Quoted 1 line

cur+1.

xxxxxxxxxxxxxxx Problem: where is the smp_rmb() that guarantees that xxxxxxxxxxxxxxx update to rcp->cur from step 1 is seen by cpu 3? step 6: cpu 3: completes quiet state
step 7: cpu 3: struct 0x123 destroyed

step 8: cpu 2: accesses pointer 0x123, but the struct is already

destroyed

Quoted 2 lines

James: Is that the race?

[James Huang]

Yes, this is the race condition that I am concerned about.

Quoted 2 lines

I agree with Paul, there are smb_rmb's on cpu 3 between Step 1 and

Step 5:

Quoted 8 lines

Either the test_and_set_bit in tasklet_action for rcu_process_callback if step 4 happens before the tasklet or somewhere in the irq handler path if step 4 happens in an irq handler that interrupted rcu_process_callback.

Thus theoretically no additional smb_rmb() should be necessary. What is missing is proper documentation.

[James Huang]

Is it true that a smb_rmb() before a read operation (say from variable
X) will guarantee that the read will always retrieve the most "current"
value of X? I can not find such a guarantee in atomic_ops.txt or
memory-barriers.txt under Linux's documentation directory. What is described in both documents is relative ordering, e.g.

            CPU1                       CPU2
           ------                     ------
          write X = x1
          smp_wmb()  
          write Y = y1 

                                      read Y
                                      smp_rmb()
                                      read X
Quoted 5 lines

Then CPU2 will read X with a value of x1 if it reads Y with a value of y1.

Please point me to the right section in the document if smp_rmb() does provide such a guarantee.

You are correct, smp_rmb() is about ordering rather than about any sort of immediacy. For one thing, it can be quite difficult to say exactly what the most "current" version of X might be at a given point in time from the viewpoint of a given CPU -- the different CPUs might well disagree as to what the "current" version is for awhile (though they are guaranteed to come to agreement).

Quoted 11 lines

Thanks,
-- James Huang

Quoted 2 lines

I'm analyzing the code right now:
Is it really true that typically a cpu only completes data in every

other

Quoted 2 lines

rcu
cycle? I.e. that most structures are stored in the rcu callback list

until

Quoted 2 lines

two
quiet states happened?

That is correct. This does mean that we should be able to leverage locking primitives and memory barriers executed from the scheduling clock interrupt.

Quoted 11 lines
Quoted 11 lines

I've tried to track the values of rcp->cur and rdp->batch. If next_pending is set, then cpu_quiet() immetiately starts the next rcu cycle and a cpu cannot both complete the currently pending rcu callbacks and add new callbacks to the next cycle, thus a cpu only takes part in every other rcu cycle.

The oocalc file is at
http://www.colorfullife.com/~manfred/rcu.ods
http://www.colorfullife.com/~manfred/rcu.pdf

Is that analysis correct? Perhaps the whole code should be rewritten?

I believe that the sequencing in spreadsheet is correct (and thank you very much for going through it!!!), but it seems to be silent on memory-barrier issues.

I also believe that Gautham's new CPU-hotplug setup will make it possible to simplify the code quite a bit. And given that the grace-period-detection code is not on any sort of hot code path, it should be possible to use a less-aggressive design, perhaps one using straight locking to guard the shared structures. Also, we are working in the -rt implementation on a scheme that allows CPUs to stay asleep through a grace period without the heavy overhead that is otherwise required to interact with them. The trick is to maintain a per-CPU counter that is incremented on each entry and exit to low-power state. But I would like to get this right in -rt before trying it in Classic RCU. ;-)

Thanx, Paul

#3 lore raw
Quoted 97 lines · Paul E. McKenney
Quoted 75 lines · James Huang
Quoted 17 lines

-----Original Message-----
From: James Huang [mailto:[email protected]]
Sent: Monday, November 26, 2007 2:21 PM
To: James Huang
Subject: Fw: __rcu_process_callbacks() in Linux 2.6

----- Forwarded Message ----
From: Manfred Spraul <[email protected]>
To: James Huang <[email protected]>
Cc: Paul E. McKenney <[email protected]>; linux- [email protected]
Sent: Monday, November 26, 2007 10:28:37 AM
Subject: __rcu_process_callbacks() in Linux 2.6

Hi James,

Quoted 8 lines

If I understand the issue correctly, then the race is:

step 1: cpu 1: starts a new rcu batch (i.e. rcp->cur++, smb_mb)

step 2: cpu 2: completes the quiet state
step 3: cpu 2: reads pointer 0x123 (ptr to a rcu protected struct)

step 4: cpu 3: call_rcu(0x123): rcu protected struct added to

rdp->nxtlist

Quoted 8 lines

step 5: cpu 3: moves a new batch into rdp->curlist, rdp->batch = rcp-

Quoted 1 line

cur+1.

xxxxxxxxxxxxxxx Problem: where is the smp_rmb() that guarantees that xxxxxxxxxxxxxxx update to rcp->cur from step 1 is seen by cpu 3? step 6: cpu 3: completes quiet state
step 7: cpu 3: struct 0x123 destroyed

step 8: cpu 2: accesses pointer 0x123, but the struct is already

destroyed

Quoted 2 lines

James: Is that the race?

[James Huang]

Yes, this is the race condition that I am concerned about.

Quoted 2 lines

I agree with Paul, there are smb_rmb's on cpu 3 between Step 1 and

Step 5:

Quoted 8 lines

Either the test_and_set_bit in tasklet_action for rcu_process_callback if step 4 happens before the tasklet or somewhere in the irq handler path if step 4 happens in an irq handler that interrupted rcu_process_callback.

Thus theoretically no additional smb_rmb() should be necessary. What is missing is proper documentation.

[James Huang]

Is it true that a smb_rmb() before a read operation (say from variable
X) will guarantee that the read will always retrieve the most "current"
value of X? I can not find such a guarantee in atomic_ops.txt or
memory-barriers.txt under Linux's documentation directory. What is described in both documents is relative ordering, e.g.

            CPU1                       CPU2
           ------                     ------
          write X = x1
          smp_wmb()  
          write Y = y1 

                                      read Y
                                      smp_rmb()
                                      read X
Quoted 5 lines

Then CPU2 will read X with a value of x1 if it reads Y with a value of y1.

Please point me to the right section in the document if smp_rmb() does provide such a guarantee.

You are correct, smp_rmb() is about ordering rather than about any sort of immediacy. For one thing, it can be quite difficult to say exactly what the most "current" version of X might be at a given point in time from the viewpoint of a given CPU -- the different CPUs might well disagree as to what the "current" version is for awhile (though they are guaranteed to come to agreement).

Quoted 8 lines

Thanks,
-- James Huang

Quoted 2 lines

I'm analyzing the code right now:
Is it really true that typically a cpu only completes data in every

other

Quoted 2 lines

rcu
cycle? I.e. that most structures are stored in the rcu callback list

Quoted 7 lines
Quoted 3 lines

until

Quoted 2 lines

two
quiet states happened?

That is correct. This does mean that we should be able to leverage locking primitives and memory barriers executed from the scheduling clock interrupt.

And I managed to get some time on a 64-CPU POWER5+ system. Been running rcutorture for about 2.5 hours without a failure (128 reader processes) running through not quite 1.5M RCU updates. Of course, this is not proof that the Classic RCU implementation works, but is should provide some reassurance.

I will keep it running until I get kicked off (probably rather soon).

Thanx, Paul

Quoted 28 lines
Quoted 11 lines
Quoted 11 lines

I've tried to track the values of rcp->cur and rdp->batch. If next_pending is set, then cpu_quiet() immetiately starts the next rcu cycle and a cpu cannot both complete the currently pending rcu callbacks and add new callbacks to the next cycle, thus a cpu only takes part in every other rcu cycle.

The oocalc file is at
http://www.colorfullife.com/~manfred/rcu.ods
http://www.colorfullife.com/~manfred/rcu.pdf

Is that analysis correct? Perhaps the whole code should be rewritten?

I believe that the sequencing in spreadsheet is correct (and thank you very much for going through it!!!), but it seems to be silent on memory-barrier issues.

I also believe that Gautham's new CPU-hotplug setup will make it possible to simplify the code quite a bit. And given that the grace-period-detection code is not on any sort of hot code path, it should be possible to use a less-aggressive design, perhaps one using straight locking to guard the shared structures. Also, we are working in the -rt implementation on a scheme that allows CPUs to stay asleep through a grace period without the heavy overhead that is otherwise required to interact with them. The trick is to maintain a per-CPU counter that is incremented on each entry and exit to low-power state. But I would like to get this right in -rt before trying it in Classic RCU. ;-)

Thanx, Paul

#4 lore raw
Quoted 104 lines · Paul E. McKenney
Quoted 95 lines · Paul E. McKenney
Quoted 73 lines · James Huang
Quoted 15 lines

From: James Huang [mailto:[email protected]]
Sent: Monday, November 26, 2007 2:21 PM
To: James Huang
Subject: Fw: __rcu_process_callbacks() in Linux 2.6

----- Forwarded Message ----
From: Manfred Spraul <[email protected]>
To: James Huang <[email protected]>
Cc: Paul E. McKenney <[email protected]>; linux- [email protected]
Sent: Monday, November 26, 2007 10:28:37 AM
Subject: __rcu_process_callbacks() in Linux 2.6

Hi James,

Quoted 8 lines

If I understand the issue correctly, then the race is:

step 1: cpu 1: starts a new rcu batch (i.e. rcp->cur++, smb_mb)

step 2: cpu 2: completes the quiet state
step 3: cpu 2: reads pointer 0x123 (ptr to a rcu protected struct)

step 4: cpu 3: call_rcu(0x123): rcu protected struct added to

rdp->nxtlist

Quoted 8 lines

step 5: cpu 3: moves a new batch into rdp->curlist, rdp->batch = rcp-

Quoted 1 line

cur+1.

xxxxxxxxxxxxxxx Problem: where is the smp_rmb() that guarantees that xxxxxxxxxxxxxxx update to rcp->cur from step 1 is seen by cpu 3? step 6: cpu 3: completes quiet state
step 7: cpu 3: struct 0x123 destroyed

step 8: cpu 2: accesses pointer 0x123, but the struct is already

destroyed

Quoted 2 lines

James: Is that the race?

[James Huang]

Yes, this is the race condition that I am concerned about.

Quoted 2 lines

I agree with Paul, there are smb_rmb's on cpu 3 between Step 1 and

Step 5:

Quoted 8 lines

Either the test_and_set_bit in tasklet_action for rcu_process_callback if step 4 happens before the tasklet or somewhere in the irq handler path if step 4 happens in an irq handler that interrupted rcu_process_callback.

Thus theoretically no additional smb_rmb() should be necessary. What is missing is proper documentation.

[James Huang]

Is it true that a smb_rmb() before a read operation (say from variable
X) will guarantee that the read will always retrieve the most "current"
value of X? I can not find such a guarantee in atomic_ops.txt or
memory-barriers.txt under Linux's documentation directory. What is described in both documents is relative ordering, e.g.

            CPU1                       CPU2
           ------                     ------
          write X = x1
          smp_wmb()  
          write Y = y1 

                                      read Y
                                      smp_rmb()
                                      read X
Quoted 5 lines

Then CPU2 will read X with a value of x1 if it reads Y with a value of y1.

Please point me to the right section in the document if smp_rmb() does provide such a guarantee.

You are correct, smp_rmb() is about ordering rather than about any sort of immediacy. For one thing, it can be quite difficult to say exactly what the most "current" version of X might be at a given point in time from the viewpoint of a given CPU -- the different CPUs might well disagree as to what the "current" version is for awhile (though they are guaranteed to come to agreement).

Quoted 8 lines

Thanks,
-- James Huang

Quoted 2 lines

I'm analyzing the code right now:
Is it really true that typically a cpu only completes data in every

other

Quoted 2 lines

rcu
cycle? I.e. that most structures are stored in the rcu callback list

Quoted 7 lines
Quoted 3 lines

until

Quoted 2 lines

two
quiet states happened?

That is correct. This does mean that we should be able to leverage locking primitives and memory barriers executed from the scheduling clock interrupt.

Quoted 7 lines

And I managed to get some time on a 64-CPU POWER5+ system. Been running rcutorture for about 2.5 hours without a failure (128 reader processes) running through not quite 1.5M RCU updates. Of course, this is not proof that the Classic RCU implementation works, but is should provide some reassurance.

I will keep it running until I get kicked off (probably rather soon).

More than seven hours, more than 4M RCU updates without failure. Someone else's turn for the machine.

Again, not proof, but at least some reassurance.

Thanx, Paul

Quoted 29 lines
Quoted 29 lines
Quoted 7 lines
Quoted 7 lines

I've tried to track the values of rcp->cur and rdp->batch. If next_pending is set, then cpu_quiet() immetiately starts the next rcu cycle and a cpu cannot both complete the currently pending rcu callbacks and add new callbacks to the next cycle, thus a cpu only takes part in every other rcu cycle.

Quoted 5 lines
Quoted 5 lines

The oocalc file is at
http://www.colorfullife.com/~manfred/rcu.ods
http://www.colorfullife.com/~manfred/rcu.pdf

Is that analysis correct? Perhaps the whole code should be rewritten?

I believe that the sequencing in spreadsheet is correct (and thank you very much for going through it!!!), but it seems to be silent on memory-barrier issues.

I also believe that Gautham's new CPU-hotplug setup will make it possible to simplify the code quite a bit. And given that the grace-period-detection code is not on any sort of hot code path, it should be possible to use a less-aggressive design, perhaps one using straight locking to guard the shared structures. Also, we are working in the -rt implementation on a scheme that allows CPUs to stay asleep through a grace period without the heavy overhead that is otherwise required to interact with them. The trick is to maintain a per-CPU counter that is incremented on each entry and exit to low-power state. But I would like to get this right in -rt before trying it in Classic RCU. ;-)

Thanx, Paul

#5 lore raw
Quoted 3 lines · Paul E. McKenney
Quoted 2 lines · Paul E. McKenney
Quoted 1 line · Paul E. McKenney

On Mon, Nov 26, 2007 at 02:48:08PM -0800, James Huang wrote:

[ . . . ]

Quoted 10 lines
Quoted 10 lines
Quoted 3 lines

That is correct. This does mean that we should be able to leverage locking primitives and memory barriers executed from the scheduling clock interrupt.

And I managed to get some time on a 64-CPU POWER5+ system. Been running rcutorture for about 2.5 hours without a failure (128 reader processes) running through not quite 1.5M RCU updates. Of course, this is not proof that the Classic RCU implementation works, but is should provide some reassurance.

Quoted 6 lines
Quoted 1 line

I will keep it running until I get kicked off (probably rather soon).

More than seven hours, more than 4M RCU updates without failure. Someone else's turn for the machine.

Again, not proof, but at least some reassurance.

Just to avoid potential misunderstanding... This testing in no way changes my opinion that the RCU Classic implementation needs some combination of documentation and rework. It pretty clearly needs a bit of both. And the increase in core counts over the past few years indicates that some scalability work is in order.

What this testing does demonstrate is that we are not in an emergency situation.

Thanx, Paul