lib/seq.h

   1 /*
   2  * Copyright (c) 2013, 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 #ifndef SEQ_H
  18 #define SEQ_H 1
  19
  20 /* Thread-safe, pollable sequence number.
  21  *
  22  *
  23  * Motivation
  24  * ==========
  25  *
  26  * It is sometimes desirable to take an action whenever an object changes.
  27  * Suppose we associate a sequence number with an object and increment the
  28  * sequence number whenver we change the object.  An observer can then record
  29  * the sequence number it sees.  Later on, if the current sequence number
  30  * differs from the one it saw last, then the observer knows to examine the
  31  * object for changes.
  32  *
  33  * Code that wants to run when a sequence number changes is challenging to
  34  * implement in a multithreaded environment.  A naive implementation, that
  35  * simply checks whether the sequence number changed and, if so, calls
  36  * poll_immediate_wake(), will fail when another thread increments the sequence
  37  * number after the check (including during poll_block()).
  38  *
  39  * struct seq is a solution.  It implements a sequence number along with enough
  40  * internal infrastructure so that a thread waiting on a particular value will
  41  * wake up if the sequence number changes, or even if the "struct seq" is
  42  * destroyed.
  43  *
  44  *
  45  * Usage
  46  * =====
  47  *
  48  * The object that includes a sequence number should use seq_create() and
  49  * seq_destroy() at creation and destruction, and seq_change() whenever the
  50  * object's observable state changes.
  51  *
  52  * An observer may seq_read() to read the current sequence number and
  53  * seq_wait() to cause poll_block() to wake up when the sequence number changes
  54  * from a specified value.
  55  *
  56  * To avoid races, observers should use seq_read() to check for changes,
  57  * process any changes, and then use seq_wait() to wait for a change from the
  58  * previously read value.  That is, a correct usage looks something like this:
  59  *
  60  *    new_seq = seq_read(seq);
  61  *    if (new_seq != last_seq) {
  62  *        ...process changes...
  63  *        last_seq = new_seq;
  64  *    }
  65  *    seq_wait(seq, new_seq);
  66  *    poll_block();
  67  *
  68  *
  69  * Alternate Usage
  70  * ===============
  71  *
  72  * struct seq can also be used as a sort of pollable condition variable.
  73  * Suppose that we want a thread to process items in a queue, and thus to be
  74  * able to wake up whenever the queue is nonempty.  This requires a lock to
  75  * protect the queue and a seq to signal that the queue has become nonempty,
  76  * e.g.:
  77  *
  78  *    struct ovs_mutex mutex;
  79  *    struct ovs_list queue OVS_GUARDED_BY(mutex);
  80  *    struct seq nonempty_seq;
  81  *
  82  * To add an element to the queue:
  83  *
  84  *    ovs_mutex_lock(&mutex);
  85  *    list_push_back(&queue, ...element...);
  86  *    if (list_is_singleton(&queue)) {   // The 'if' test here is optional.
  87  *        seq_change(&nonempty_seq);
  88  *    }
  89  *    ovs_mutex_unlock(&mutex);
  90  *
  91  * To wait for the queue to become nonempty:
  92  *
  93  *    ovs_mutex_lock(&mutex);
  94  *    if (list_is_empty(&queue)) {
  95  *        seq_wait(&nonempty_seq, seq_read(&nonempty_seq));
  96  *    } else {
  97  *        poll_immediate_wake();
  98  *    }
  99  *    ovs_mutex_unlock(&mutex);
 100  *
 101  * (In the above code 'mutex' prevents the queue from changing between
 102  * seq_read() and seq_wait().  Otherwise, it would be necessary to seq_read(),
 103  * check for a nonempty queue, and then seq_wait() on the previously read
 104  * sequence number, as under Usage above.)
 105  *
 106  *
 107  * Thread-safety
 108  * =============
 109  *
 110  * Fully thread safe.  seq_change() synchronizes with seq_read() and
 111  * seq_wait() on the same variable in release-acquire fashion.  That
 112  * is, all effects of the memory accesses performed by a thread prior
 113  * to seq_change() are visible to the threads returning from
 114  * seq_read() or seq_wait() observing that change.
 115  */
 116
 117 #include <stdint.h>
 118 #include "util.h"
 119
 120 /* For implementation of an object with a sequence number attached. */
 121 struct seq *seq_create(void);
 122 void seq_destroy(struct seq *);
 123 void seq_change(struct seq *);
 124
 125 /* For observers. */
 126 uint64_t seq_read(const struct seq *);
 127
 128 void seq_wait_at(const struct seq *, uint64_t value, const char *where);
 129 #define seq_wait(seq, value) seq_wait_at(seq, value, OVS_SOURCE_LOCATOR)
 130
 131 /* For poll_block() internal use. */
 132 void seq_woke(void);
 133
 134 #endif /* seq.h */