kernel/rcu/tree.c: correct a check for grace period in progress
RFC PATCH 1/1 kernel/rcu/tree.c: correct a check for grace period in progress
The comment above the code says that we are checking both the current node and the parent node to see if a grace period is in progress. Change the code accordingly.
--- kernel/rcu/tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/rcu/tree.c +1 -1
@@ -1227,7 +1227,7 @@ rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp,* need to explicitly start one. */ if (rnp->gpnum != rnp->completed || -ACCESS_ONCE (rnp->gpnum) !=ACCESS_ONCE (rnp->completed)) { +ACCESS_ONCE (rnp_root->gpnum) !=ACCESS_ONCE (rnp_root->completed)) { rnp->need_future_gp[c &0x1 ]++;trace_rcu_future_gp (rnp, rdp, c,TPS ("Startedleaf" )); goto out;
Signature · 1 line
1.9.1
Quoted 3 lines · Pranith Kumar
The comment above the code says that we are checking both the current node and the parent node to see if a grace period is in progress. Change the code accordingly.
Almost... Please see below.
Thanx, Paul
Quoted 10 lines
Signed-off-by Pranith Kumar <[email protected]>--- kernel/rcu/tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)kernel/rcu/tree.c +0
-0
kernel/rcu/tree.c rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1230
Quoted 5 lines
kernel/rcu/tree.c +1
-1@@ -1227,7 +1227,7 @@ rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp,* need to explicitly start one. */ if (rnp->gpnum != rnp->completed || -ACCESS_ONCE (rnp->gpnum) !=ACCESS_ONCE (rnp->completed)) { +ACCESS_ONCE (rnp_root->gpnum) !=ACCESS_ONCE (rnp_root->completed)) {
At this point in the code, we are checking the current rcu_node structure, which might or might not be the root. If it is not the root, we absolutely cannot compare against the root because we don't yet hold the root's lock.
So I cannot take this change.
That said, I do heartily encourage you to keep looking. After all, there are bound to be at least a few bugs in RCU somewhere.
Quoted 3 lines
kernel/rcu/tree.c +0
-0rnp->need_future_gp[c &0x1 ]++;trace_rcu_future_gp (rnp, rdp, c,TPS ("Startedleaf" )); goto out;
Hi Paul,
Quoted 8 lines · Paul E. McKenney
kernel/rcu/tree.c rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1230
Quoted 3 lines
if (rnp->gpnum != rnp->completed ||kernel/rcu/tree.c +1
-1- ACCESS_ONCE(rnp->gpnum) != ACCESS_ONCE(rnp->completed)) { + ACCESS_ONCE(rnp_root->gpnum) != ACCESS_ONCE(rnp_root->completed)) {At this point in the code, we are checking the current
rcu_nodestructure, which might or might not be the root. If it is not the root, we absolutely cannot compare against the root because we don't yet hold the root's lock.
I was a bit thrown by the double checking which is being done (rnp->gpnum != rnp->complete) in that if condition. Once without ACCESS_ONCE and one with. Is there any particular reason for this?
I now understand that we are comparing ->gpnum and ->completed of the root node which might change from under us if we don't hold the root's lock. I will keep looking :)
Thanks!
Signature · 1 line
Pranith
Quoted 13 lines · Pranith Kumar
Hi Paul,
Quoted 8 lines · Paul E. McKenney
kernel/rcu/tree.c rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1230
Quoted 3 lines
if (rnp->gpnum != rnp->completed ||kernel/rcu/tree.c +1
-1- ACCESS_ONCE(rnp->gpnum) != ACCESS_ONCE(rnp->completed)) { + ACCESS_ONCE(rnp_root->gpnum) != ACCESS_ONCE(rnp_root->completed)) {At this point in the code, we are checking the current
rcu_nodestructure, which might or might not be the root. If it is not the root, we absolutely cannot compare against the root because we don't yet hold the root's lock.
Quoted 7 lines
I was a bit thrown by the double checking which is being done (
rnp->gpnum!=rnp->complete) in that if condition. Once withoutACCESS_ONCEand one with. Is there any particular reason for this?I now understand that we are comparing ->gpnum and ->completed of the root node which might change from under us if we don't hold the root's lock. I will keep looking :)
Hmmm... Now that you mention it, that does look a bit strange.
Thanx, Paul
Quoted 18 lines · Paul E. McKenney
Quoted 17 lines · Pranith Kumar
Hi Paul,
Quoted 8 lines · Paul E. McKenney
Review
Quoted 3 lines
if (rnp->gpnum != rnp->completed ||(quoted diff) +1
-1- ACCESS_ONCE(rnp->gpnum) != ACCESS_ONCE(rnp->completed)) { + ACCESS_ONCE(rnp_root->gpnum) != ACCESS_ONCE(rnp_root->completed)) {At this point in the code, we are checking the current
rcu_nodestructure, which might or might not be the root. If it is not the root, we absolutely cannot compare against the root because we don't yet hold the root's lock.I was a bit thrown by the double checking which is being done (
rnp->gpnum!=rnp->complete) in that if condition. Once withoutACCESS_ONCEand one with. Is there any particular reason for this?
Quoted 5 lines
Quoted 3 lines
I now understand that we are comparing ->gpnum and ->completed of the root node which might change from under us if we don't hold the root's lock. I will keep looking :)
Hmmm... Now that you mention it, that does look a bit strange.
And it turns out that you were right to begin with! I queue your change, but with a full explanation in the commit log and with some additions to the comment. Please see below.
Thanx, Paul
------------------------------------------------------------------------
rcu: Check both root and current rcu_node when setting up future grace period
The rcu_start_future_gp() function checks the current rcu_node's ->gpnum and ->completed twice, once without ACCESS_ONCE() and once with it. Which is pointless because we hold that rcu_node's ->lock at that point. The intent was to check the current rcu_node structure and the root rcu_node structure, the latter locklessly with ACCESS_ONCE(). This commit therefore makes that change.
The reason that it is safe to locklessly check the root rcu_nodes's ->gpnum and ->completed fields is that we hold the current rcu_node's ->lock, which constrains the root rcu_node's ability to change its ->gpnum and ->completed fields. Of course, if there is a single rcu_node structure, then rnp_root==rnp, and holding the lock prevents all changes. If there is more than one rcu_node structure, then the code updates the fields in the following order:
1. Increment rnp_root->gpnum to start new grace period.
2. Increment rnp->gpnum to initialize the current rcu_node,
continuing initialization for the new grace period.
3. Increment rnp_root->completed to end the current grace period.
4. Increment rnp->completed to continue cleaning up after the
old grace period.
So there are four possible combinations of relative values of these four fields:
N N N N: RCU idle, new grace period must be initiated.
Although rnp_root->gpnum might be incremented immediately after we check, that will just result in unnecessary work. The grace period already started, and we try to start it.
N+1 N N N: RCU grace period just started. No further change is
possible because we hold rnp->lock, so the checks of rnp_root->gpnum and rnp_root->completed are stable. We know that our request for a future grace period will be seen during grace-period cleanup.
N+1 N N+1 N: RCU grace period is ongoing. Because rnp->gpnum is
different than rnp->completed, we won't even look at
rnp_root->gpnum and rnp_root->completed, so the possible
concurrent change to rnp_root->completed does not matter.
We know that our request for a future grace period will
be seen during grace-period cleanup, which cannot pass
this rcu_node because we hold its ->lock.N+1 N+1 N+1 N: RCU grace period has ended, but not yet been cleaned up.
Because rnp->gpnum is different than rnp->completed, we
won't look at rnp_root->gpnum and rnp_root->completed, so
the possible concurrent change to rnp_root->completed does
not matter. We know that our request for a future grace
period will be seen during grace-period cleanup, which
cannot pass this rcu_node because we hold its ->lock.Therefore, despite initial appearances, the lockless check is safe.
kernel/rcu/tree.c +8 -2
@@ -1224,10 +1224,16 @@ rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp,* believe that a grace period is in progress, then we must wait * for the one following, which is in "c". Because our request * will be noticed at the end of the current grace period, we don't -* need to explicitly start one. +* need to explicitly start one. We only do the lockless check +* of rnp_root's fields if the current rcu_node structure thinks +* there is no grace period in flight, and because we hold rnp->lock, +* the only possible change is when rnp_root's two fields are +* equal, in which case rnp_root->gpnum might be concurrently +* incremented. But that is OK, as it will just result in our +* doing some extra useless work. */ if (rnp->gpnum != rnp->completed || -ACCESS_ONCE (rnp->gpnum) !=ACCESS_ONCE (rnp->completed)) { +ACCESS_ONCE (rnp_root->gpnum) !=ACCESS_ONCE (rnp_root->completed)) { rnp->need_future_gp[c &0x1 ]++;trace_rcu_future_gp (rnp, rdp, c,TPS ("Startedleaf" )); goto out;
Quoted 23 lines · Paul E. McKenney
Quoted 22 lines · Paul E. McKenney
Quoted 20 lines · Pranith Kumar
Hi Paul,
Quoted 8 lines · Paul E. McKenney
kernel/rcu/tree.c rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1236
Quoted 3 lines
if (rnp->gpnum != rnp->completed ||kernel/rcu/tree.c +1
-1- ACCESS_ONCE(rnp->gpnum) != ACCESS_ONCE(rnp->completed)) { + ACCESS_ONCE(rnp_root->gpnum) != ACCESS_ONCE(rnp_root->completed)) {At this point in the code, we are checking the current
rcu_nodestructure, which might or might not be the root. If it is not the root, we absolutely cannot compare against the root because we don't yet hold the root's lock.I was a bit thrown by the double checking which is being done (
rnp->gpnum!=rnp->complete) in that if condition. Once withoutACCESS_ONCEand one with. Is there any particular reason for this?I now understand that we are comparing ->gpnum and ->completed of the root node which might change from under us if we don't hold the root's lock. I will keep looking :)
Quoted 6 lines
Quoted 1 line
Hmmm... Now that you mention it, that does look a bit strange.
And it turns out that you were right to begin with! I queue your change, but with a full explanation in the commit log and with some additions to the comment. Please see below.
Awesome! A few more patches on your way :)
--
Pranith