kernel/rcu/tree.c: simplify force_quiescent_state()

This might sound really naive, but please bear with me.

force_quiescent_state() used to do a lot of things in the past in addition to forcing a quiescent state. (In my reading of the mailing list I found state transitions for one).

Now according to the code, what is being done is multiple callers try to go up the hierarchy of nodes to see who reaches the root node. The caller reaching the root node wins and it acquires root node lock and it gets to set rsp->gp_flags!

At each level of the hierarchy we try to acquire fqslock. This is the only place which actually uses fqslock.

I guess this was being done to avoid the contention on fqslock, but all we are doing here is setting one flag. This way of acquiring locks might reduce contention if every update is trying to do some independent work, but here all we are doing is setting the same flag with same value.

We can also remove fqslock completely if we do not need this. Also using cmpxchg() to set the value of the flag looks like a good idea to avoid taking the root node lock. Thoughts?

Signed-off-by Pranith Kumar <[email protected]>

---
 kernel/rcu/tree.c | 35 +++++++++++++----------------------
 1 file changed, 13 insertions(+), 22 deletions(-)

kernel/rcu/tree.c +13 -22

index f1ba773..9a46f32 100644
@@ -2399,36 +2399,27 @@ static void force_qs_rnp(struct rcu_state *rsp,
 static void force_quiescent_state(struct rcu_state *rsp)
 {
 	unsigned long flags;
-	bool ret;
-	struct rcu_node *rnp;
-	struct rcu_node *rnp_old = NULL;
-
-	/* Funnel through hierarchy to reduce memory contention. */
-	rnp = per_cpu_ptr(rsp->rda, raw_smp_processor_id())->mynode;
-	for (; rnp != NULL; rnp = rnp->parent) {
-		ret = (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) ||
-		      !raw_spin_trylock(&rnp->fqslock);
-		if (rnp_old != NULL)
-			raw_spin_unlock(&rnp_old->fqslock);
-		if (ret) {
-			ACCESS_ONCE(rsp->n_force_qs_lh)++;
-			return;
-		}
-		rnp_old = rnp;
+	struct rcu_node *rnp_root = rcu_get_root(rsp);
+
+	/* early test to see if someone already forced a quiescent state
+	 */
+	if (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
+		ACCESS_ONCE(rsp->n_force_qs_lh)++;
+		return;  /* Someone beat us to it. */
 	}
-	/* rnp_old == rcu_get_root(rsp), rnp == NULL. */
 
 	/* Reached the root of the rcu_node tree, acquire lock. */
-	raw_spin_lock_irqsave(&rnp_old->lock, flags);
+	raw_spin_lock_irqsave(&rnp_root->lock, flags);
 	smp_mb__after_unlock_lock();
-	raw_spin_unlock(&rnp_old->fqslock);
 	if (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
 		ACCESS_ONCE(rsp->n_force_qs_lh)++;
-		raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
-		return;  /* Someone beat us to it. */
+		raw_spin_unlock_irqrestore(&rnp_root->lock, flags);
+		return;  /* Someone actually beat us to it. */
 	}
+
+	/* can we use cmpxchg instead of the above lock? */
 	ACCESS_ONCE(rsp->gp_flags) |= RCU_GP_FLAG_FQS;
-	raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
+	raw_spin_unlock_irqrestore(&rnp_root->lock, flags);
 	wake_up(&rsp->gp_wq);  /* Memory barrier implied by wake_up() path. */
 }
 

Signature · 1 line

1.9.1

Quoted 10 lines · Pranith Kumar

This might sound really naive, but please bear with me.

force_quiescent_state() used to do a lot of things in the past in addition to forcing a quiescent state. (In my reading of the mailing list I found state transitions for one).

Now according to the code, what is being done is multiple callers try to go up the hierarchy of nodes to see who reaches the root node. The caller reaching the root node wins and it acquires root node lock and it gets to set rsp->gp_flags!

Quoted 7 lines

At each level of the hierarchy we try to acquire fqslock. This is the only place which actually uses fqslock.

I guess this was being done to avoid the contention on fqslock, but all we are doing here is setting one flag. This way of acquiring locks might reduce contention if every update is trying to do some independent work, but here all we are doing is setting the same flag with same value.

Actually, to reduce contention on rnp_root->lock.

The trick is that the "losers" at each level of ->fqslock acquisition go away. The "winner" ends up doing the real work of setting RCU_GP_FLAG_FQS.

Quoted 3 lines

We can also remove fqslock completely if we do not need this. Also using cmpxchg() to set the value of the flag looks like a good idea to avoid taking the root node lock. Thoughts?

The ->fqslock funnel was needed to avoid lockups on large systems (many hundreds or even thousands of CPUs). Moving grace-period responsibilities from softirq to the grace-period kthreads might have reduced contention sufficienty to make the ->fqslock funnel unnecessary. However, given that I don't usually have access to such a large system, I will leave it, at least for the time being.

But you might be interested in thinking through what else would need to change in order to make cmpxchg() work. ;-)

Thanx, Paul

Quoted 60 lines

Signed-off-by Pranith Kumar <[email protected]>

---
 kernel/rcu/tree.c | 35 +++++++++++++----------------------
 1 file changed, 13 insertions(+), 22 deletions(-)

kernel/rcu/tree.c +13 -23

index f1ba773..9a46f32 100644
@@ -2399,36 +2399,27 @@ static void force_qs_rnp(struct rcu_state *rsp,
 static void force_quiescent_state(struct rcu_state *rsp)
 {
      unsigned long flags;
-     bool ret;
-     struct rcu_node *rnp;
-     struct rcu_node *rnp_old = NULL;
-
-     /* Funnel through hierarchy to reduce memory contention. */
-     rnp = per_cpu_ptr(rsp->rda, raw_smp_processor_id())->mynode;
-     for (; rnp != NULL; rnp = rnp->parent) {
-             ret = (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) ||
-                   !raw_spin_trylock(&rnp->fqslock);
-             if (rnp_old != NULL)
-                     raw_spin_unlock(&rnp_old->fqslock);
-             if (ret) {
-                     ACCESS_ONCE(rsp->n_force_qs_lh)++;
-                     return;
-             }
-             rnp_old = rnp;
+     struct rcu_node *rnp_root = rcu_get_root(rsp);
+
+     /* early test to see if someone already forced a quiescent state
+      */
+     if (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
+             ACCESS_ONCE(rsp->n_force_qs_lh)++;
+             return;  /* Someone beat us to it. */
      }
-     /* rnp_old == rcu_get_root(rsp), rnp == NULL. */
 
      /* Reached the root of the rcu_node tree, acquire lock. */
-     raw_spin_lock_irqsave(&rnp_old->lock, flags);
+     raw_spin_lock_irqsave(&rnp_root->lock, flags);
      smp_mb__after_unlock_lock();
-     raw_spin_unlock(&rnp_old->fqslock);
      if (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
              ACCESS_ONCE(rsp->n_force_qs_lh)++;
-             raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
-             return;  /* Someone beat us to it. */
+             raw_spin_unlock_irqrestore(&rnp_root->lock, flags);
+             return;  /* Someone actually beat us to it. */
      }
+
+     /* can we use cmpxchg instead of the above lock? */
      ACCESS_ONCE(rsp->gp_flags) |= RCU_GP_FLAG_FQS;
-     raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
+     raw_spin_unlock_irqrestore(&rnp_root->lock, flags);
      wake_up(&rsp->gp_wq);  /* Memory barrier implied by wake_up() path. */
 }
 
--

Quoted 2 lines

1.9.1

--
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/

Quoted 26 lines · Paul E. McKenney

Quoted 10 lines · Pranith Kumar

This might sound really naive, but please bear with me.

force_quiescent_state() used to do a lot of things in the past in addition to forcing a quiescent state. (In my reading of the mailing list I found state transitions for one).

Now according to the code, what is being done is multiple callers try to go up the hierarchy of nodes to see who reaches the root node. The caller reaching the root node wins and it acquires root node lock and it gets to set rsp->gp_flags!

Quoted 7 lines

At each level of the hierarchy we try to acquire fqslock. This is the only place which actually uses fqslock.

I guess this was being done to avoid the contention on fqslock, but all we are doing here is setting one flag. This way of acquiring locks might reduce contention if every update is trying to do some independent work, but here all we are doing is setting the same flag with same value.

Actually, to reduce contention on rnp_root->lock.

The trick is that the "losers" at each level of ->fqslock acquisition go away. The "winner" ends up doing the real work of setting RCU_GP_FLAG_FQS.

Quoted 3 lines

We can also remove fqslock completely if we do not need this. Also using cmpxchg() to set the value of the flag looks like a good idea to avoid taking the root node lock. Thoughts?

Quoted 6 lines

The ->fqslock funnel was needed to avoid lockups on large systems (many hundreds or even thousands of CPUs). Moving grace-period responsibilities from softirq to the grace-period kthreads might have reduced contention sufficienty to make the ->fqslock funnel unnecessary. However, given that I don't usually have access to such a large system, I will leave it, at least for the time being.

Sounds like a good case study for using the newly introduced MCS based locks(qspinlock.h).
Waiman, Peter?

Btw, is doing the following a bad idea? It reduces contention on rnp_root->lock using fqslock
which seems to be the lock which needs to be taken while forcing a quiescent state:

kernel/rcu/tree.c +0 -10

index f1ba773..f5a0e7e 100644
@@ -2401,34 +2401,24 @@ static void force_quiescent_state(struct rcu_state *rsp)
      unsigned long flags;
      bool ret;
      struct rcu_node *rnp;
-    struct rcu_node *rnp_old = NULL;
-
-    /* Funnel through hierarchy to reduce memory contention. */
-    rnp = per_cpu_ptr(rsp->rda, raw_smp_processor_id())->mynode;
-    for (; rnp != NULL; rnp = rnp->parent) {
-        ret = (ACCESS_ONCE(rsp->gp_flags)&  RCU_GP_FLAG_FQS) ||
-              !raw_spin_trylock(&rnp->fqslock);
-        if (rnp_old != NULL)
-            raw_spin_unlock(&rnp_old->fqslock);
-        if (ret) {

Quoted 28 lines · Paul E. McKenney

Quoted 10 lines · Pranith Kumar

This might sound really naive, but please bear with me.

force_quiescent_state() used to do a lot of things in the past in addition to forcing a quiescent state. (In my reading of the mailing list I found state transitions for one).

Now according to the code, what is being done is multiple callers try to go up the hierarchy of nodes to see who reaches the root node. The caller reaching the root node wins and it acquires root node lock and it gets to set rsp->gp_flags!

Quoted 7 lines

At each level of the hierarchy we try to acquire fqslock. This is the only place which actually uses fqslock.

I guess this was being done to avoid the contention on fqslock, but all we are doing here is setting one flag. This way of acquiring locks might reduce contention if every update is trying to do some independent work, but here all we are doing is setting the same flag with same value.

Actually, to reduce contention on rnp_root->lock.

The trick is that the "losers" at each level of ->fqslock acquisition go away. The "winner" ends up doing the real work of setting RCU_GP_FLAG_FQS.

Quoted 3 lines

We can also remove fqslock completely if we do not need this. Also using cmpxchg() to set the value of the flag looks like a good idea to avoid taking the root node lock. Thoughts?

Quoted 6 lines

The ->fqslock funnel was needed to avoid lockups on large systems (many hundreds or even thousands of CPUs). Moving grace-period responsibilities from softirq to the grace-period kthreads might have reduced contention sufficienty to make the ->fqslock funnel unnecessary. However, given that I don't usually have access to such a large system, I will leave it, at least for the time being.

Sounds like a good case study for using the newly introduced MCS based locks(qspinlock.h).
Waiman, Peter?

Btw, is doing the following a bad idea? It reduces contention on rnp_root->lock using fqslock
which seems to be the lock which needs to be taken while forcing a quiescent state:

kernel/rcu/tree.c +0 -7

index f1ba773..f5a0e7e 100644
@@ -2401,34 +2401,24 @@ static void force_quiescent_state(struct rcu_state *rsp)
     unsigned long flags;
     bool ret;
     struct rcu_node *rnp;
-    struct rcu_node *rnp_old = NULL;
-
-    /* Funnel through hierarchy to reduce memory contention. */
-    rnp = per_cpu_ptr(rsp->rda, raw_smp_processor_id())->mynode;
-    for (; rnp != NULL; rnp = rnp->parent) {
-        ret = (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) ||
-              !raw_spin_trylock(&rnp->fqslock);

kernel/rcu/tree.c +8 -7

+        ACCESS_ONCE(rsp->n_force_qs_lh)++;
+        return;  /* Someone is already trying to force */
     }
-    /* rnp_old == rcu_get_root(rsp), rnp == NULL. */
 
-    /* Reached the root of the rcu_node tree, acquire lock. */
-    raw_spin_lock_irqsave(&rnp_old->lock, flags);
-    smp_mb__after_unlock_lock();
-    raw_spin_unlock(&rnp_old->fqslock);
     if (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
         ACCESS_ONCE(rsp->n_force_qs_lh)++;
-        raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
+        raw_spin_unlock(rnp_root->fqslock);
         return;  /* Someone beat us to it. */
     }
+
+    /* Reached the root of the rcu_node tree, acquire lock. */
+    raw_spin_lock_irqsave(&rnp_root->lock, flags);
+    smp_mb__after_unlock_lock();
     ACCESS_ONCE(rsp->gp_flags) |= RCU_GP_FLAG_FQS;
-    raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
+    raw_spin_unlock_irqrestore(&rnp_root->lock, flags);
     wake_up(&rsp->gp_wq);  /* Memory barrier implied by wake_up() path. */
 }
 

Regards,
Romanov

Quoted 74 lines

But you might be interested in thinking through what else would need to change in order to make cmpxchg() work. ;-)

Thanx, Paul

Quoted 60 lines

Signed-off-by Pranith Kumar <[email protected]>

---
 kernel/rcu/tree.c | 35 +++++++++++++----------------------
 1 file changed, 13 insertions(+), 22 deletions(-)

kernel/rcu/tree.c +13 -23

index f1ba773..9a46f32 100644
@@ -2399,36 +2399,27 @@ static void force_qs_rnp(struct rcu_state *rsp,
 static void force_quiescent_state(struct rcu_state *rsp)
 {
      unsigned long flags;
-     bool ret;
-     struct rcu_node *rnp;
-     struct rcu_node *rnp_old = NULL;
-
-     /* Funnel through hierarchy to reduce memory contention. */
-     rnp = per_cpu_ptr(rsp->rda, raw_smp_processor_id())->mynode;
-     for (; rnp != NULL; rnp = rnp->parent) {
-             ret = (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) ||
-                   !raw_spin_trylock(&rnp->fqslock);
-             if (rnp_old != NULL)
-                     raw_spin_unlock(&rnp_old->fqslock);
-             if (ret) {
-                     ACCESS_ONCE(rsp->n_force_qs_lh)++;
-                     return;
-             }
-             rnp_old = rnp;
+     struct rcu_node *rnp_root = rcu_get_root(rsp);
+
+     /* early test to see if someone already forced a quiescent state
+      */
+     if (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
+             ACCESS_ONCE(rsp->n_force_qs_lh)++;
+             return;  /* Someone beat us to it. */
      }
-     /* rnp_old == rcu_get_root(rsp), rnp == NULL. */
 
      /* Reached the root of the rcu_node tree, acquire lock. */
-     raw_spin_lock_irqsave(&rnp_old->lock, flags);
+     raw_spin_lock_irqsave(&rnp_root->lock, flags);
      smp_mb__after_unlock_lock();
-     raw_spin_unlock(&rnp_old->fqslock);
      if (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
              ACCESS_ONCE(rsp->n_force_qs_lh)++;
-             raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
-             return;  /* Someone beat us to it. */
+             raw_spin_unlock_irqrestore(&rnp_root->lock, flags);
+             return;  /* Someone actually beat us to it. */
      }
+
+     /* can we use cmpxchg instead of the above lock? */
      ACCESS_ONCE(rsp->gp_flags) |= RCU_GP_FLAG_FQS;
-     raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
+     raw_spin_unlock_irqrestore(&rnp_root->lock, flags);
      wake_up(&rsp->gp_wq);  /* Memory barrier implied by wake_up() path. */
 }
 
--

Quoted 2 lines

1.9.1

--
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/

Quoted 34 lines · Romanov Arya

Quoted 26 lines · Paul E. McKenney

Quoted 10 lines · Pranith Kumar

This might sound really naive, but please bear with me.

force_quiescent_state() used to do a lot of things in the past in addition to forcing a quiescent state. (In my reading of the mailing list I found state transitions for one).

Now according to the code, what is being done is multiple callers try to go up the hierarchy of nodes to see who reaches the root node. The caller reaching the root node wins and it acquires root node lock and it gets to set rsp->gp_flags!

Quoted 7 lines

At each level of the hierarchy we try to acquire fqslock. This is the only place which actually uses fqslock.

I guess this was being done to avoid the contention on fqslock, but all we are doing here is setting one flag. This way of acquiring locks might reduce contention if every update is trying to do some independent work, but here all we are doing is setting the same flag with same value.

Actually, to reduce contention on rnp_root->lock.

The trick is that the "losers" at each level of ->fqslock acquisition go away. The "winner" ends up doing the real work of setting RCU_GP_FLAG_FQS.

Quoted 3 lines

We can also remove fqslock completely if we do not need this. Also using cmpxchg() to set the value of the flag looks like a good idea to avoid taking the root node lock. Thoughts?

Quoted 6 lines

The ->fqslock funnel was needed to avoid lockups on large systems (many hundreds or even thousands of CPUs). Moving grace-period responsibilities from softirq to the grace-period kthreads might have reduced contention sufficienty to make the ->fqslock funnel unnecessary. However, given that I don't usually have access to such a large system, I will leave it, at least for the time being.

Quoted 3 lines

Sounds like a good case study for using the newly introduced MCS based locks(qspinlock.h).
Waiman, Peter?

The ticket trylock and queue trylock are similar in the sense they both do a read to check if the lock is free first and then use cmpxchg() to acquire the lock. So if it is a problem to use ticket spinlock, it will be a problem for the queue spinlock as well. The advantage of the queue spinlock in a heavily contended case is that the lock waiters except the one in the head of the queue will not be contending the lock cacheline.

Quoted 4 lines

Btw, is doing the following a bad idea? It reduces contention on rnp_root->lock using fqslock
which seems to be the lock which needs to be taken while forcing a quiescent state:

I don't see any problem with the existing code as long as the number of funnel levels is small. You really need to have some performance data to show that your approach is better.

Quoted 18 lines

kernel/rcu/tree.c +0 -10

index f1ba773..f5a0e7e 100644
@@ -2401,34 +2401,24 @@ static void force_quiescent_state(struct rcu_state *rsp)
     unsigned long flags;
     bool ret;
     struct rcu_node *rnp;
-    struct rcu_node *rnp_old = NULL;
-
-    /* Funnel through hierarchy to reduce memory contention. */
-    rnp = per_cpu_ptr(rsp->rda, raw_smp_processor_id())->mynode;
-    for (; rnp != NULL; rnp = rnp->parent) {
-        ret = (ACCESS_ONCE(rsp->gp_flags)&  RCU_GP_FLAG_FQS) ||
-              !raw_spin_trylock(&rnp->fqslock);
-        if (rnp_old != NULL)
-            raw_spin_unlock(&rnp_old->fqslock);
-        if (ret) {

kernel/rcu/tree.c static void force_quiescent_state(struct rcu_state *rsp) · line 2409

Quoted 10 lines

kernel/rcu/tree.c +5 -4

-            ACCESS_ONCE(rsp->n_force_qs_lh)++;
-            return;
-        }
-        rnp_old = rnp;
+    struct rcu_node *rnp_root = rcu_get_root(rsp);
+
+    if (!raw_spin_trylock(rnp_root->fqslock)) {
+        ACCESS_ONCE(rsp->n_force_qs_lh)++;
+        return;  /* Someone is already trying to force */
     }

I think it is better to check the gp_flags first before doing a trylock.

-Longman

Quoted 46 lines · Waiman Long

Quoted 34 lines · Romanov Arya

Quoted 26 lines · Paul E. McKenney

Quoted 10 lines · Pranith Kumar

This might sound really naive, but please bear with me.

force_quiescent_state() used to do a lot of things in the past in addition to forcing a quiescent state. (In my reading of the mailing list I found state transitions for one).

Now according to the code, what is being done is multiple callers try to go up the hierarchy of nodes to see who reaches the root node. The caller reaching the root node wins and it acquires root node lock and it gets to set rsp->gp_flags!

Quoted 7 lines

At each level of the hierarchy we try to acquire fqslock. This is the only place which actually uses fqslock.

I guess this was being done to avoid the contention on fqslock, but all we are doing here is setting one flag. This way of acquiring locks might reduce contention if every update is trying to do some independent work, but here all we are doing is setting the same flag with same value.

Actually, to reduce contention on rnp_root->lock.

The trick is that the "losers" at each level of ->fqslock acquisition go away. The "winner" ends up doing the real work of setting RCU_GP_FLAG_FQS.

Quoted 3 lines

We can also remove fqslock completely if we do not need this. Also using cmpxchg() to set the value of the flag looks like a good idea to avoid taking the root node lock. Thoughts?

Quoted 6 lines

The ->fqslock funnel was needed to avoid lockups on large systems (many hundreds or even thousands of CPUs). Moving grace-period responsibilities from softirq to the grace-period kthreads might have reduced contention sufficienty to make the ->fqslock funnel unnecessary. However, given that I don't usually have access to such a large system, I will leave it, at least for the time being.

Quoted 3 lines

Sounds like a good case study for using the newly introduced MCS based locks(qspinlock.h).
Waiman, Peter?

The ticket trylock and queue trylock are similar in the sense they both do a read to check if the lock is free first and then use cmpxchg() to acquire the lock. So if it is a problem to use ticket spinlock, it will be a problem for the queue spinlock as well. The advantage of the queue spinlock in a heavily contended case is that the lock waiters except the one in the head of the queue will not be contending the lock cacheline.

Quoted 7 lines

Quoted 4 lines

Btw, is doing the following a bad idea? It reduces contention on rnp_root->lock using fqslock
which seems to be the lock which needs to be taken while forcing a quiescent state:

I don't see any problem with the existing code as long as the number of funnel levels is small.

Quoted 2 lines

You really need to have some performance
data to show that your approach is better.

What Waiman said.

And you will need that performance data taken on systems with at least 1024 CPUs, because it was those systems that motivated this code.

Thanx, Paul

Quoted 33 lines

Quoted 18 lines

kernel/rcu/tree.c +0 -10

index f1ba773..f5a0e7e 100644
@@ -2401,34 +2401,24 @@ static void force_quiescent_state(struct rcu_state *rsp)
     unsigned long flags;
     bool ret;
     struct rcu_node *rnp;
-    struct rcu_node *rnp_old = NULL;
-
-    /* Funnel through hierarchy to reduce memory contention. */
-    rnp = per_cpu_ptr(rsp->rda, raw_smp_processor_id())->mynode;
-    for (; rnp != NULL; rnp = rnp->parent) {
-        ret = (ACCESS_ONCE(rsp->gp_flags)&  RCU_GP_FLAG_FQS) ||
-              !raw_spin_trylock(&rnp->fqslock);
-        if (rnp_old != NULL)
-            raw_spin_unlock(&rnp_old->fqslock);
-        if (ret) {

kernel/rcu/tree.c static void force_quiescent_state(struct rcu_state *rsp) · line 2409

Quoted 10 lines

kernel/rcu/tree.c +5 -4

-            ACCESS_ONCE(rsp->n_force_qs_lh)++;
-            return;
-        }
-        rnp_old = rnp;
+    struct rcu_node *rnp_root = rcu_get_root(rsp);
+
+    if (!raw_spin_trylock(rnp_root->fqslock)) {
+        ACCESS_ONCE(rsp->n_force_qs_lh)++;
+        return;  /* Someone is already trying to force */
     }

I think it is better to check the gp_flags first before doing a trylock.

-Longman

Pranith, Romanov: You do -not-, repeat -not-, get to shoot from the hip with this code. You absolutely need to understand what it is doing and why before you try hacking on it. Otherwise, all that will happen is that you will come up with additional creative ways to break RCU. Your commit log and comments will need to clearly indicate that you understand what happens if (say) 4096 CPUs all call force_quiescent_state() at the same time.

Oh, and to answer the implicit question... A properly configured 4096-CPU system will have two funnel levels, with 64 nodes at the leaf level and a single node at the root level. If the system is not properly configured, it will have three funnel levels. The maximum number of funnel levels is four, which would handle more than four million CPUs (sixteen million if properly configured), so we should be good. ;-)

The larger numbers of levels are intended strictly for testing. I set CONFIG_RCU_FANOUT_LEAF=2 and CONFIG_RCU_FANOUT=2 on a 16-CPU system just to make sure that I am testing something uglier than what will be running in production. A large system should have both of these set to 64, though this requires also booting with skew_tick=1 as well.

Thanx, Paul

Oh, and to answer the implicit question... A properly configured 4096-CPU system will have two funnel levels, with 64 nodes at the leaf level and a single node at the root level. If the system is not properly configured, it will have three funnel levels. The maximum number of funnel levels is four, which would handle more than four million CPUs (sixteen million if properly configured), so we should be good. ;-)

The larger numbers of levels are intended strictly for testing. I set CONFIG_RCU_FANOUT_LEAF=2 and CONFIG_RCU_FANOUT=2 on a 16-CPU system just to make sure that I am testing something uglier than what will be running in production. A large system should have both of these set to 64, though this requires also booting with skew_tick=1 as well.

Quoted 7 lines · Paul E. McKenney

Oh, and to answer the implicit question... A properly configured 4096-CPU system will have two funnel levels, with 64 nodes at the leaf level and a single node at the root level. If the system is not properly configured, it will have three funnel levels. The maximum number of funnel levels is four, which would handle more than four million CPUs (sixteen million if properly configured), so we should be good. ;-)

Quoted 5 lines

The larger numbers of levels are intended strictly for testing. I set CONFIG_RCU_FANOUT_LEAF=2 and CONFIG_RCU_FANOUT=2 on a 16-CPU system just to make sure that I am testing something uglier than what will be running in production. A large system should have both of these set to 64, though this requires also booting with skew_tick=1 as well.

Right, and I think we talked about this before; the first thing one should do is align the RCU fanout masks with the actual machine topology. Because currently they can be all over the place.

Quoted 14 lines · Peter Zijlstra

Quoted 7 lines · Paul E. McKenney

Oh, and to answer the implicit question... A properly configured 4096-CPU system will have two funnel levels, with 64 nodes at the leaf level and a single node at the root level. If the system is not properly configured, it will have three funnel levels. The maximum number of funnel levels is four, which would handle more than four million CPUs (sixteen million if properly configured), so we should be good. ;-)

Quoted 5 lines

The larger numbers of levels are intended strictly for testing. I set CONFIG_RCU_FANOUT_LEAF=2 and CONFIG_RCU_FANOUT=2 on a 16-CPU system just to make sure that I am testing something uglier than what will be running in production. A large system should have both of these set to 64, though this requires also booting with skew_tick=1 as well.

Quoted 3 lines

Right, and I think we talked about this before; the first thing one should do is align the RCU fanout masks with the actual machine topology. Because currently they can be all over the place.

And we also talked before about how it would make a lot more sense to align the CPU numbering with the actual machine topology, as that would fix the problem in one place. But either way, in the particular case of the RCU fanout, does anyone have any real data showing that this is a real problem? Given that the rcu_node accesses are quite a ways off of any fastpath, I remain skeptical.

Quoted 19 lines · Paul E. McKenney

Quoted 14 lines · Peter Zijlstra

Quoted 7 lines · Paul E. McKenney

Oh, and to answer the implicit question... A properly configured 4096-CPU system will have two funnel levels, with 64 nodes at the leaf level and a single node at the root level. If the system is not properly configured, it will have three funnel levels. The maximum number of funnel levels is four, which would handle more than four million CPUs (sixteen million if properly configured), so we should be good. ;-)

Quoted 5 lines

The larger numbers of levels are intended strictly for testing. I set CONFIG_RCU_FANOUT_LEAF=2 and CONFIG_RCU_FANOUT=2 on a 16-CPU system just to make sure that I am testing something uglier than what will be running in production. A large system should have both of these set to 64, though this requires also booting with skew_tick=1 as well.

Quoted 3 lines

Right, and I think we talked about this before; the first thing one should do is align the RCU fanout masks with the actual machine topology. Because currently they can be all over the place.

Quoted 6 lines

And we also talked before about how it would make a lot more sense to align the CPU numbering with the actual machine topology, as that would fix the problem in one place. But either way, in the particular case of the RCU fanout, does anyone have any real data showing that this is a real problem? Given that the rcu_node accesses are quite a ways off of any fastpath, I remain skeptical.

And one way to test for this is to set CONFIG_RCU_FANOUT to the number of cores in a socket (or to the number of hardware threads per socket for systems that number their hardware threads consecutively), then specify CONFIG_RCU_FANOUT_EXACT=y. This will align the rcu_node structures with the sockets. If the number of cores/threads per socket is too large, you can of course use a smaller number that exactly divides the number of cores/threads per socket.

Quoted 27 lines · Paul E. McKenney

Quoted 19 lines · Paul E. McKenney

Quoted 14 lines · Peter Zijlstra

Quoted 7 lines · Paul E. McKenney

Oh, and to answer the implicit question... A properly configured 4096-CPU system will have two funnel levels, with 64 nodes at the leaf level and a single node at the root level. If the system is not properly configured, it will have three funnel levels. The maximum number of funnel levels is four, which would handle more than four million CPUs (sixteen million if properly configured), so we should be good. ;-)

Quoted 5 lines

The larger numbers of levels are intended strictly for testing. I set CONFIG_RCU_FANOUT_LEAF=2 and CONFIG_RCU_FANOUT=2 on a 16-CPU system just to make sure that I am testing something uglier than what will be running in production. A large system should have both of these set to 64, though this requires also booting with skew_tick=1 as well.

Quoted 3 lines

Right, and I think we talked about this before; the first thing one should do is align the RCU fanout masks with the actual machine topology. Because currently they can be all over the place.

Quoted 6 lines

And we also talked before about how it would make a lot more sense to align the CPU numbering with the actual machine topology, as that would fix the problem in one place. But either way, in the particular case of the RCU fanout, does anyone have any real data showing that this is a real problem? Given that the rcu_node accesses are quite a ways off of any fastpath, I remain skeptical.

Quoted 7 lines

And one way to test for this is to set CONFIG_RCU_FANOUT to the number of cores in a socket (or to the number of hardware threads per socket for systems that number their hardware threads consecutively), then specify CONFIG_RCU_FANOUT_EXACT=y. This will align the rcu_node structures with the sockets. If the number of cores/threads per socket is too large, you can of course use a smaller number that exactly divides the number of cores/threads per socket.

Typical Intel cpu numbering is [0..n) for SMT0 and [n..2*n) for SMT1, so that'll fall flat on its face at try 1.