lib/ovs-rcu.c

   1 /*
   2  * Copyright (c) 2014 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18 #include "ovs-rcu.h"
  19 #include "fatal-signal.h"
  20 #include "guarded-list.h"
  21 #include "list.h"
  22 #include "ovs-thread.h"
  23 #include "poll-loop.h"
  24 #include "seq.h"
  25 #include "timeval.h"
  26 #include "openvswitch/vlog.h"
  27
  28 VLOG_DEFINE_THIS_MODULE(ovs_rcu);
  29
  30 struct ovsrcu_cb {
  31     void (*function)(void *aux);
  32     void *aux;
  33 };
  34
  35 struct ovsrcu_cbset {
  36     struct ovs_list list_node;
  37     struct ovsrcu_cb cbs[16];
  38     int n_cbs;
  39 };
  40
  41 struct ovsrcu_perthread {
  42     struct ovs_list list_node;  /* In global list. */
  43
  44     struct ovs_mutex mutex;
  45     uint64_t seqno;
  46     struct ovsrcu_cbset *cbset;
  47     char name[16];              /* This thread's name. */
  48 };
  49
  50 static struct seq *global_seqno;
  51
  52 static pthread_key_t perthread_key;
  53 static struct ovs_list ovsrcu_threads;
  54 static struct ovs_mutex ovsrcu_threads_mutex;
  55
  56 static struct guarded_list flushed_cbsets;
  57 static struct seq *flushed_cbsets_seq;
  58
  59 static void ovsrcu_init_module(void);
  60 static void ovsrcu_flush_cbset(struct ovsrcu_perthread *);
  61 static void ovsrcu_unregister__(struct ovsrcu_perthread *);
  62 static bool ovsrcu_call_postponed(void);
  63 static void *ovsrcu_postpone_thread(void *arg OVS_UNUSED);
  64
  65 static struct ovsrcu_perthread *
  66 ovsrcu_perthread_get(void)
  67 {
  68     struct ovsrcu_perthread *perthread;
  69
  70     ovsrcu_init_module();
  71
  72     perthread = pthread_getspecific(perthread_key);
  73     if (!perthread) {
  74         const char *name = get_subprogram_name();
  75
  76         perthread = xmalloc(sizeof *perthread);
  77         ovs_mutex_init(&perthread->mutex);
  78         perthread->seqno = seq_read(global_seqno);
  79         perthread->cbset = NULL;
  80         ovs_strlcpy(perthread->name, name[0] ? name : "main",
  81                     sizeof perthread->name);
  82
  83         ovs_mutex_lock(&ovsrcu_threads_mutex);
  84         list_push_back(&ovsrcu_threads, &perthread->list_node);
  85         ovs_mutex_unlock(&ovsrcu_threads_mutex);
  86
  87         pthread_setspecific(perthread_key, perthread);
  88     }
  89     return perthread;
  90 }
  91
  92 /* Indicates the end of a quiescent state.  See "Details" near the top of
  93  * ovs-rcu.h.
  94  *
  95  * Quiescent states don't stack or nest, so this always ends a quiescent state
  96  * even if ovsrcu_quiesce_start() was called multiple times in a row. */
  97 void
  98 ovsrcu_quiesce_end(void)
  99 {
 100     ovsrcu_perthread_get();
 101 }
 102
 103 static void
 104 ovsrcu_quiesced(void)
 105 {
 106     if (single_threaded()) {
 107         ovsrcu_call_postponed();
 108     } else {
 109         static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER;
 110         if (ovsthread_once_start(&once)) {
 111             ovs_thread_create("urcu", ovsrcu_postpone_thread, NULL);
 112             ovsthread_once_done(&once);
 113         }
 114     }
 115 }
 116
 117 /* Indicates the beginning of a quiescent state.  See "Details" near the top of
 118  * ovs-rcu.h. */
 119 void
 120 ovsrcu_quiesce_start(void)
 121 {
 122     struct ovsrcu_perthread *perthread;
 123
 124     ovsrcu_init_module();
 125     perthread = pthread_getspecific(perthread_key);
 126     if (perthread) {
 127         pthread_setspecific(perthread_key, NULL);
 128         ovsrcu_unregister__(perthread);
 129     }
 130
 131     ovsrcu_quiesced();
 132 }
 133
 134 /* Indicates a momentary quiescent state.  See "Details" near the top of
 135  * ovs-rcu.h.
 136  *
 137  * Provides a full memory barrier via seq_change().
 138  */
 139 void
 140 ovsrcu_quiesce(void)
 141 {
 142     struct ovsrcu_perthread *perthread;
 143
 144     perthread = ovsrcu_perthread_get();
 145     perthread->seqno = seq_read(global_seqno);
 146     if (perthread->cbset) {
 147         ovsrcu_flush_cbset(perthread);
 148     }
 149     seq_change(global_seqno);
 150
 151     ovsrcu_quiesced();
 152 }
 153
 154 bool
 155 ovsrcu_is_quiescent(void)
 156 {
 157     ovsrcu_init_module();
 158     return pthread_getspecific(perthread_key) == NULL;
 159 }
 160
 161 void
 162 ovsrcu_synchronize(void)
 163 {
 164     unsigned int warning_threshold = 1000;
 165     uint64_t target_seqno;
 166     long long int start;
 167
 168     if (single_threaded()) {
 169         return;
 170     }
 171
 172     target_seqno = seq_read(global_seqno);
 173     ovsrcu_quiesce_start();
 174     start = time_msec();
 175
 176     for (;;) {
 177         uint64_t cur_seqno = seq_read(global_seqno);
 178         struct ovsrcu_perthread *perthread;
 179         char stalled_thread[16];
 180         unsigned int elapsed;
 181         bool done = true;
 182
 183         ovs_mutex_lock(&ovsrcu_threads_mutex);
 184         LIST_FOR_EACH (perthread, list_node, &ovsrcu_threads) {
 185             if (perthread->seqno <= target_seqno) {
 186                 ovs_strlcpy(stalled_thread, perthread->name,
 187                             sizeof stalled_thread);
 188                 done = false;
 189                 break;
 190             }
 191         }
 192         ovs_mutex_unlock(&ovsrcu_threads_mutex);
 193
 194         if (done) {
 195             break;
 196         }
 197
 198         elapsed = time_msec() - start;
 199         if (elapsed >= warning_threshold) {
 200             VLOG_WARN("blocked %u ms waiting for %s to quiesce",
 201                       elapsed, stalled_thread);
 202             warning_threshold *= 2;
 203         }
 204         poll_timer_wait_until(start + warning_threshold);
 205
 206         seq_wait(global_seqno, cur_seqno);
 207         poll_block();
 208     }
 209     ovsrcu_quiesce_end();
 210 }
 211
 212 /* Registers 'function' to be called, passing 'aux' as argument, after the
 213  * next grace period.
 214  *
 215  * The call is guaranteed to happen after the next time all participating
 216  * threads have quiesced at least once, but there is no quarantee that all
 217  * registered functions are called as early as possible, or that the functions
 218  * registered by different threads would be called in the order the
 219  * registrations took place.  In particular, even if two threads provably
 220  * register a function each in a specific order, the functions may still be
 221  * called in the opposite order, depending on the timing of when the threads
 222  * call ovsrcu_quiesce(), how many functions they postpone, and when the
 223  * ovs-rcu thread happens to grab the functions to be called.
 224  *
 225  * All functions registered by a single thread are guaranteed to execute in the
 226  * registering order, however.
 227  *
 228  * This function is more conveniently called through the ovsrcu_postpone()
 229  * macro, which provides a type-safe way to allow 'function''s parameter to be
 230  * any pointer type. */
 231 void
 232 ovsrcu_postpone__(void (*function)(void *aux), void *aux)
 233 {
 234     struct ovsrcu_perthread *perthread = ovsrcu_perthread_get();
 235     struct ovsrcu_cbset *cbset;
 236     struct ovsrcu_cb *cb;
 237
 238     cbset = perthread->cbset;
 239     if (!cbset) {
 240         cbset = perthread->cbset = xmalloc(sizeof *perthread->cbset);
 241         cbset->n_cbs = 0;
 242     }
 243
 244     cb = &cbset->cbs[cbset->n_cbs++];
 245     cb->function = function;
 246     cb->aux = aux;
 247
 248     if (cbset->n_cbs >= ARRAY_SIZE(cbset->cbs)) {
 249         ovsrcu_flush_cbset(perthread);
 250     }
 251 }
 252
 253 static bool
 254 ovsrcu_call_postponed(void)
 255 {
 256     struct ovsrcu_cbset *cbset;
 257     struct ovs_list cbsets;
 258
 259     guarded_list_pop_all(&flushed_cbsets, &cbsets);
 260     if (list_is_empty(&cbsets)) {
 261         return false;
 262     }
 263
 264     ovsrcu_synchronize();
 265
 266     LIST_FOR_EACH_POP (cbset, list_node, &cbsets) {
 267         struct ovsrcu_cb *cb;
 268
 269         for (cb = cbset->cbs; cb < &cbset->cbs[cbset->n_cbs]; cb++) {
 270             cb->function(cb->aux);
 271         }
 272         free(cbset);
 273     }
 274
 275     return true;
 276 }
 277
 278 static void *
 279 ovsrcu_postpone_thread(void *arg OVS_UNUSED)
 280 {
 281     pthread_detach(pthread_self());
 282
 283     for (;;) {
 284         uint64_t seqno = seq_read(flushed_cbsets_seq);
 285         if (!ovsrcu_call_postponed()) {
 286             seq_wait(flushed_cbsets_seq, seqno);
 287             poll_block();
 288         }
 289     }
 290
 291     OVS_NOT_REACHED();
 292 }
 293
 294 static void
 295 ovsrcu_flush_cbset(struct ovsrcu_perthread *perthread)
 296 {
 297     struct ovsrcu_cbset *cbset = perthread->cbset;
 298
 299     if (cbset) {
 300         guarded_list_push_back(&flushed_cbsets, &cbset->list_node, SIZE_MAX);
 301         perthread->cbset = NULL;
 302
 303         seq_change(flushed_cbsets_seq);
 304     }
 305 }
 306
 307 static void
 308 ovsrcu_unregister__(struct ovsrcu_perthread *perthread)
 309 {
 310     if (perthread->cbset) {
 311         ovsrcu_flush_cbset(perthread);
 312     }
 313
 314     ovs_mutex_lock(&ovsrcu_threads_mutex);
 315     list_remove(&perthread->list_node);
 316     ovs_mutex_unlock(&ovsrcu_threads_mutex);
 317
 318     ovs_mutex_destroy(&perthread->mutex);
 319     free(perthread);
 320
 321     seq_change(global_seqno);
 322 }
 323
 324 static void
 325 ovsrcu_thread_exit_cb(void *perthread)
 326 {
 327     ovsrcu_unregister__(perthread);
 328 }
 329
 330 /* Cancels the callback to ovsrcu_thread_exit_cb().
 331  *
 332  * Cancelling the call to the destructor during the main thread exit
 333  * is needed while using pthreads-win32 library in Windows. It has been
 334  * observed that in pthreads-win32, a call to the destructor during
 335  * main thread exit causes undefined behavior. */
 336 static void
 337 ovsrcu_cancel_thread_exit_cb(void *aux OVS_UNUSED)
 338 {
 339     pthread_setspecific(perthread_key, NULL);
 340 }
 341
 342 static void
 343 ovsrcu_init_module(void)
 344 {
 345     static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER;
 346     if (ovsthread_once_start(&once)) {
 347         global_seqno = seq_create();
 348         xpthread_key_create(&perthread_key, ovsrcu_thread_exit_cb);
 349         fatal_signal_add_hook(ovsrcu_cancel_thread_exit_cb, NULL, NULL, true);
 350         list_init(&ovsrcu_threads);
 351         ovs_mutex_init(&ovsrcu_threads_mutex);
 352
 353         guarded_list_init(&flushed_cbsets);
 354         flushed_cbsets_seq = seq_create();
 355
 356         ovsthread_once_done(&once);
 357     }
 358 }