urcu-qsbr: avoid useless futex wakeups and burning CPU for long grace periods

I noticed that urcu makes exactly _one_ attempt at using futexes
to avoid busy looping on synchronize_rcu.  The attached patch instead
switches from busy waiting to futexes after RCU_QS_ACTIVE_ATTEMPTS.
To limit the amount of system calls, reading threads remember whether
they already had a quiescent state in this grace period; if so they were
already removed from the list, and can avoid signaling the futex.

Performance measured with rcutorture (nreaders: 10, nupdaters: 1,
duration: 10, median of nine runs):

     RCU_QS_ACTIVE_ATTEMPTS == 100, no patch         n_updates = 292
     RCU_QS_ACTIVE_ATTEMPTS == 1, no patch           n_updates = 290
     RCU_QS_ACTIVE_ATTEMPTS == 100, with patch       n_updates = 408
     RCU_QS_ACTIVE_ATTEMPTS == 1, with patch         n_updates = 404

(the first two cases are obviously the same; the only change is
when the futex is used, but over many calls there is no difference).

This patch matches the update to the Promela model.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

diff --git a/urcu-qsbr.c b/urcu-qsbr.c
index a239be036d416f68259c0f586f5d0ce7248385e9..8d8a9cf05ced0fd18ef9943110dc22a2e6e05e87 100644 (file)
--- a/urcu-qsbr.c
+++ b/urcu-qsbr.c
@@ -150,26 +150,33 @@ static void update_counter_and_wait(void)
         */
        for (;;) {
                wait_loops++;
-               if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS) {
-                       uatomic_dec(&gp_futex);
+               if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
+                       uatomic_set(&gp_futex, -1);
+                       /*
+                        * Write futex before write waiting (the other side
+                        * reads them in the opposite order).
+                        */
+                       cmm_smp_wmb();
+                       cds_list_for_each_entry(index, &registry, node) {
+                               _CMM_STORE_SHARED(index->waiting, 1);
+                       }
                        /* Write futex before read reader_gp */
                        cmm_smp_mb();
                }
-
                cds_list_for_each_entry_safe(index, tmp, &registry, node) {
                        if (!rcu_gp_ongoing(&index->ctr))
                                cds_list_move(&index->node, &qsreaders);
                }
 
                if (cds_list_empty(&registry)) {
-                       if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS) {
+                       if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
                                /* Read reader_gp before write futex */
                                cmm_smp_mb();
                                uatomic_set(&gp_futex, 0);
                        }
                        break;
                } else {
-                       if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS) {
+                       if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
                                wait_gp();
                        } else {
 #ifndef HAS_INCOHERENT_CACHES

diff --git a/urcu/static/urcu-qsbr.h b/urcu/static/urcu-qsbr.h
index 5b7adac658bfe1b64264d3adcf2b06e0a00c2430..489abb0c399cc1026b387f37960530dfb9400bdf 100644 (file)
--- a/urcu/static/urcu-qsbr.h
+++ b/urcu/static/urcu-qsbr.h
@@ -124,6 +124,7 @@ struct rcu_reader {
        unsigned long ctr;
        /* Data used for registry */
        struct cds_list_head node __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
+       int waiting;
        pthread_t tid;
 };
 
@@ -136,7 +137,11 @@ extern int32_t gp_futex;
  */
 static inline void wake_up_gp(void)
 {
-       if (unlikely(uatomic_read(&gp_futex) == -1)) {
+       if (unlikely(_CMM_LOAD_SHARED(rcu_reader.waiting))) {
+               _CMM_STORE_SHARED(rcu_reader.waiting, 0);
+               cmm_smp_mb();
+               if (uatomic_read(&gp_futex) != -1)
+                       return;
                uatomic_set(&gp_futex, 0);
                futex_noasync(&gp_futex, FUTEX_WAKE, 1,
                      NULL, NULL, 0);