__rcu_process_callbacks() in Linux 2.6
A message that is not in the archive (sent off-list or not yet received): [email protected]
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.6Hi 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 pointer0x123(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 torcp->curfrom step 1 is seen by cpu 3? step 6: cpu 3: completes quiet state
step 7: cpu 3: struct0x123destroyedstep 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_bitintasklet_actionforrcu_process_callbackif step 4 happens before the tasklet or somewhere in the irq handler path if step 4 happens in an irq handler that interruptedrcu_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 XThen 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->curandrdp->batch. Ifnext_pendingis set, thencpu_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.pdfIs that analysis correct? Perhaps the whole code should be rewritten?
--
Manfred
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.6Hi 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 pointer0x123(ptr to a rcu protected struct)step 4: cpu 3:
call_rcu(0x123): rcu protected struct added to
rdp->nxtlistQuoted 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 torcp->curfrom step 1 is seen by cpu 3? step 6: cpu 3: completes quiet state
step 7: cpu 3: struct0x123destroyedstep 8: cpu 2: accesses pointer
0x123, but the struct is alreadydestroyed
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_bitintasklet_actionforrcu_process_callbackif step 4 happens before the tasklet or somewhere in the irq handler path if step 4 happens in an irq handler that interruptedrcu_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 HuangQuoted 2 lines
I'm analyzing the code right now:
Is it really true that typically a cpu only completes data in everyother
Quoted 2 lines
rcu
cycle? I.e. that most structures are stored in the rcu callback listuntil
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->curandrdp->batch. Ifnext_pendingis set, thencpu_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.pdfIs 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
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.6Hi 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 pointer0x123(ptr to a rcu protected struct)step 4: cpu 3:
call_rcu(0x123): rcu protected struct added to
rdp->nxtlistQuoted 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 torcp->curfrom step 1 is seen by cpu 3? step 6: cpu 3: completes quiet state
step 7: cpu 3: struct0x123destroyedstep 8: cpu 2: accesses pointer
0x123, but the struct is alreadydestroyed
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_bitintasklet_actionforrcu_process_callbackif step 4 happens before the tasklet or somewhere in the irq handler path if step 4 happens in an irq handler that interruptedrcu_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 XQuoted 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 HuangQuoted 2 lines
I'm analyzing the code right now:
Is it really true that typically a cpu only completes data in everyother
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->curandrdp->batch. Ifnext_pendingis set, thencpu_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.pdfIs 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
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.6Hi 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 pointer0x123(ptr to a rcu protected struct)step 4: cpu 3:
call_rcu(0x123): rcu protected struct added to
rdp->nxtlistQuoted 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 torcp->curfrom step 1 is seen by cpu 3? step 6: cpu 3: completes quiet state
step 7: cpu 3: struct0x123destroyedstep 8: cpu 2: accesses pointer
0x123, but the struct is alreadydestroyed
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_bitintasklet_actionforrcu_process_callbackif step 4 happens before the tasklet or somewhere in the irq handler path if step 4 happens in an irq handler that interruptedrcu_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 XQuoted 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 HuangQuoted 2 lines
I'm analyzing the code right now:
Is it really true that typically a cpu only completes data in everyother
Quoted 2 lines
rcu
cycle? I.e. that most structures are stored in the rcu callback listQuoted 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->curandrdp->batch. Ifnext_pendingis set, thencpu_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.pdfIs 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
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